scc.h
Go to the documentation of this file.
00001 #ifndef SCC_H
00002 #define SCC_H
00003 
00004 /*
00005    This implements Tarjan's linear-time algorithm for finding the maximal
00006    strongly connected components. It takes time proportional to the sum
00007    of the number of vertices and arcs.
00008 
00009    Instantiate class SCC with a graph represented as a vector of vectors,
00010    where graph[i] is the vector of successors of vertex i.
00011 
00012    Method get_result() returns a vector of strongly connected components,
00013    each of which is a vector of vertices (ints).
00014    This is a partitioning of all vertices where each SCC is a maximal subset
00015    such that each node in an SCC is reachable from all other nodes in the SCC.
00016    Note that the derived graph where each SCC is a single "supernode" is
00017    necessarily acyclic. The SCCs returned by get_result() are in a topological
00018    sort order with regard to this derived DAG.
00019    */
00020 
00021 #include <vector>
00022 using namespace std;
00023 
00024 class SCC {
00025     const vector<vector<int> > &graph;
00026 
00027     // The following three are indexed by vertex number.
00028     vector<int> dfs_numbers;
00029     vector<int> dfs_minima;
00030     vector<int> stack_indices;
00031 
00032     vector<int> stack; // This is indexed by the level of recursion.
00033     vector<vector<int> > sccs;
00034 
00035     int current_dfs_number;
00036 
00037     void dfs(int vertex);
00038     public:
00039     SCC(const vector<vector<int> > &theGraph) : graph(theGraph) {}
00040     vector<vector<int> > get_result();
00041 };
00042 #endif


tfd_modules
Author(s): Maintained by Christian Dornhege (see AUTHORS file).
autogenerated on Mon Oct 6 2014 07:52:06