1 //=======================================================================
2 // Copyright 1997-2001 University of Notre Dame.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
4 //
5 // Distributed under the Boost Software License, Version 1.0. (See
6 // accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //=======================================================================
9
10 #include <boost/config.hpp>
11 #include <iostream>
12 #include <vector>
13 #include <boost/graph/strong_components.hpp>
14 #include <boost/graph/adjacency_list.hpp>
15 #include <boost/graph/graphviz.hpp>
16 #include <boost/graph/graph_utility.hpp>
17 /*
18 Sample output:
19 A directed graph:
20 a --> b f h
21 b --> c a
22 c --> d b
23 d --> e
24 e --> d
25 f --> g
26 g --> f d
27 h --> i
28 i --> h j e c
29 j -->
30
31 Total number of components: 4
32 Vertex a is in component 3
33 Vertex b is in component 3
34 Vertex c is in component 3
35 Vertex d is in component 0
36 Vertex e is in component 0
37 Vertex f is in component 1
38 Vertex g is in component 1
39 Vertex h is in component 3
40 Vertex i is in component 3
41 Vertex j is in component 2
42 */
43
main(int,char * [])44 int main(int, char*[])
45 {
46 using namespace boost;
47 const char* name = "abcdefghij";
48
49 adjacency_list<vecS, vecS, directedS> G;
50 dynamic_properties dp;
51 read_graphviz("scc.dot", G, dp);
52
53 std::cout << "A directed graph:" << std::endl;
54 print_graph(G, name);
55 std::cout << std::endl;
56
57 typedef graph_traits<adjacency_list<vecS, vecS, directedS> >::vertex_descriptor Vertex;
58
59 std::vector<int> component(num_vertices(G)), discover_time(num_vertices(G));
60 std::vector<default_color_type> color(num_vertices(G));
61 std::vector<Vertex> root(num_vertices(G));
62 int num = strong_components(G, make_iterator_property_map(component.begin(), get(vertex_index, G)),
63 root_map(make_iterator_property_map(root.begin(), get(vertex_index, G))).
64 color_map(make_iterator_property_map(color.begin(), get(vertex_index, G))).
65 discover_time_map(make_iterator_property_map(discover_time.begin(), get(vertex_index, G))));
66
67 std::cout << "Total number of components: " << num << std::endl;
68 std::vector<int>::size_type i;
69 for (i = 0; i != component.size(); ++i)
70 std::cout << "Vertex " << name[i]
71 <<" is in component " << component[i] << std::endl;
72
73 return 0;
74 }
75