scc.cpp
Go to the documentation of this file.
00001 #include "scc.h"
00002 #include <algorithm>
00003 #include <vector>
00004 using namespace std;
00005 
00006 vector<vector<int> > SCC::get_result() {
00007     int node_count = graph.size();
00008     dfs_numbers.resize(node_count, -1);
00009     dfs_minima.resize(node_count, -1);
00010     stack_indices.resize(node_count, -1);
00011     stack.reserve(node_count);
00012     current_dfs_number = 0;
00013 
00014     for(int i = 0; i < node_count; i++)
00015         if(dfs_numbers[i] == -1)
00016             dfs(i);
00017 
00018     reverse(sccs.begin(), sccs.end());
00019     return sccs;
00020 }
00021 
00022 void SCC::dfs(int vertex) {
00023     int vertex_dfs_number = current_dfs_number++;
00024     dfs_numbers[vertex] = dfs_minima[vertex] = vertex_dfs_number;
00025     stack_indices[vertex] = stack.size();
00026     stack.push_back(vertex);
00027 
00028     const vector<int> &successors = graph[vertex];
00029     for(int i = 0; i < successors.size(); i++) {
00030         int succ = successors[i];
00031         int succ_dfs_number = dfs_numbers[succ];
00032         if(succ_dfs_number == -1) {
00033             dfs(succ);
00034             dfs_minima[vertex] = min(dfs_minima[vertex], dfs_minima[succ]);
00035         } else if(succ_dfs_number < vertex_dfs_number && stack_indices[succ] != -1) {
00036             dfs_minima[vertex] = min(dfs_minima[vertex], succ_dfs_number);
00037         }
00038     }
00039 
00040     if(dfs_minima[vertex] == vertex_dfs_number) {
00041         int stack_index = stack_indices[vertex];
00042         vector<int> scc;
00043         for(int i = stack_index; i < stack.size(); i++) {
00044             scc.push_back(stack[i]);
00045             stack_indices[stack[i]] = -1;
00046         }
00047         stack.erase(stack.begin() + stack_index, stack.end());
00048         sccs.push_back(scc);
00049     }
00050 }
00051 
00052 /*
00053 #include <iostream>
00054 using namespace std;
00055 
00056 int main() {
00057 
00058 #if 0
00059 int n0[] = {1, -1};
00060 int n1[] = {-1};
00061 int n2[] = {3, 4, -1};
00062 int n3[] = {2, 4, -1};
00063 int n4[] = {0, 3, -1};
00064 int *all_nodes[] = {n0, n1, n2, n3, n4, 0};
00065 #endif
00066 
00067 int n0[] = {-1};
00068 int n1[] = {3, -1};
00069 int n2[] = {4, -1};
00070 int n3[] = {8, -1};
00071 int n4[] = {0, 7, -1};
00072 int n5[] = {4, -1};
00073 int n6[] = {5, 8, -1};
00074 int n7[] = {2, 6, -1};
00075 int n8[] = {1, -1};
00076 int *all_nodes[] = {n0, n1, n2, n3, n4, n5, n6, n7, n8, 0};
00077 
00078 vector<vector<int> > graph;
00079 for(int i = 0; all_nodes[i] != 0; i++) {
00080 vector<int> successors;
00081 for(int j = 0; all_nodes[i][j] != -1; j++)
00082 successors.push_back(all_nodes[i][j]);
00083 graph.push_back(successors);
00084 }
00085 
00086 vector<vector<int> > sccs = SCC(graph).get_result();
00087 for(int i = 0; i < sccs.size(); i++) {
00088 for(int j = 0; j < sccs[i].size(); j++)
00089 cout << " " << sccs[i][j];
00090 cout << endl;
00091 }
00092 }
00093 */
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines


tfd_modules
Author(s): Maintained by Christian Dornhege (see AUTHORS file).
autogenerated on Tue Jan 22 2013 12:25:03