mCRL2

#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 
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 runtime 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.
Worstcase memory use: 5*sizeof(verti) + c.
Definition at line 35 of file SCC_impl.h.

inline 
Definition at line 38 of file SCC_impl.h.
Definition at line 68 of file SCC_impl.h.

inlineprivate 
Definition at line 82 of file SCC_impl.h.

inline 
Definition at line 43 of file SCC_impl.h.
Callback& SCC< Callback >::callback_ 
Definition at line 146 of file SCC_impl.h.
Vertex indices of the current component.
Definition at line 156 of file SCC_impl.h.
const StaticGraph& SCC< Callback >::graph_ 
Definition at line 145 of file SCC_impl.h.
Inorder index and lowest link index of each vertex.
Definition at line 153 of file SCC_impl.h.
Index of next vertex to be labelled by inorder traversal.
Definition at line 150 of file SCC_impl.h.
The depthfirstsearch 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.