Comprehensive example of Kosaraju's algorithm for SCCs. More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cstring>
#include <tpl_graph.H>
#include <kosaraju.H>
#include <Tarjan.H>

Include dependency graph for kosaraju_example.cc:

Typedefs
using	Graph = List_Digraph< Graph_Node< string >, Graph_Arc< int > >

using	Node = Graph::Node

using	Arc = Graph::Arc

Functions
Node *	find_node (Graph &g, const string &name)

void	print_graph (Graph &g)

void	example_basic_sccs ()

void	example_lightweight_version ()

void	example_strongly_connected ()

void	example_dag ()

void	example_comparison_tarjan ()

void	example_applications ()

static void	usage (const char *prog)

static bool	has_flag (int argc, char argv[], const char flag)

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

Detailed Description

Comprehensive example of Kosaraju's algorithm for SCCs.

This example demonstrates Kosaraju's algorithm for finding Strongly Connected Components (SCCs) in a directed graph. Kosaraju's algorithm is conceptually simpler than Tarjan's, using two DFS passes instead of one, but requiring a graph transpose.

What is a Strongly Connected Component?

In a directed graph, a strongly connected component (SCC) is a maximal set of vertices such that there is a path from every vertex to every other vertex in the set.

Key property: 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
{D, E} - form a cycle

Kosaraju's Algorithm

Overview

Kosaraju's algorithm works in two phases:

Phase 1: Compute Finish Times

Run DFS on the original graph G
Record nodes in order they finish (postorder)
Store finish times

Key: We record when DFS finishes exploring a vertex (post-order).

Phase 2: Find SCCs

Create transposed graph G^T (reverse all edges)
Process nodes in DECREASING order of finish time
Run DFS on G^T starting from highest finish time
Each DFS tree found is one SCC

Key: Process in reverse finish order, on reversed graph.

Why Does It Work?

Key Insight

If vertex u can reach vertex v in graph G, then v can reach u in the transposed graph G^T (where all edges are reversed).

Why Reverse Finish Order?

By processing vertices in decreasing finish order:

We start with vertices that finished LAST in Phase 1
These are "sink" vertices (end of paths)
In G^T, they become "source" vertices
DFS from them only reaches vertices in the same SCC

Why Transpose?

In G: If u → v, then u can reach v
In G^T: If v → u (reversed), then v can reach u
Together: u and v can reach each other ⟺ same SCC

Algorithm Pseudocode

Kosaraju_SCC(G):
  // Phase 1: Compute finish times
  stack = empty
  visited = all false
  For each vertex v in G:
    If not visited[v]:
      DFS_Phase1(v, G, visited, stack)
 
  // Phase 2: Find SCCs on transposed graph
  G_transpose = transpose(G)
  visited = all false
  While stack not empty:
    v = stack.pop()
    If not visited[v]:
      SCC = DFS_Phase2(v, G_transpose, visited)
      Output SCC
 
DFS_Phase1(v, G, visited, stack):
  visited[v] = true
  For each neighbor w of v in G:
    If not visited[w]:
      DFS_Phase1(w, G, visited, stack)
  stack.push(v)  // Post-order: push after exploring
 
DFS_Phase2(v, G_T, visited):
  visited[v] = true
  SCC = {v}
  For each neighbor w of v in G_T:
    If not visited[w]:
      SCC += DFS_Phase2(w, G_T, visited)
  Return SCC

Complexity

Time: O(V + E) - two DFS passes
Space: O(V + E) - for transposed graph

Note: Tarjan's algorithm is more space-efficient (no transpose needed)

Comparison with Tarjan's Algorithm

Aspect	Kosaraju's	Tarjan's
Passes	2 DFS	1 DFS
Graph transpose	Required	Not needed
Space	O(V+E) for transpose	O(V)
Implementation	Simpler	More complex
Performance	Slightly slower	Faster
Best for	Learning, simplicity	Production, efficiency

