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

[Gábor Csárdi]

Emmanuel,

On Wed, Dec 3, 2008 at 1:54 PM, Manu <address@hidden> wrote:
> 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...

Now that I think about it, it will break the interfaces completely,
since the conversion functions (i.e. between C and R) use the igraph_t
directly. :(
It *might* not break the Python interface, I think that uses just an
external pointer for an igraph graph.

> but by concentrating first on useful functions and
> interfaces (for use...) it looks possible !

Everything is possible. The question is whether it is worth....

> 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...

Not really. At the C level, the attributes are passed to functions as
standard arguments, the functions do not query the attributes at all.
(Except for the ones that read/write graphs in different formats.)

Again, the thing is, the igraph functions were written with the idea,
that O(|V|) and O(|E|) things fit into the memory.....

Gabor

> 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
>>
>



-- 
Gabor Csardi <address@hidden>     UNIL DGM