python-graph by Pedro Matiello.
From the webpage:
python-graph is a library for working with graphs in Python.
This software provides a suitable data structure for representing graphs and a whole set of important algorithms.
…..
Provided features and algorithms:
- Support for directed, undirected, weighted and non-weighted graphs
- Support for hypergraphs
- Canonical operations
- XML import and export
- DOT-Language import and export (for usage with Graphviz)
- Random graph generation
- Accessibility (transitive closure)
- Breadth-first search
- Critical path algorithm
- Cut-vertex and cut-edge identification
- Cycle detection
- Depth-first search
- Gomory-Hu cut-tree algorithm
- Heuristic search (A* algorithm)
- Identification of connected components
- Maximum-flow / Minimum-cut (Edmonds-Karp algorithm)
- Minimum spanning tree (Prim's algorithm)
- Mutual-accessibility (strongly connected components)
- Pagerank algorithm
- Shortest path search (Dijkstra's algorithm)
- Shortest path search (Bellman-Ford algorithm)
- Topological sorting
- Transitive edge identification
Python package to help you explore graphs and algorithms on graphs.