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

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. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax