Strongly connected components of a directed graph. (Python)

2013-04-03T19:30:32-07:00

Python recipe 578507 by Mark Dickinson (connected, directed, graph, strong, tarjan). Revision 3.

Two linear-time algorithms for finding the strongly connected components of a directed graph. strongly_connected_components_tree implements (a variant of) Tarjan's well-known algorithm for finding strongly connected components, while strongly_connected_components_path implements a path-based algorithm due (in this form) to Gabow.

Edit: I added an iterative function strongly_connected_components_iterative; this is a direct conversion of strongly_connected_components_path into iterative form. It's therefore safe to use on high-depth graphs, without risk of running into Python's recursion limit.

Simple graph algorithms with a modular design (Python)

2011-04-21T13:40:32-07:00

Python recipe 577668 by jimmy2times (algorithms, breadth, depth, directed, first, graph, object, oriented, python, search, theory, undirected, visit). Revision 7.

The purpose of this recipe is to look at algorithmic graph theory from an object-oriented perspective.

A graph is built on top of a dictionary indexed by its vertices, each item being the set of neighbours of the key vertex. This ensures that iterating through the neighbours of a vertex is still efficient in sparse graphs (as with adjacency lists) while at the same time checking for adjacency is expected constant-time (as with the adjacency matrix).

Any valid class of graph must implement the interface defined by AbstractGraph.

A generic search algorithm takes as input a graph, source and target vertices and a queue. A queue must implement the methods Q.get(), Q.put() and Q.empty() in such a way to get the desired order in visiting the vertices.

Given this pattern, breadth-first and depth-first search are essentially defined by the corresponding expansion policies: the first one uses an actual FIFO queue, the second one a LIFO queue (or stack).

Popular Python recipes tagged "directed"

Strongly connected components of a directed graph. (Python)

Simple graph algorithms with a modular design (Python)