Applications

2-SAT Satisfiability

Boolean formulas: Reduce 2-SAT to SCC finding
Constraint satisfaction: Solve logical constraints
Circuit design: Verify satisfiability

Dependency Analysis

Circular dependencies: Find cycles in dependency graphs
Build systems: Detect circular build dependencies
Package managers: Find circular package dependencies

Social Networks

Communities: Find tightly-knit groups
Influence: Identify influential clusters
Recommendations: Suggest connections in same SCC

Compiler Optimization

Data flow: Analyze variable dependencies
Dead code: Identify unreachable code
Optimization: Find optimization opportunities

Web Crawling

Site clusters: Identify website communities
Link analysis: Understand web structure
SEO: Analyze site connectivity

Example: Dependency Graph

Modules: A → B → C → A  (circular!)
         D → E → D      (circular!)
         F → G
 
SCCs:
- {A, B, C} - circular dependency
- {D, E} - circular dependency
- {F} - single module
- {G} - single module

This helps identify problematic circular dependencies.

Usage

# Run Kosaraju's algorithm demo
./kosaraju_example
 
# Compare with Tarjan's
./kosaraju_example --compare
 
# Show help
./kosaraju_example --help

See also: kosaraju.H Kosaraju's algorithm implementation; tarjan_example.C Tarjan's algorithm (more efficient); graph_components_example.C Connected components (undirected)

Author: Leandro Rabindranath León

Definition in file kosaraju_example.cc.

Typedef Documentation

◆ Arc

using Arc = Graph::Arc

Definition at line 243 of file kosaraju_example.cc.

◆ Graph

using Graph = List_Digraph<Graph_Node<string>, Graph_Arc<int> >

Definition at line 241 of file kosaraju_example.cc.

◆ Node

using Node = Graph::Node

Definition at line 242 of file kosaraju_example.cc.

Function Documentation

◆ example_applications()

void example_applications ( )

Definition at line 560 of file kosaraju_example.cc.

◆ example_basic_sccs()

void example_basic_sccs ( )

Definition at line 283 of file kosaraju_example.cc.

References GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::kosaraju_connected_components(), Aleph::maps(), NODE_COOKIE, print_graph(), and Aleph::HTList::size().

◆ example_comparison_tarjan()

void example_comparison_tarjan ( )

Definition at line 521 of file kosaraju_example.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

◆ example_dag()

void example_dag ( )

Definition at line 476 of file kosaraju_example.cc.

References GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::kosaraju_connected_components(), Aleph::maps(), print_graph(), and Aleph::HTList::size().

◆ example_lightweight_version()

void example_lightweight_version ( )

Definition at line 373 of file kosaraju_example.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::kosaraju_connected_components(), Aleph::maps(), and Aleph::HTList::size().

◆ example_strongly_connected()

void example_strongly_connected ( )

Definition at line 425 of file kosaraju_example.cc.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), Aleph::kosaraju_connected_components(), Aleph::maps(), print_graph(), and Aleph::HTList::size().

◆ find_node()

Node * find_node	(	Graph &	g,
		const string &	name
	)

Definition at line 249 of file kosaraju_example.cc.

References GraphCommon< GT, Node, Arc >::get_node_it().

◆ has_flag()

static bool has_flag	(	int	argc,
		char *	argv[],
		const char *	flag
	)

static

Definition at line 579 of file kosaraju_example.cc.

References Aleph::maps().

◆ main()

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

Definition at line 587 of file kosaraju_example.cc.

◆ print_graph()

void print_graph ( Graph & g )

Definition at line 257 of file kosaraju_example.cc.

References GraphCommon< GT, Node, Arc >::get_node_it(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_out_it(), GraphCommon< GT, Node, Arc >::get_tgt_node(), and Aleph::maps().

Referenced by example_basic_sccs(), example_dag(), and example_strongly_connected().

◆ usage()

static void usage ( const char * prog )