Tarjan's algorithm for strongly connected components. More...

#include <tpl_dynListStack.H>
#include <tpl_dynSetTree.H>
#include <htlist.H>
#include <tpl_graph_utils.H>
#include <tpl_find_path.H>
#include <ah-errors.H>

Include dependency graph for Tarjan.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Tarjan_Connected_Components< GT, Itor, SA >
	Computes strongly connected components (SCCs) in a directed graph using Tarjan's algorithm. More...

struct	Aleph::Tarjan_Connected_Components< GT, Itor, SA >::Init_Tarjan_Node
	Functor to initialize node metadata for Tarjan traversal. More...

class	Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA >
	Determines if a digraph contains a cycle and constructs it. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Tarjan's algorithm for strongly connected components.

This file implements Tarjan's algorithm for finding strongly connected components (SCCs) in directed graphs. An SCC is a maximal subset of vertices where every vertex is reachable from every other vertex.

Algorithm Overview

Tarjan's algorithm uses a single DFS traversal with a stack to identify SCCs. Each node is assigned:

index: Order of first visit
lowlink: Lowest index reachable from subtree

When lowlink[v] == index[v], v is the root of an SCC.

Key Features

Single DFS pass (optimal)
Returns SCCs in reverse topological order
Can build condensation graph (DAG of SCCs)
Detects cycles in digraphs

Complexity

Operation	Time	Space
Find all SCCs	O(V + E)	O(V)
Build condensation	O(V + E)	O(V + E)

Applications

Detecting cycles in directed graphs
Computing 2-SAT satisfiability
Finding strongly connected components
Building DAG condensation for topological analysis

Usage Example

List_Digraph<Node, Arc> g;
// ... build digraph ...
 
DynList<DynList<Node*>> sccs;
Tarjan_Connected_Components<decltype(g)> tarjan;
tarjan.connected_components(g, sccs);
 
for (auto& scc : sccs) {
  std::cout << "SCC with " << scc.size() << " nodes\n";
}

See also: Kosaraju.H Alternative SCC algorithm (two DFS passes); topological_sort.H Topological ordering for DAGs

Author: Leandro Rabindranath León

Definition in file Tarjan.H.