Python Graph Library

I would like to plug my own graph python library: graph-tool.

It is very fast, since it is implemented in C++ with the Boost Graph Library, and it contains lots of algorithms and extensive documentation.

Have you looked at python-graph? I haven't used it myself, but the project page looks promising.

There are two excellent choices:

NetworkX

and

igraph

I like NetworkX, but I read good things about igraph as well. I routinely use NetworkX with graphs with 1 million nodes with no problem (it's about double the overhead of a dict of size V + E)

If you want a feature comparison, see this from the Networkx-discuss list

Feature comparison thread

Also, you might want to take a look at NetworkX