kosaraju.H File Reference

Kosaraju's algorithm for finding strongly connected components. More...

#include <tpl_graph_utils.H>

Include dependency graph for kosaraju.H:

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

Go to the source code of this file.

Classes
struct	Aleph::Kosaraju_Connected_Components< GT >
	Functor wrapper for Kosaraju's algorithm. More...

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

Functions
template<class GT >
static void	Aleph::__dfp_phase1 (const GT &g, typename GT::Node *p, DynArray< typename GT::Node * > &df)
	Depth-first search that computes finish times in postorder (Phase 1).
template<class GT >
static void	Aleph::__dfp_phase2_subgraph (const GT &g, typename GT::Node *p, GT &blk, const int &color)
	DFS on transposed graph that builds an SCC subgraph (Phase 2).
template<class GT >
static void	Aleph::__dfp_phase2_list (const GT &g, typename GT::Node *p, DynList< typename GT::Node * > &list)
	DFS on transposed graph that builds an SCC node list (Phase 2).
template<class GT >
void	Aleph::kosaraju_connected_components (const GT &g, DynList< GT > &blk_list, DynList< typename GT::Arc * > &arc_list)
	Compute strongly connected components using Kosaraju's algorithm.
template<class GT >
DynList< DynList< typename GT::Node * > >	Aleph::kosaraju_connected_components (const GT &g)
	Compute strongly connected components as lists of nodes.
template<class GT >
size_t	Aleph::kosaraju_scc_count (const GT &g)
	Count the number of strongly connected components.
template<class GT >
bool	Aleph::is_strongly_connected (const GT &g)
	Check if a directed graph is strongly connected.

Detailed Description

Kosaraju's algorithm for finding strongly connected components.

This file implements Kosaraju's algorithm for computing the strongly connected components (SCCs) of a directed graph. The algorithm performs two depth-first searches: one on the original graph to compute finish times, and one on the transposed graph in decreasing order of finish times to identify the SCCs.

Time complexity: O(V + E) Space complexity: O(V + E) for the transposed graph

See also

Tarjan.H for an alternative SCC algorithm that uses only one DFS

Author

Leandro Rabindranath León

Definition in file kosaraju.H.