kjBuckets is a toothsome, and long in the tooth, Python library that has an elegant graph module I've been putting to good use lately. But I'm always on the lookout for more options. e4graph is a C++ library, written by Jacob Levy & Jean-Claude Wippler, with Python bindings. Possible big wins are persistence and the ability to deal with huge data sets. I'll have to pop this on the top of the kick the tires stack.