Graph theory in python

Question

I was wondering how people deal with graph theory in python? How is a graph stored? Are there libraries for this?

For example how would I input a graph and then find its Chromatic polynomial? Or its girth? Or the number of unique spanning trees? How about problems that involve edge weight like salesman problems?

I don't need all of these answered, I'm just looking for a method or tool set that will be able to help me approach solve problems like this.

Thanks, Dan

Answer 1

Hi, this might help - http://wiki.python.org/moin/PythonGraphApi. From the page and quick lookaround, python-graph seems pretty mature.

• 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
• 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)
• Shortest path search (Dijkstra's algorithm)
• Shortest path search (Bellman-Ford algorithm)
• Topological sorting
• Transitive edge identification

Answer 2

networkx

Features

Standard graph-theoretic and statistical physics functions
Easy exchange of network algorithms between applications, disciplines, and platforms
Many classic graphs and synthetic networks
Nodes and edges can be "anything" (e.g. time-series, text, images, XML records)
Exploits existing code from high-quality legacy software in C, C++, Fortran, etc.
Open source (encourages community input)
Unit-tested

Additional benefits from Python

Fast prototyping of new algorithms
Easy to teach
Multi-platform
Allows easy access to almost any database

Answer 3

You can also have a look at NetworkX which has pretty advanced algorithms & drawing capability for graphs !

From the web site :

Features

* Standard graph-theoretic and statistical physics functions
* Easy exchange of network algorithms between applications, disciplines, and platforms
* Many classic graphs and synthetic networks
* Nodes and edges can be "anything" (e.g. time-series, text, images, XML records)
* Exploits existing code from high-quality legacy software in C, C++, Fortran, etc.
* Open source (encourages community input)
* Unit-tested

Answer 4

There's also igraph, which is a library primarily implemented in C (hence it is usually faster than pure Python solutions), with a higher level interface to Python. Therefore, you get the best of both worlds: the speed of a pure C solution and all the usual benefits (fast prototyping etc.) of Python.

An example with igraph:

>>> from igraph import Graph
>>> g = Graph.Famous("petersen")
>>> g.girth()
5

Disclaimer: I'm a co-developer of igraph, so I'm not totally impartial :)