SCC2: Tarjan's algorithm for finding strongly connected components...

In FinNet: Quickly Build and Manipulate Financial Networks

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

Description

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

Usage

SCC2(x)

Arguments

x	A square adjacency matrix representing the directed network.

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.

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)

Geeks for Geeks

Telarico, Fabio Ashtar

References

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

See Also

Other SCC finders: SCC()

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