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

[Manu]

Thank you for answering so quickly,
lot of useful information !

So a sqlite based basic interface will break a lot of function in
upper layers... but by concentrating first on useful functions and
interfaces (for use...) it looks possible !

For attributes, make each high level interface ask the database sound
to be the simpler solution. It's ok for attributes like color, label,
... but I wonder about weights. I plan to writte some algothms in C
layer (but calls from Python) witch need to known weights for all
edges (a bit like igraph_maxflow_value need capacity). So to be
efficient, this C functions had to query the database directly...
A proper way to do so is to had weighted graph support to the basic
layer... I can do it just for my -free- igraph hack, but I'm wondering
if you are thinking about that in -official- igraph ?

An other question, I fear to "reinventing the wheel" (I'm not sure if
it's said in English, we use it in French...). I searched on the web
about database or disk based graph library, but except neo4j, I didn't
find anything. Some of you heard about something like that ?

For information, this hack will certainly be a project for engineer
school students.

Thanks again,
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
>