C++ Reference: strongly_connected_components

Note: This documentation is automatically generated.

This code computes the strongly connected components of a directed graph, and presents them sorted by reverse topological order.

It implements an efficient version of Tarjan's strongly connected components algorithm published in: Tarjan, R. E. (1972), "Depth-first search and linear graph algorithms", SIAM Journal on Computing.

A description can also be found here: http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

SIMPLE EXAMPLE:

Fill a vector<vector<int>> graph; representing your graph adjacency lists. That is, graph[i] contains the nodes adjacent to node #i. The nodes must be integers in [0, num_nodes). Then just do:

vector<vector<int>> components; FindStronglyConnectedComponents( static_cast<int>(graph.size()), graph, &components);

The nodes of each strongly connected components will be listed in each subvector of components. The components appear in reverse topological order: outgoing arcs from a component will only be towards earlier components.

IMPORTANT: num_nodes will be the number of nodes of the graph. Its type is the type used internally by the algorithm. It is why it is better to convert it to int or even int32_t rather than using size_t which takes 64 bits.

Finds the strongly connected components of a directed graph. It is templated so it can be used in many contexts. See the simple example above for the easiest use case.

The requirement of the different types are:
   - The type NodeIndex must be an integer type representing a node of the
   graph. The nodes must be in [0, num_nodes). It can be unsigned.
   - The type Graph must provide a [] operator such that the following code
   iterates over the adjacency list of the given node:
   for (const NodeIndex head : graph[node]) {}
   - The type SccOutput must implement the function:
   emplace_back(NodeIndex const* begin, NodeIndex const* end);
   It will be called with the connected components of the given graph as they
   are found (In the reverse topological order).

More practical details on the algorithm:

   - It deals properly with self-loop and duplicate nodes.
   - It is really fast! and work in O(nodes + edges).
   - Its memory usage is also bounded by O(nodes + edges) but in practice it
   uses less than the input graph.

Classes
StronglyConnectedComponentsFinder

C++ Reference: strongly_connected_components

Classes