SCC< Callback > Class Template Reference

#include <SCC_impl.h>

Public Member Functions
	SCC (const StaticGraph &graph, Callback &callback)
int	run ()

Public Attributes
const StaticGraph &	graph_
Callback &	callback_

Private Member Functions
void	add (verti v)
int	dfs ()

Private Attributes
verti	next_index
	Index of next vertex to be labelled by inorder traversal.
std::vector< std::pair< verti, verti > >	info
	Inorder index and lowest link index of each vertex.
std::vector< verti >	component
	Vertex indices of the current component.
std::vector< std::pair< verti, verti > >	stack

Detailed Description

template<class Callback>
class SCC< Callback >

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

Visits each vertex and edge in the graph once, so it has a run-time complexity O(V + E). For each vertex, two items are stored: the vertex index (which denotes the order in which vertices are visited) and a lowest link index, which gives the lowest index of a vertex that is reachable from the current vertex.

When a vertex has not yet been visited, its index is set to NO_VERTEX. Furthermore, the lowest link index is set to NO_VERTEX if the vertex is not part of the current component.

Worst-case memory use: 5*sizeof(verti) + c.

Definition at line 35 of file SCC_impl.h.

Constructor & Destructor Documentation

SCC()

template<class Callback >

SCC< Callback >::SCC ( const StaticGraph &  graph, Callback &  callback  )

inline

Definition at line 38 of file SCC_impl.h.

Member Function Documentation

add()

template<class Callback >

void SCC< Callback >::add ( verti  v )

inlineprivate

Definition at line 68 of file SCC_impl.h.

dfs()

template<class Callback >

int SCC< Callback >::dfs ( )

inlineprivate

Definition at line 82 of file SCC_impl.h.

run()

template<class Callback >

int SCC< Callback >::run ( )

inline

Definition at line 43 of file SCC_impl.h.

Member Data Documentation

callback_

template<class Callback >

Callback& SCC< Callback >::callback_

Definition at line 146 of file SCC_impl.h.

component

template<class Callback >

std::vector<verti> SCC< Callback >::component

private

Vertex indices of the current component.

Definition at line 156 of file SCC_impl.h.

graph_

template<class Callback >

const StaticGraph& SCC< Callback >::graph_

Definition at line 145 of file SCC_impl.h.

info

template<class Callback >

std::vector<std::pair<verti, verti> > SCC< Callback >::info

private

Inorder index and lowest link index of each vertex.

Definition at line 153 of file SCC_impl.h.

next_index

template<class Callback >

verti SCC< Callback >::next_index

private

Index of next vertex to be labelled by inorder traversal.

Definition at line 150 of file SCC_impl.h.

stack

template<class Callback >

std::vector< std::pair< verti, verti > > SCC< Callback >::stack

private

The depth-first-search stack.

Each entry consists of a vertex index and an index into its successor list. When a new unvisited vertex v is discovered, a pair (v, 0) is appened at the end of the stack. The top element is popped off the stack when its successor index points to the end of the successor list.

Definition at line 165 of file SCC_impl.h.

---

The documentation for this class was generated from the following file:

• pg/include/mcrl2/pg/SCC_impl.h