skip to navigation
skip to content

python-graph 1.8.2

A library for working with graphs in Python

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