Re: [igraph] graph representation in memory

[Gábor Csárdi]

Emmanuel,

this is great, thanks for sharing it! Nice to see that not too many
modifications were needed to achieve it. If you want a new branch on
Launchpad, that is of course possible, just register on bazaar, push
the branch, tell me its name and then I will add it to the list of
igraph branches.

We can potentially add it to igraph as well, and then you could choose
between different data representations at compile time. We'll see, it
would be a nice feature. I don't think that it solves the problem of
_really_ _very_ superlarge graphs (those probably require specialized
algorithms and not igraph), but it might be still useful to some
people.

Porting it to 0.6 should not be very difficult.

The R interface surely does not work with it, unfortunately, but
that's a problem with the R interface, not with your code.

May I ask you at which department/faculty/class you're doing this?

Best Regards,
Gabor

On Wed, Mar 25, 2009 at 11:18 AM, E. Navarro <address@hidden> wrote:
> Hello,
>
> I was about to send a email presenting a database implementation of
> igraph basic layer we write with 4 schoolmates as school project
> (also...). Perhaps it might be helpful for you Mati.
>
> We started modifications from 0.5.1. You can find the last -working-
> source package of our work here :
> https://wwwsecu.irit.fr/FILEX/get?k=aXR2nQQGgzdvgcbfhf4 (open the link
> and just wait 5sec)
> Changes are mainly in igraph.h and basicinterface_db.c which replace
> type_indexededgelist.c. The Makefile configuration also changes a bit
> to renamed the compiled library.
>
> Currently we work on our own subversion repository. But it could be
> better to open a new branch in launchpad bazaar, if some people are
> interested in and If it's ok for you Gabor and Tamas.
>
> In few words :
>  - it use unixOdbc,
>  - database (mysql) slow down performances from 20 to 100 times,
>  - we didn't test R layer,
>  - python layer work fine...
>
> Also I plan to improve this implementation, mainly :
>  - merge the code with igraph 0.6
>  - store attributes in the database
>  - create a cache system in physical memory
>
> Best regards,
> Emmanuel N.
>
> 2009/3/23 Chris Wj <address@hidden>
>>
>> I would be interested in following your progress, learning a bit, and making 
>> the same modifications. Please post to the mailing list as you make updates 
>> and the such.
>>
>> Question, have you started modifications from the 0.6 main launchpad bazaar 
>> branch? Or are you modifying 0.5.1/0.5.2?
>>
>> Thanks,
>> Chris
>>
>> On Mon, Mar 23, 2009 at 1:47 PM, Gábor Csárdi <address@hidden> wrote:
>>>
>>> Hi Mati,
>>>
>>> you are completely right, it is better to use (long) int instead of
>>> double, this was a design mistake on my part.
>>>
>>> As for the work, it should not be very difficult. In theory, all
>>> functions that you need to rewrite are in type_indexededgelist.c.
>>> Plus, there are three macros in igraph.h that you need to update or
>>> rewrite as a function: IGRAPH_FROM, IGRAPH_TO and IGRAPH_OTHER.
>>>
>>> This is theoretically enough for the C library and probably also for
>>> Python. For R you need a bit more, you need to write some conversion
>>> functions and rewrite iterators.R as well.
>>>
>>> Many C functions transform the igraph_t into a plain adjacency list,
>>> or one containing edge ids. For better performance you would need to
>>> rewrite these too, they are igraph_adjlist_t and igraph_adjedgelist,
>>> plus lazy versions of these. You can rewrite these just to use the
>>> normal operations of your new data structure.
>>>
>>> Maybe I forgot some minor things, but I thing roughly this is it.
>>>
>>> Of course I can help you if you decide to work on this, assuming you
>>> need any help. :)
>>>
>>> May I ask you what kind of data structure you have in mind? Do you
>>> intend to put it into igraph, or the goal is just to play with it a
>>> bit?
>>>
>>> Btw. I am not sure what you can actually do with a graph with 100
>>> million nodes and a general graph library. You cannot calculate too
>>> many things and perhaps you're better off coding them without using
>>> igraph at all. But I understand that this is a school project. :)
>>>
>>> Best,
>>> Gabor
>>>
>>> On Mon, Mar 23, 2009 at 6:15 PM, Mati Vait <address@hidden> wrote:
>>> > Hello,
>>> > as a school project we are investigating scalability of graph algorithms
>>> > on very large undirected graphs. Graphs under question have hundreds of
>>> > millions of nodes, billions of edges), but we have run into some memory
>>> > issues with igraph because of it's way of holding graph in memory
>>> > exhausts ram really fast. We reached this conclusion by looking at
>>> > comments on igraph_t in include/igraph.h and testing on cluster with
>>> > 32GB ram for each node. At the moment we are able to hold in memory a
>>> > graph with 100 million nodes and 300 million edges which uses about 27.9
>>> > GB of ram (after tweaking igraph_real_t and igraph_integer_t types to
>>> > use int instead of double).
>>> > Questions:
>>> > How difficult it is to implement another way of graph representation
>>> > instead of current one? Some loss in work time could be tolerated.
>>> >
>>> > What code must be reimplemented in order to keep algorithms running?
>>> >
>>> >
>>> >
>>> > Some insight and references to specific documentation would be really
>>> > helpful.
>>> >
>>> > Thank you for your time,
>>> > Mati
>>> >
>>> >
>>> >
>>> > _______________________________________________
>>> > igraph-help mailing list
>>> > address@hidden
>>> > http://lists.nongnu.org/mailman/listinfo/igraph-help
>>> >
>>>
>>>
>>>
>>> --
>>> Gabor Csardi <address@hidden>     UNIL DGM
>>>
>>>
>>> _______________________________________________
>>> igraph-help mailing list
>>> address@hidden
>>> http://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>>
>> _______________________________________________
>> igraph-help mailing list
>> address@hidden
>> http://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM