tarjan_example.C File Reference

Tarjan's Algorithm: Finding Strongly Connected Components. More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <tpl_graph.H>
#include <Tarjan.H>
#include <tclap/CmdLine.h>

Include dependency graph for tarjan_example.C:

Go to the source code of this file.

Typedefs
using	SNode = Graph_Node< string >
using	SArc = Graph_Arc< int >
using	SDigraph = List_Digraph< SNode, SArc >

Functions
SDigraph	build_web_graph ()
	Build a sample web page link graph.
SDigraph	build_module_graph ()
	Build a software module dependency graph.
SDigraph	build_dag ()
	Build a simple graph with no cycles (DAG)
SDigraph::Node *	find_node (SDigraph &g, const string &name)
	Find a node by name.
void	print_graph (SDigraph &g, const string &title)
	Print the graph structure.
void	demo_find_sccs (SDigraph &g, const string &description)
	Demonstrate finding SCCs with Tarjan's algorithm.
void	demo_cycle_detection (SDigraph &g, const string &description)
	Demonstrate cycle detection.
void	demo_web_communities ()
	Demonstrate practical application: web communities.
void	demo_dependency_analysis ()
	Demonstrate practical application: dependency analysis.
void	demo_dag_detection ()
	Demonstrate DAG detection.
int	main (int argc, char *argv[])

Detailed Description

Tarjan's Algorithm: Finding Strongly Connected Components.

This example demonstrates Tarjan's algorithm for finding strongly connected components (SCCs) in directed graphs. Tarjan's algorithm is one of the most efficient algorithms for this problem, using a single DFS pass.

What is a Strongly Connected Component?

A strongly connected component (SCC) is a maximal subset of vertices in a directed graph where:

• Every vertex is reachable from every other vertex in the SCC
• There's a path from any vertex to any other within the SCC

Key insight: In an SCC, you can travel from any vertex to any other vertex (and back).

Example

Graph: A → B → C → A, D → E → D

SCCs:

• {A, B, C} - form a cycle, all reachable from each other
• {D, E} - form a cycle

Note: In undirected graphs, SCCs are just connected components.

Tarjan's Algorithm

How It Works

Tarjan's algorithm uses a single DFS pass with two key values:

• **index[v]**: Order in which vertex v was first visited (discovery time)
• **lowlink[v]**: Smallest index reachable from v (including v itself)

Key Insight

A vertex v is the root of an SCC if and only if:

lowlink[v] == index[v]

This means v cannot reach any vertex discovered earlier, so it's the "entry point" to a new SCC.

Algorithm Steps

Tarjan_SCC(G):
  1. Initialize index = 0, stack = empty
  2. For each unvisited vertex v:
     DFS(v)
 
DFS(v):
  1. Set index[v] = lowlink[v] = current_index++
  2. Push v onto stack, mark as on_stack
  3. For each neighbor w of v:
     If w not visited:
       DFS(w)
       lowlink[v] = min(lowlink[v], lowlink[w])
     Else if w is on_stack:
       lowlink[v] = min(lowlink[v], index[w])
  4. If lowlink[v] == index[v]:
     Pop stack until v, all popped vertices form one SCC

Why It Works

• **lowlink[v]** tracks the earliest vertex reachable from v
• If lowlink[v] == index[v], v cannot reach earlier vertices
• All vertices on stack above v are in the same SCC
• Popping them gives us the complete SCC

Complexity

• Time: O(V + E) - single DFS pass
• Space: O(V) - for stack and arrays

Advantage: More efficient than Kosaraju's (no graph transpose needed)

Comparison with Kosaraju's Algorithm

Aspect	Tarjan's	Kosaraju's
Passes	1 DFS	2 DFS (original + transpose)
Graph transpose	No	Yes (O(V+E) space)
Implementation	More complex	Simpler
Performance	Faster	Slightly slower
Best for	General use	When simplicity preferred

Real-World Applications

Social Networks

• Cohesive groups: Find communities where everyone knows everyone
• Influence analysis: Identify tightly-knit groups
• Recommendation: Suggest friends in same SCC

Web Analysis

• Page clusters: Identify mutually linked web pages
• SEO: Understand website structure
• Crawling: Identify website communities

Compiler Optimization

• Cyclic dependencies: Detect circular dependencies
• Data flow: Analyze variable dependencies
• Dead code: Identify unreachable code

2-SAT Satisfiability

• Boolean formulas: Reduce 2-SAT to SCC finding
• Constraint satisfaction: Solve logical constraints

