You should add graph-tool to the python list. It is very complete, and it is implemented in C++, with the Boost Graph Library, making it orders of magnitude faster than python-only alternatives, such as NetworkX.
Disclaimer: I’m the author of graph-tool. 🙂