//======================================================================= // Copyright 1997-2001 University of Notre Dame. // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= #include #include #include #include #include #include #include /* Sample output: A directed graph: a --> b f h b --> c a c --> d b d --> e e --> d f --> g g --> f d h --> i i --> h j e c j --> Total number of components: 4 Vertex a is in component 3 Vertex b is in component 3 Vertex c is in component 3 Vertex d is in component 0 Vertex e is in component 0 Vertex f is in component 1 Vertex g is in component 1 Vertex h is in component 3 Vertex i is in component 3 Vertex j is in component 2 */ int main(int, char*[]) { using namespace boost; const char* name = "abcdefghij"; GraphvizDigraph G; read_graphviz("scc.dot", G); std::cout << "A directed graph:" << std::endl; print_graph(G, name); std::cout << std::endl; typedef graph_traits::vertex_descriptor Vertex; std::vector component(num_vertices(G)), discover_time(num_vertices(G)); std::vector color(num_vertices(G)); std::vector root(num_vertices(G)); int num = strong_components(G, &component[0], root_map(&root[0]). color_map(&color[0]). discover_time_map(&discover_time[0])); std::cout << "Total number of components: " << num << std::endl; std::vector::size_type i; for (i = 0; i != component.size(); ++i) std::cout << "Vertex " << name[i] <<" is in component " << component[i] << std::endl; return 0; }