Re: [igraph] about reimplement igraph C basic interface using DB

[Gábor Csárdi]

Hi Emmanuel,

some points.
1) I did a similar thing many years ago as a proof of concept with a
PostgreSQL database. The code is here:
http://bazaar.launchpad.net/~igraph/igraph/0.6-main/revision/11
But this was really just a proof of concept, and igraph was pretty
small back then.

2) The igraph layers help you in general to do this, but there some
exceptions, e.g. some functions in the R interface actually make use
of the underlying data representation. It is just a couple of
functions, all of them are in the iterators.R file.

3) Some C functions convert the igraph_t data structure to an
adjacency list for efficiency. This completely messes up things, since
these are stored in memory and have about the same size, as the
igraph_t object. All these functions would need an update, or at least
the linear ones, because you cannot really calculate anything
quadratic on graphs that do not fit into the memory, anyway.

4) It is not clear how to do the attributes. Each interface (R,
Python, C) has its own way of handling the attributes. You cannot
easily make all of them use a SQLite database instead. You would need
to add SQLite support for attributes one by one to each interface. Of
course if you just want to support one language, then it is simpler.

5) I am not convinced that igraph can be used efficiently for graphs
that do not fit into the memory. You would really need to design the
library with this in mind and this was never the case with igraph.
Instead, we assume that just inspecting the igraph_t data structure is
a cheap operation. This is clearly not true if it is in a database.

In summary, it might be a lot of work to make this extension
_properly_. If you don't want to do it properly, e.g. you don't mind
screwing up some functions in the R interface, and you just want to
make a couple of algorithms work on your big graphs, that is easier.
Of course we can help you to find your way through the igraph
internals.

Best,
Gabor

On Mon, Dec 1, 2008 at 11:57 PM, E. Navarro <address@hidden> wrote:
> Hi !
>
> I'm doing some research on really large graphs, -part of- the web's
> hyperlink graph for instance.
> This graphs generally doesn't fit into memory.
>
> As I seen igraph is well layered, my idea is "simply" to reimplement
> iGraph basic interface to make it use a DB (SQLite certanly).
> so I was wondering :
> - have you already think about such an idea ?
> - is there major technical issue I didn't see ?
> - any advice ?
>
> A issue I was thinking on, is about attributes, especially weights.
> If I load it in into the memory, I'm back to the initial problem :
> it's quite the same than load the entire graph...
> I seen the C Attribute Handler Interface, could it be a simple solution ?
>
> Thanks a lot,
> Emmanuel Navarro
>
> PS: I known neo4j, but it's really not conventional graph library...
> And I'm interest on all algorithms implements into iGraph.
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM