SCC2 function

Tarjan's algorithm for finding strongly connected components in C++

This function performs a depth-first search (DFS) on a directed graph to identify strongly connected components (SCCs) and their size

SCC2(x)

Arguments

• x: A square adjacency matrix representing the directed network.

Returns

A list containing two elements:

• n - number of strongly connected components
• sizes - size of each strongly connected component, in order of discovery

Details

This function is a modified version of the C++ implementation of Tarjan's algorithm for finding strongly connected components in directed graphs made available by the webiste Geeks for Geeks (see References).

The function consists of several internal steps:

1. Node Labeling - All nodes are labeled with two-digit names for clarity in referencing.
2. Successor List Creation - For each node, lists of direct successors are compiled.
3. Utilization Table Setup - A table is set up for tracking exploration details such as depth and backtracking information.
4. Main DFS Loop - The core loop where DFS occurs, including node visitation and backtracking logic to determine SCCs.
5. Stack Management - Nodes are managed in a stack to keep track of the current path of exploration and to facilitate backtracking.
6. SCC Identification - Upon finishing exploration of an SCC, it is identified and nodes are popped from the stack.

References

Geeks for Geeks. ‘Strongly Connected Components’. C++, 17 January 2024. https://www.geeksforgeeks.org/strongly-connected-components/.

See Also

Other SCC finders: SCC()

Author(s)