tarjan.h File Reference

Implements Tarjan's algorithm for finding strongly connected components (SCCs) in a directed graph. More...

#include <functional>
#include <map>
#include <stack>
#include "GraphLib/internal/concepts.h"

Go to the source code of this file.

Functions
template<Internal::valid_directed_graph_type G>
std::vector< std::vector< typename G::id_type > >	GraphLib::tarjan (const G &graph)
	Finds all strongly connected components (SCCs) in a directed graph using Tarjan's algorithm.

Detailed Description

Implements Tarjan's algorithm for finding strongly connected components (SCCs) in a directed graph.

Provides a templated function that identifies all strongly connected components using a depth-first search with low-link values to efficiently detect SCC roots.

Definition in file tarjan.h.