Deadlock Detection

• Operating systems: Find circular wait conditions
• Database systems: Detect transaction deadlocks
• Resource allocation: Identify circular dependencies

Network Analysis

• Internet routing: Identify network clusters
• Telecommunications: Analyze call patterns

Example: Web Page Links

Pages: Home → About → Contact → Home
       Blog → Archive → Blog
 
SCCs:
- {Home, About, Contact} - circular links
- {Blog, Archive} - circular links

This helps identify website structure and navigation patterns.

Usage

# Run Tarjan's algorithm demo
./tarjan_example
 
# Run specific demos
./tarjan_example --web
./tarjan_example --modules
./tarjan_example --dag
 
# Run all demos (default if no specific demo flags are given)
./tarjan_example --all
 
# Show help
./tarjan_example --help

See also

Tarjan.H Tarjan's algorithm implementation

kosaraju_example.cc Kosaraju's algorithm (alternative)

graph_components_example.C Connected components (undirected)

Author

Leandro Rabindranath León

Definition in file tarjan_example.C.

Typedef Documentation

SArc

using SArc = Graph_Arc<int>

Definition at line 207 of file tarjan_example.C.

SDigraph

using SDigraph = List_Digraph<SNode, SArc>

Definition at line 208 of file tarjan_example.C.

SNode

using SNode = Graph_Node<string>

Definition at line 206 of file tarjan_example.C.

Function Documentation

build_dag()

SDigraph build_dag

(

)

Build a simple graph with no cycles (DAG)

Definition at line 318 of file tarjan_example.C.

Referenced by demo_dag_detection().

build_module_graph()

SDigraph build_module_graph

(

)

Build a software module dependency graph.

Core <--> Utils | | v v DB <--> Cache <--> Logger

API --> Auth --> Session ^ | +---------—+

Definition at line 277 of file tarjan_example.C.

References Aleph::maps().

Referenced by demo_dependency_analysis().

build_web_graph()

SDigraph build_web_graph

(

)

Build a sample web page link graph.

Represents web pages and their hyperlinks:

Homepage <—> About | | v v Products --> Services ^ | | v +------— Contact

Blog <--> Article1 | | v v Article2 <– Article3

Definition at line 228 of file tarjan_example.C.

References Aleph::maps().

Referenced by demo_web_communities().

demo_cycle_detection()

void demo_cycle_detection	(	SDigraph &	g,
		const string &	description
	)

Demonstrate cycle detection.

Definition at line 416 of file tarjan_example.C.

References LocateFunctions< Container, Type >::get_it(), Aleph::maps(), and Aleph::HTList::size().

Referenced by demo_dag_detection(), and demo_dependency_analysis().

demo_dag_detection()

void demo_dag_detection

(

)

Demonstrate DAG detection.

Definition at line 500 of file tarjan_example.C.

References build_dag(), demo_cycle_detection(), demo_find_sccs(), Aleph::maps(), and print_graph().

Referenced by main().

demo_dependency_analysis()

void demo_dependency_analysis

(

)

Demonstrate practical application: dependency analysis.

Definition at line 477 of file tarjan_example.C.

References build_module_graph(), demo_cycle_detection(), demo_find_sccs(), Aleph::maps(), and print_graph().

Referenced by main().

demo_find_sccs()

void demo_find_sccs	(	SDigraph &	g,
		const string &	description
	)

Demonstrate finding SCCs with Tarjan's algorithm.

Definition at line 378 of file tarjan_example.C.

References LocateFunctions< Container, Type >::get_it(), Aleph::maps(), and Aleph::HTList::size().

Referenced by demo_dag_detection(), demo_dependency_analysis(), and demo_web_communities().

demo_web_communities()

void demo_web_communities

(

)

Demonstrate practical application: web communities.

Definition at line 454 of file tarjan_example.C.

References build_web_graph(), demo_find_sccs(), Aleph::maps(), and print_graph().

Referenced by main().

find_node()

SDigraph::Node * find_node	(	SDigraph &	g,
		const string &	name
	)

Find a node by name.

Definition at line 340 of file tarjan_example.C.

main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 517 of file tarjan_example.C.

References demo_dag_detection(), demo_dependency_analysis(), demo_web_communities(), and Aleph::maps().

print_graph()

void print_graph	(	SDigraph &	g,
		const string &	title
	)

Print the graph structure.

Definition at line 351 of file tarjan_example.C.

References Aleph::maps().

Referenced by demo_dag_detection(), demo_dependency_analysis(), and demo_web_communities().