python-graph 1.8.2

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.

The code is appropriately documented and API reference is generated automatically by epydoc.

Comments, bug reports and suggestions are welcome.

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