Re: [igraph] graph representation in memory

[E. Navarro]

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
>