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

Daniel Lemire, "Looking For Great Open Source Graph Library," in Daniel Lemire's blog, January 26, 2006.

Published by

Daniel Lemire

A computer science professor at the University of Quebec (TELUQ).

3 thoughts on “Looking For Great Open Source Graph Library”

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

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

Leave a Reply

Your email address will not be published.

You may subscribe to this blog by email.