SCC function

Tarjan's algorithm for finding strongly connected components

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

SCC(test_m)

Arguments

• test_m: 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 R implementation of Tarjan's algorithm for finding strongly connected components in directed graphs by Ettore Settanni at the University of Cambridge (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

Settanni, Ettore. ‘RtarD - Find Strongly Connected Components in a Digraph Using R’. R, 15 November 2021. https://github.com/Dr-Eti/RtarD-Tarjans_DFS_in_R.

See Also

Other SCC finders: SCC2()

Author(s)