Re: [igraph] A few questions

[Csardi Gabor]

On Thu, Aug 09, 2007 at 01:15:15PM +0200, Tamas Nepusz wrote:
> > I'm trying to decide between using igraph and boost graph. I
> > saw a comparison [1] of igraph (sna) against several other
> > graphing solutions, and was wondering if the benchmarks could
> > be updated to include boost. Would be good information to
> > have on the main web page.
> I'll keep it on my TODO list. The reason why I didn't include BOOST in
> the comparison in the paper you mentioned is that I had to finish that
> paper in about two days and I had no previous experience in BOOST - it
> would have taken a whole lot of time :) Personally I expect igraph to
> be faster than BOOST in most of the cases, since the former is written
> in C and the latter in C++ with lots of templating stuff, but of
> course this has to be benchmarked thoroughly. If there is anyone out
> there among the members of this mailing list who is more experienced
> in BOOST than me, it would be great if he/she could sketch up some
> quick benchmarks for BOOST regarding (for instance) diameter
> calculation, PageRank, closeness centrality, edge betweenness or
> whatever BOOST supports.

Personally i don't expect that Boost would be much slower than igraph,
especially that most igraph functions were never profiled. This 
also means that there are reserves in igraph, ie. much could be gained
by profiling the functions.

Boost templates are interpreted at compile time, that make programs 
actually quite fast. They are also much more complicated though.
So i would advise to go with boost only if you're an experienced c++
programmer.

> > Also, I see in layout.c that igraph_layout_springs is not
> > yet implemented. Would it be possible to use some of the
> > ideas from graphopt [2] (it's c++)?
> I think yes, sooner or later :) One of the reasons why the springs
> layout is not implemented yet is that we did not really need it so
> far, the Fruchterman-Reingold and Kamada-Kawai layouts (based on the
> same principles) were pretty satisfactory, and for very large graphs
> (where these two layouts are way too slow) there is the grid-based
> Fruchterman-Reingold layout and the Large Graph Layout (see
> http://lgl.sourceforge.net/), both implemented in igraph.

Yes, although the layout for large graphs are not very well tested
and it is not clear to me how to give the parameters to get 
good results.

graphopt looks very good, after taking a look at the source 
it seems that the actual layout generation code can be extracted
easily.

> > Finally, are there plans to add support for ogdl [3]?
> I don't think support for this format will be included directly in the
> trunk in the near future (unless someone sends us a patch which does
> not add dependence on libogdl - we are trying to keep library
> dependencies to a minimum). However, using the code from libogdl, I
> think it would be easy to sketch up a converter from OGDL to a more
> specific graph format - the OGDL parsing is done by libogdl, and by
> conducting a BFS or DFS traversal of the resulting Graph structure
> (see http://ogdl.sourceforge.net/api/c/graph_8c.html), one can easily
> transform it to an edge list or something similar. Labeled edge lists
> can then be imported by igraph using igraph_read_graph_edgelist().

Hmmm, read_graph_edgelist() does not support labels, but there are
other simple formats which do. Actually the odgl format seems to be
very simple, so i think it is fairly easy to write a parser for
it independently of libodgl.

So, all these suggestions could be done fairly easily, which does not 
mean that we will do it soon because there are many important bits 
missing from igraph and we need to work on these.

In general it helps if you keep pestering us,
and especially if you tell us how you would use these features and
igraph in general. Providing your real name might also help a bit,
personally i'm more motivated to help real people.

Best,
Gabor

ps. please consider joining the list, otherwise your messages will
have delays, even a couple of days are possible if i'm offline.

> -- 
> Tamas
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help

-- 
Csardi Gabor <address@hidden>    MTA RMKI, ELTE TTK