strongly_connected_components.h File Reference

#include <limits>
#include <vector>
#include "absl/log/check.h"
#include "absl/types/span.h"

Go to the source code of this file.

Classes
struct	SccCounterOutput< NodeIndex >
class	StronglyConnectedComponentsFinder< NodeIndex, Graph, SccOutput >

Functions
template<typename NodeIndex , typename Graph , typename SccOutput >
void	FindStronglyConnectedComponents (const NodeIndex num_nodes, const Graph &graph, SccOutput *components)
	Simple wrapper function for most usage.

Function Documentation

FindStronglyConnectedComponents()

template<typename NodeIndex , typename Graph , typename SccOutput >

void FindStronglyConnectedComponents	(	NodeIndex	num_nodes,
		const Graph &	graph,
		SccOutput *	components )

Simple wrapper function for most usage.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. 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.

Definition at line 216 of file strongly_connected_components.h.