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 /*
11 IMPORTANT!!!
12 ~~~~~~~~~~~~
13 This example uses interfaces that have been deprecated and removed from
14 Boost.Grpah. Someone needs to update it, as it does NOT compile.
15 */
16
17 #include <boost/config.hpp>
18 #include <iostream>
19 #include <vector>
20 #include <boost/graph/strong_components.hpp>
21 #include <boost/graph/adjacency_list.hpp>
22 #include <boost/graph/graphviz.hpp>
23 #include <boost/graph/graph_utility.hpp>
24 /*
25 Sample output:
26 A directed graph:
27 a --> b f h
28 b --> c a
29 c --> d b
30 d --> e
31 e --> d
32 f --> g
33 g --> f d
34 h --> i
35 i --> h j e c
36 j -->
37
38 Total number of components: 4
39 Vertex a is in component 3
40 Vertex b is in component 3
41 Vertex c is in component 3
42 Vertex d is in component 0
43 Vertex e is in component 0
44 Vertex f is in component 1
45 Vertex g is in component 1
46 Vertex h is in component 3
47 Vertex i is in component 3
48 Vertex j is in component 2
49 */
50
main(int,char * [])51 int main(int, char*[])
52 {
53 using namespace boost;
54 const char* name = "abcdefghij";
55
56 adjacency_list< vecS, vecS, directedS > G;
57 dynamic_properties dp;
58 read_graphviz("scc.dot", G, dp);
59
60 std::cout << "A directed graph:" << std::endl;
61 print_graph(G, name);
62 std::cout << std::endl;
63
64 typedef graph_traits<
65 adjacency_list< vecS, vecS, directedS > >::vertex_descriptor Vertex;
66
67 std::vector< int > component(num_vertices(G)),
68 discover_time(num_vertices(G));
69 std::vector< default_color_type > color(num_vertices(G));
70 std::vector< Vertex > root(num_vertices(G));
71 int num = strong_components(G,
72 make_iterator_property_map(component.begin(), get(vertex_index, G)),
73 root_map(make_iterator_property_map(root.begin(), get(vertex_index, G)))
74 .color_map(
75 make_iterator_property_map(color.begin(), get(vertex_index, G)))
76 .discover_time_map(make_iterator_property_map(
77 discover_time.begin(), get(vertex_index, G))));
78
79 std::cout << "Total number of components: " << num << std::endl;
80 std::vector< int >::size_type i;
81 for (i = 0; i != component.size(); ++i)
82 std::cout << "Vertex " << name[i] << " is in component " << component[i]
83 << std::endl;
84
85 return 0;
86 }
87