SCC: Tarjan's algorithm for finding strongly connected components

In FinNet: Quickly Build and Manipulate Financial Networks

Tarjan's algorithm for finding strongly connected components

Description

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

Usage

SCC(test_m)

Arguments

test_m

A square adjacency matrix representing the directed network.

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.

Value

A list containing two elements:

• n - number of strongly connected components

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

Author(s)

Settanni,Ettore

Telarico, Fabio Ashtar

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()

FinNet documentation built on Oct. 31, 2024, 5:07 p.m.