1 | //======================================================================= |
2 | // Copyright 2001 University of Notre Dame. |
3 | // Author: Andrew Janiszewski, 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/core/lightweight_test.hpp> |
11 | #include <boost/graph/adjacency_list.hpp> |
12 | #include <boost/graph/random.hpp> |
13 | #include <boost/graph/graph_utility.hpp> |
14 | #include <boost/graph/graph_archetypes.hpp> |
15 | #include <boost/graph/breadth_first_search.hpp> |
16 | |
17 | #include <boost/random/mersenne_twister.hpp> |
18 | |
19 | #ifdef BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP |
20 | using namespace boost; |
21 | #endif |
22 | |
23 | template < typename DistanceMap, typename ParentMap, typename Graph, |
24 | typename ColorMap > |
25 | class bfs_testing_visitor |
26 | { |
27 | typedef typename boost::graph_traits< Graph >::vertex_descriptor Vertex; |
28 | typedef typename boost::graph_traits< Graph >::edge_descriptor Edge; |
29 | typedef typename boost::color_traits< |
30 | typename boost::property_traits< ColorMap >::value_type > |
31 | Color; |
32 | |
33 | public: |
34 | bfs_testing_visitor(Vertex s, DistanceMap d, ParentMap p, ColorMap c) |
35 | : current_distance(0), distance(d), parent(p), color(c), src(s) |
36 | { |
37 | } |
38 | |
39 | void initialize_vertex(const Vertex& u, const Graph&) const |
40 | { |
41 | BOOST_TEST(get(color, u) == Color::white()); |
42 | } |
43 | void examine_vertex(const Vertex& u, const Graph&) const |
44 | { |
45 | current_vertex = u; |
46 | // Ensure that the distances monotonically increase. |
47 | BOOST_TEST(distance[u] == current_distance |
48 | || distance[u] == current_distance + 1); |
49 | if (distance[u] == current_distance + 1) // new level |
50 | ++current_distance; |
51 | } |
52 | void discover_vertex(const Vertex& u, const Graph&) const |
53 | { |
54 | BOOST_TEST(get(color, u) == Color::gray()); |
55 | if (u == src) |
56 | { |
57 | current_vertex = src; |
58 | } |
59 | else |
60 | { |
61 | BOOST_TEST(parent[u] == current_vertex); |
62 | BOOST_TEST(distance[u] == current_distance + 1); |
63 | BOOST_TEST(distance[u] == distance[parent[u]] + 1); |
64 | } |
65 | } |
66 | void examine_edge(const Edge& e, const Graph& g) const |
67 | { |
68 | BOOST_TEST(source(e, g) == current_vertex); |
69 | } |
70 | void tree_edge(const Edge& e, const Graph& g) const |
71 | { |
72 | BOOST_TEST(get(color, target(e, g)) == Color::white()); |
73 | Vertex u = source(e, g), v = target(e, g); |
74 | BOOST_TEST(distance[u] == current_distance); |
75 | parent[v] = u; |
76 | distance[v] = distance[u] + 1; |
77 | } |
78 | void non_tree_edge(const Edge& e, const Graph& g) const |
79 | { |
80 | BOOST_TEST(color[target(e, g)] != Color::white()); |
81 | |
82 | if (boost::is_directed(g)) |
83 | // cross or back edge |
84 | BOOST_TEST(distance[target(e, g)] <= distance[source(e, g)] + 1); |
85 | else |
86 | { |
87 | // cross edge (or going backwards on a tree edge) |
88 | BOOST_TEST(distance[target(e, g)] == distance[source(e, g)] |
89 | || distance[target(e, g)] == distance[source(e, g)] + 1 |
90 | || distance[target(e, g)] == distance[source(e, g)] - 1); |
91 | } |
92 | } |
93 | |
94 | void gray_target(const Edge& e, const Graph& g) const |
95 | { |
96 | BOOST_TEST(color[target(e, g)] == Color::gray()); |
97 | } |
98 | |
99 | void black_target(const Edge& e, const Graph& g) const |
100 | { |
101 | BOOST_TEST(color[target(e, g)] == Color::black()); |
102 | |
103 | // All vertices adjacent to a black vertex must already be discovered |
104 | typename boost::graph_traits< Graph >::adjacency_iterator ai, ai_end; |
105 | for (boost::tie(ai, ai_end) = adjacent_vertices(target(e, g), g); |
106 | ai != ai_end; ++ai) |
107 | BOOST_TEST(color[*ai] != Color::white()); |
108 | } |
109 | void finish_vertex(const Vertex& u, const Graph&) const |
110 | { |
111 | BOOST_TEST(color[u] == Color::black()); |
112 | } |
113 | |
114 | private: |
115 | mutable Vertex current_vertex; |
116 | mutable typename boost::property_traits< DistanceMap >::value_type |
117 | current_distance; |
118 | DistanceMap distance; |
119 | ParentMap parent; |
120 | ColorMap color; |
121 | Vertex src; |
122 | }; |
123 | |
124 | template < class Graph > struct bfs_test |
125 | { |
126 | typedef boost::graph_traits< Graph > Traits; |
127 | typedef typename Traits::vertices_size_type vertices_size_type; |
128 | static void go(vertices_size_type max_V) |
129 | { |
130 | typedef typename Traits::vertex_descriptor vertex_descriptor; |
131 | typedef boost::color_traits< boost::default_color_type > Color; |
132 | |
133 | vertices_size_type i; |
134 | typename Traits::edges_size_type j; |
135 | typename Traits::vertex_iterator ui, ui_end; |
136 | |
137 | boost::mt19937 gen; |
138 | |
139 | for (i = 0; i < max_V; ++i) |
140 | for (j = 0; j < i * i; ++j) |
141 | { |
142 | Graph g; |
143 | boost::generate_random_graph(g, i, j, gen); |
144 | |
145 | // declare the "start" variable |
146 | vertex_descriptor start = boost::random_vertex(g, gen); |
147 | |
148 | // vertex properties |
149 | std::vector< int > distance( |
150 | i, (std::numeric_limits< int >::max)()); |
151 | distance[start] = 0; |
152 | std::vector< vertex_descriptor > parent(i); |
153 | for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) |
154 | parent[*ui] = *ui; |
155 | std::vector< boost::default_color_type > color(i); |
156 | |
157 | // Get vertex index map |
158 | typedef typename boost::property_map< Graph, |
159 | boost::vertex_index_t >::const_type idx_type; |
160 | idx_type idx = get(boost::vertex_index, g); |
161 | |
162 | // Make property maps from vectors |
163 | typedef boost::iterator_property_map< |
164 | std::vector< int >::iterator, idx_type > |
165 | distance_pm_type; |
166 | distance_pm_type distance_pm(distance.begin(), idx); |
167 | typedef boost::iterator_property_map< |
168 | typename std::vector< vertex_descriptor >::iterator, |
169 | idx_type > |
170 | parent_pm_type; |
171 | parent_pm_type parent_pm(parent.begin(), idx); |
172 | typedef boost::iterator_property_map< |
173 | std::vector< boost::default_color_type >::iterator, |
174 | idx_type > |
175 | color_pm_type; |
176 | color_pm_type color_pm(color.begin(), idx); |
177 | |
178 | // Create the testing visitor. |
179 | bfs_testing_visitor< distance_pm_type, parent_pm_type, Graph, |
180 | color_pm_type > |
181 | vis(start, distance_pm, parent_pm, color_pm); |
182 | |
183 | boost::breadth_first_search( |
184 | g, start, visitor(vis).color_map(color_pm)); |
185 | |
186 | // All white vertices should be unreachable from the source. |
187 | for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) |
188 | if (color[*ui] == Color::white()) |
189 | { |
190 | std::vector< boost::default_color_type > color2( |
191 | i, Color::white()); |
192 | BOOST_TEST(!boost::is_reachable( |
193 | start, *ui, g, color_pm_type(color2.begin(), idx))); |
194 | } |
195 | |
196 | // The shortest path to a child should be one longer than |
197 | // shortest path to the parent. |
198 | for (boost::tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui) |
199 | if (parent[*ui] != *ui) // *ui not the root of the bfs tree |
200 | BOOST_TEST(distance[*ui] == distance[parent[*ui]] + 1); |
201 | } |
202 | } |
203 | }; |
204 | |
205 | int main(int argc, char* argv[]) |
206 | { |
207 | using namespace boost; |
208 | int max_V = 7; |
209 | if (argc > 1) |
210 | max_V = atoi(nptr: argv[1]); |
211 | |
212 | bfs_test< adjacency_list< vecS, vecS, directedS > >::go(max_V); |
213 | bfs_test< adjacency_list< vecS, vecS, undirectedS > >::go(max_V); |
214 | return boost::report_errors(); |
215 | } |
216 | |