1 //=======================================================================
2 // Copyright 2014 Alexander Lauser.
3 // Authors: Alexander Lauser
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 // This test is an adapted version of the MWE for Bug #10231 (showing
11 // incorrect root_map computation).
12
13 /* Output should be:
14 The example graph:
15 a --> b
16 b --> a c
17 c --> b
18
19 Vertex a is in component 0 and has root 0
20 Vertex b is in component 0 and has root 0
21 Vertex c is in component 0 and has root 0
22 */
23 #include <boost/config.hpp>
24 #include <iostream>
25 #include <vector>
26 #include <boost/graph/strong_components.hpp>
27 #include <boost/graph/adjacency_list.hpp>
28 #include <boost/graph/graph_utility.hpp>
29
main(int,char * [])30 int main(int, char*[])
31 {
32 using namespace boost;
33
34 adjacency_list< vecS, vecS, directedS > G;
35
36 typedef graph_traits<
37 adjacency_list< vecS, vecS, directedS > >::vertex_descriptor Vertex;
38 Vertex a = add_vertex(G);
39 Vertex b = add_vertex(G);
40 Vertex c = add_vertex(G);
41
42 add_edge(a, b, G);
43 add_edge(b, a, G);
44
45 add_edge(c, b, G);
46 add_edge(b, c, G);
47
48 #if VERBOSE
49 std::cout << "The example graph:" << std::endl;
50 const char* name = "abc";
51 print_graph(G, name);
52 std::cout << std::endl;
53 #endif
54
55 std::vector< int > component(num_vertices(G)),
56 discover_time(num_vertices(G));
57 std::vector< default_color_type > color(num_vertices(G));
58 std::vector< Vertex > root(num_vertices(G));
59 strong_components(G,
60 make_iterator_property_map(component.begin(), get(vertex_index, G)),
61 root_map(make_iterator_property_map(root.begin(), get(vertex_index, G)))
62 .color_map(
63 make_iterator_property_map(color.begin(), get(vertex_index, G)))
64 .discover_time_map(make_iterator_property_map(
65 discover_time.begin(), get(vertex_index, G))));
66
67 #if VERBOSE
68 for (std::vector< int >::size_type i = 0; i != component.size(); ++i)
69 std::cout << "Vertex " << name[i] << " is in component " << component[i]
70 << " and has root " << root[i] << std::endl;
71 #endif
72
73 #if VERBOSE
74 bool test_failed;
75 #endif
76 int ret = 0;
77
78 //////////
79 #if VERBOSE
80 test_failed = false;
81 std::cerr << "Testing component-computation of strong_components ..."
82 << std::endl;
83 #endif
84 for (std::vector< int >::size_type i = 0; i != component.size(); ++i)
85 {
86 if (component[i] != 0)
87 {
88 #if VERBOSE
89 test_failed = true;
90 #endif
91 ret = -1;
92 break;
93 }
94 }
95 #if VERBOSE
96 std::cerr << (test_failed ? " **** Failed." : " Passed.") << std::endl;
97 #endif
98 //////////
99
100 //////////
101 #if VERBOSE
102 test_failed = false;
103 std::cerr << "Testing root_map-computation of strong_components ..."
104 << std::endl;
105 #endif
106 for (std::vector< int >::size_type i = 0; i != component.size(); ++i)
107 {
108 if (root[i] != 0)
109 {
110 #if VERBOSE
111 test_failed = true;
112 #endif
113 ret = -1;
114 break;
115 }
116 }
117 #if VERBOSE
118 std::cerr << (test_failed ? " **** Failed." : " Passed.") << std::endl;
119 #endif
120 //////////
121
122 if (ret == 0)
123 std::cout << "tests passed" << std::endl;
124 return ret;
125 }
126