Looking For Great Open Source Graph Library
I’m currently looking for good open source graph theory. It needs to support basic algorithms for problems like minimum cost maximum flow. I need a GPL-compatible license.
- In C++, I found that the Boost library has something pretty complete together with Python wrapping. But I hate working with Boost: it is monolithic, the code is obscur (to me) and they require their own build tools instead of the default unix way (./configure; make; make install).
- In Python, I found NetworkX but while it has great plotting facilities, it lacks supports for fancy algorithms.
- In Python, I found kjbuckets which is self-described as “a Python extension module that provides fast set, graph and mapping operations”.
Follow me on twitter!
I’m back to using an aggregator, so when I read the excerpt, I was going to suggest Boost. Strangely, I don’t have anything in my del.icio.us links to answer this question. I dug a little, and found the GTL again, but immediately noticed the strings attached: “Please use your academic address, e.g. .edu, if you have. Otherwise your are classified as a “commercial” user.” Definately not libre software.
LEDA has something too, and you can easily convert from LEDA to Boost: http://www.boost.org/libs/graph/doc/leda_conversion.html
But LEDA isn’t libre software either.
Not sure what you mean by Boost being monolithic, though. Like I mentionned before, it’s designed to be incorporated into the next C++ standard. I can only hope it has weak dependencies.
After digging a little more, I found what might be a good source of info: http://del.icio.us/xamdam/python+graph
and his blog: http://pythonzweb.blogspot.com/
Can you give us an example why Boost doesn’t do it for you?
P.S.: I waited too long I guess before submitting this form, and code a “wrong code” error. I took precautions, and copied my comment before submitting. I got my comment back in the textarea, but the ‘ where escaped with a \ and the comment was cut at the first “. (just letting you know my experience, not trying to beat a dead horse
Comment by Robin — 27/1/2006 @ 0:40
Forgot to mention this one, in the public domain, and recent:
(from README.txt) “This is PADS, a library of Python Algorithms and Data Structures implemented by David Eppstein of the University of California, Irvine”
http://www.ics.uci.edu/~eppstein/PADS/
Never worked with it though.
Comment by Robin — 27/1/2006 @ 0:57
Thanks Robin.
Good find! I should have remembered http://www.ics.uci.edu/~eppstein/PADS/, but an all Python library cannot be fast enough for my needs.
What do I hold against Boost? Have you ever worked with it? I simply dislike it. It is not elegant. It is a giant pile of code, with obscur coding practices.
The fact that it was designed by people who work on the C++ standard is not a very good reference. The C++ standard isn’t exactly sane.
Comment by Daniel Lemire — 27/1/2006 @ 11:33