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:
14The example graph:
15a --> b
16b --> a c
17c --> b
18
19Vertex a is in component 0 and has root 0
20Vertex b is in component 0 and has root 0
21Vertex 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
30int 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_&: G);
39 Vertex b = add_vertex(g_&: G);
40 Vertex c = add_vertex(g_&: G);
41
42 add_edge(u: a, v: b, g_&: G);
43 add_edge(u: b, v: a, g_&: G);
44
45 add_edge(u: c, v: b, g_&: G);
46 add_edge(u: b, v: c, g_&: 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_: G)),
56 discover_time(num_vertices(g_: G));
57 std::vector< default_color_type > color(num_vertices(g_: G));
58 std::vector< Vertex > root(num_vertices(g_: G));
59 strong_components(g: G,
60 comp: make_iterator_property_map(iter: component.begin(), id: get(p: vertex_index, g&: G)),
61 params: root_map(p: make_iterator_property_map(iter: root.begin(), id: get(p: vertex_index, g&: G)))
62 .color_map(
63 p: make_iterator_property_map(iter: color.begin(), id: get(p: vertex_index, g&: G)))
64 .discover_time_map(p: make_iterator_property_map(
65 iter: discover_time.begin(), id: get(p: vertex_index, g&: 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

source code of boost/libs/graph/test/strong_components_test.cpp