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 | |
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_&: 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 | |