1 | /* adjacency_matrix_test.cpp source file |
2 | * |
3 | * Copyright Cromwell D. Enage 2004 |
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 | * Defines the std::ios class and std::cout, its global output instance. |
12 | */ |
13 | #include <iostream> |
14 | |
15 | /* |
16 | * Defines the boost::property_map class template and the boost::get and |
17 | * boost::put function templates. |
18 | */ |
19 | #include <boost/property_map/property_map.hpp> |
20 | |
21 | /* |
22 | * Defines the boost::graph_traits class template. |
23 | */ |
24 | #include <boost/graph/graph_traits.hpp> |
25 | |
26 | /* |
27 | * Defines the vertex and edge property tags. |
28 | */ |
29 | #include <boost/graph/properties.hpp> |
30 | |
31 | /* |
32 | * Defines the boost::adjacency_list class template and its associated |
33 | * non-member function templates. |
34 | */ |
35 | #include <boost/graph/adjacency_list.hpp> |
36 | |
37 | /* |
38 | * Defines the boost::adjacency_matrix class template and its associated |
39 | * non-member function templates. |
40 | */ |
41 | #include <boost/graph/adjacency_matrix.hpp> |
42 | |
43 | #include <boost/core/lightweight_test.hpp> |
44 | |
45 | #include <vector> |
46 | #include <algorithm> // For std::sort |
47 | #include <boost/type_traits/is_convertible.hpp> |
48 | |
49 | #include <boost/graph/iteration_macros.hpp> |
50 | |
51 | template < typename Graph1, typename Graph2 > void run_test() |
52 | { |
53 | typedef typename boost::property_map< Graph1, boost::vertex_index_t >::type |
54 | IndexMap1; |
55 | typedef typename boost::property_map< Graph2, boost::vertex_index_t >::type |
56 | IndexMap2; |
57 | |
58 | Graph1 g1(24); |
59 | Graph2 g2(24); |
60 | |
61 | boost::add_edge(boost::vertex(1, g1), boost::vertex(2, g1), g1); |
62 | boost::add_edge(boost::vertex(1, g2), boost::vertex(2, g2), g2); |
63 | boost::add_edge(boost::vertex(2, g1), boost::vertex(10, g1), g1); |
64 | boost::add_edge(boost::vertex(2, g2), boost::vertex(10, g2), g2); |
65 | boost::add_edge(boost::vertex(2, g1), boost::vertex(5, g1), g1); |
66 | boost::add_edge(boost::vertex(2, g2), boost::vertex(5, g2), g2); |
67 | boost::add_edge(boost::vertex(3, g1), boost::vertex(10, g1), g1); |
68 | boost::add_edge(boost::vertex(3, g2), boost::vertex(10, g2), g2); |
69 | boost::add_edge(boost::vertex(3, g1), boost::vertex(0, g1), g1); |
70 | boost::add_edge(boost::vertex(3, g2), boost::vertex(0, g2), g2); |
71 | boost::add_edge(boost::vertex(4, g1), boost::vertex(5, g1), g1); |
72 | boost::add_edge(boost::vertex(4, g2), boost::vertex(5, g2), g2); |
73 | boost::add_edge(boost::vertex(4, g1), boost::vertex(0, g1), g1); |
74 | boost::add_edge(boost::vertex(4, g2), boost::vertex(0, g2), g2); |
75 | boost::add_edge(boost::vertex(5, g1), boost::vertex(14, g1), g1); |
76 | boost::add_edge(boost::vertex(5, g2), boost::vertex(14, g2), g2); |
77 | boost::add_edge(boost::vertex(6, g1), boost::vertex(3, g1), g1); |
78 | boost::add_edge(boost::vertex(6, g2), boost::vertex(3, g2), g2); |
79 | boost::add_edge(boost::vertex(7, g1), boost::vertex(17, g1), g1); |
80 | boost::add_edge(boost::vertex(7, g2), boost::vertex(17, g2), g2); |
81 | boost::add_edge(boost::vertex(7, g1), boost::vertex(11, g1), g1); |
82 | boost::add_edge(boost::vertex(7, g2), boost::vertex(11, g2), g2); |
83 | boost::add_edge(boost::vertex(8, g1), boost::vertex(17, g1), g1); |
84 | boost::add_edge(boost::vertex(8, g2), boost::vertex(17, g2), g2); |
85 | boost::add_edge(boost::vertex(8, g1), boost::vertex(1, g1), g1); |
86 | boost::add_edge(boost::vertex(8, g2), boost::vertex(1, g2), g2); |
87 | boost::add_edge(boost::vertex(9, g1), boost::vertex(11, g1), g1); |
88 | boost::add_edge(boost::vertex(9, g2), boost::vertex(11, g2), g2); |
89 | boost::add_edge(boost::vertex(9, g1), boost::vertex(1, g1), g1); |
90 | boost::add_edge(boost::vertex(9, g2), boost::vertex(1, g2), g2); |
91 | boost::add_edge(boost::vertex(10, g1), boost::vertex(19, g1), g1); |
92 | boost::add_edge(boost::vertex(10, g2), boost::vertex(19, g2), g2); |
93 | boost::add_edge(boost::vertex(10, g1), boost::vertex(15, g1), g1); |
94 | boost::add_edge(boost::vertex(10, g2), boost::vertex(15, g2), g2); |
95 | boost::add_edge(boost::vertex(10, g1), boost::vertex(8, g1), g1); |
96 | boost::add_edge(boost::vertex(10, g2), boost::vertex(8, g2), g2); |
97 | boost::add_edge(boost::vertex(11, g1), boost::vertex(19, g1), g1); |
98 | boost::add_edge(boost::vertex(11, g2), boost::vertex(19, g2), g2); |
99 | boost::add_edge(boost::vertex(11, g1), boost::vertex(15, g1), g1); |
100 | boost::add_edge(boost::vertex(11, g2), boost::vertex(15, g2), g2); |
101 | boost::add_edge(boost::vertex(11, g1), boost::vertex(4, g1), g1); |
102 | boost::add_edge(boost::vertex(11, g2), boost::vertex(4, g2), g2); |
103 | boost::add_edge(boost::vertex(12, g1), boost::vertex(19, g1), g1); |
104 | boost::add_edge(boost::vertex(12, g2), boost::vertex(19, g2), g2); |
105 | boost::add_edge(boost::vertex(12, g1), boost::vertex(8, g1), g1); |
106 | boost::add_edge(boost::vertex(12, g2), boost::vertex(8, g2), g2); |
107 | boost::add_edge(boost::vertex(12, g1), boost::vertex(4, g1), g1); |
108 | boost::add_edge(boost::vertex(12, g2), boost::vertex(4, g2), g2); |
109 | boost::add_edge(boost::vertex(13, g1), boost::vertex(15, g1), g1); |
110 | boost::add_edge(boost::vertex(13, g2), boost::vertex(15, g2), g2); |
111 | boost::add_edge(boost::vertex(13, g1), boost::vertex(8, g1), g1); |
112 | boost::add_edge(boost::vertex(13, g2), boost::vertex(8, g2), g2); |
113 | boost::add_edge(boost::vertex(13, g1), boost::vertex(4, g1), g1); |
114 | boost::add_edge(boost::vertex(13, g2), boost::vertex(4, g2), g2); |
115 | boost::add_edge(boost::vertex(14, g1), boost::vertex(22, g1), g1); |
116 | boost::add_edge(boost::vertex(14, g2), boost::vertex(22, g2), g2); |
117 | boost::add_edge(boost::vertex(14, g1), boost::vertex(12, g1), g1); |
118 | boost::add_edge(boost::vertex(14, g2), boost::vertex(12, g2), g2); |
119 | boost::add_edge(boost::vertex(15, g1), boost::vertex(22, g1), g1); |
120 | boost::add_edge(boost::vertex(15, g2), boost::vertex(22, g2), g2); |
121 | boost::add_edge(boost::vertex(15, g1), boost::vertex(6, g1), g1); |
122 | boost::add_edge(boost::vertex(15, g2), boost::vertex(6, g2), g2); |
123 | boost::add_edge(boost::vertex(16, g1), boost::vertex(12, g1), g1); |
124 | boost::add_edge(boost::vertex(16, g2), boost::vertex(12, g2), g2); |
125 | boost::add_edge(boost::vertex(16, g1), boost::vertex(6, g1), g1); |
126 | boost::add_edge(boost::vertex(16, g2), boost::vertex(6, g2), g2); |
127 | boost::add_edge(boost::vertex(17, g1), boost::vertex(20, g1), g1); |
128 | boost::add_edge(boost::vertex(17, g2), boost::vertex(20, g2), g2); |
129 | boost::add_edge(boost::vertex(18, g1), boost::vertex(9, g1), g1); |
130 | boost::add_edge(boost::vertex(18, g2), boost::vertex(9, g2), g2); |
131 | boost::add_edge(boost::vertex(19, g1), boost::vertex(23, g1), g1); |
132 | boost::add_edge(boost::vertex(19, g2), boost::vertex(23, g2), g2); |
133 | boost::add_edge(boost::vertex(19, g1), boost::vertex(18, g1), g1); |
134 | boost::add_edge(boost::vertex(19, g2), boost::vertex(18, g2), g2); |
135 | boost::add_edge(boost::vertex(20, g1), boost::vertex(23, g1), g1); |
136 | boost::add_edge(boost::vertex(20, g2), boost::vertex(23, g2), g2); |
137 | boost::add_edge(boost::vertex(20, g1), boost::vertex(13, g1), g1); |
138 | boost::add_edge(boost::vertex(20, g2), boost::vertex(13, g2), g2); |
139 | boost::add_edge(boost::vertex(21, g1), boost::vertex(18, g1), g1); |
140 | boost::add_edge(boost::vertex(21, g2), boost::vertex(18, g2), g2); |
141 | boost::add_edge(boost::vertex(21, g1), boost::vertex(13, g1), g1); |
142 | boost::add_edge(boost::vertex(21, g2), boost::vertex(13, g2), g2); |
143 | boost::add_edge(boost::vertex(22, g1), boost::vertex(21, g1), g1); |
144 | boost::add_edge(boost::vertex(22, g2), boost::vertex(21, g2), g2); |
145 | boost::add_edge(boost::vertex(23, g1), boost::vertex(16, g1), g1); |
146 | boost::add_edge(boost::vertex(23, g2), boost::vertex(16, g2), g2); |
147 | |
148 | IndexMap1 index_map1 = boost::get(boost::vertex_index_t(), g1); |
149 | IndexMap2 index_map2 = boost::get(boost::vertex_index_t(), g2); |
150 | typename boost::graph_traits< Graph1 >::vertex_iterator vi1, vend1; |
151 | typename boost::graph_traits< Graph2 >::vertex_iterator vi2, vend2; |
152 | |
153 | typename boost::graph_traits< Graph1 >::adjacency_iterator ai1, aend1; |
154 | typename boost::graph_traits< Graph2 >::adjacency_iterator ai2, aend2; |
155 | |
156 | for (boost::tie(vi1, vend1) = boost::vertices(g1), |
157 | boost::tie(vi2, vend2) = boost::vertices(g2); |
158 | vi1 != vend1; ++vi1, ++vi2) |
159 | { |
160 | BOOST_TEST( |
161 | boost::get(index_map1, *vi1) == boost::get(index_map2, *vi2)); |
162 | |
163 | for (boost::tie(ai1, aend1) = boost::adjacent_vertices(*vi1, g1), |
164 | boost::tie(ai2, aend2) |
165 | = boost::adjacent_vertices(*vi2, g2); |
166 | ai1 != aend1; ++ai1, ++ai2) |
167 | { |
168 | BOOST_TEST( |
169 | boost::get(index_map1, *ai1) == boost::get(index_map2, *ai2)); |
170 | } |
171 | } |
172 | |
173 | typename boost::graph_traits< Graph1 >::out_edge_iterator ei1, eend1; |
174 | typename boost::graph_traits< Graph2 >::out_edge_iterator ei2, eend2; |
175 | |
176 | for (boost::tie(vi1, vend1) = boost::vertices(g1), |
177 | boost::tie(vi2, vend2) = boost::vertices(g2); |
178 | vi1 != vend1; ++vi1, ++vi2) |
179 | { |
180 | BOOST_TEST( |
181 | boost::get(index_map1, *vi1) == boost::get(index_map2, *vi2)); |
182 | |
183 | for (boost::tie(ei1, eend1) = boost::out_edges(*vi1, g1), |
184 | boost::tie(ei2, eend2) |
185 | = boost::out_edges(*vi2, g2); |
186 | ei1 != eend1; ++ei1, ++ei2) |
187 | { |
188 | BOOST_TEST(boost::get(index_map1, boost::target(*ei1, g1)) |
189 | == boost::get(index_map2, boost::target(*ei2, g2))); |
190 | } |
191 | } |
192 | |
193 | typename boost::graph_traits< Graph1 >::in_edge_iterator iei1, ieend1; |
194 | typename boost::graph_traits< Graph2 >::in_edge_iterator iei2, ieend2; |
195 | |
196 | for (boost::tie(vi1, vend1) = boost::vertices(g1), |
197 | boost::tie(vi2, vend2) = boost::vertices(g2); |
198 | vi1 != vend1; ++vi1, ++vi2) |
199 | { |
200 | BOOST_TEST( |
201 | boost::get(index_map1, *vi1) == boost::get(index_map2, *vi2)); |
202 | |
203 | for (boost::tie(iei1, ieend1) = boost::in_edges(*vi1, g1), |
204 | boost::tie(iei2, ieend2) |
205 | = boost::in_edges(*vi2, g2); |
206 | iei1 != ieend1; ++iei1, ++iei2) |
207 | { |
208 | BOOST_TEST(boost::get(index_map1, boost::target(*iei1, g1)) |
209 | == boost::get(index_map2, boost::target(*iei2, g2))); |
210 | } |
211 | } |
212 | |
213 | // Test construction from a range of pairs |
214 | std::vector< std::pair< int, int > > edge_pairs_g1; |
215 | BGL_FORALL_EDGES_T(e, g1, Graph1) |
216 | { |
217 | edge_pairs_g1.push_back(std::make_pair( |
218 | get(index_map1, source(e, g1)), get(index_map1, target(e, g1)))); |
219 | } |
220 | Graph2 g3(edge_pairs_g1.begin(), edge_pairs_g1.end(), num_vertices(g1)); |
221 | BOOST_TEST(num_vertices(g1) == num_vertices(g3)); |
222 | std::vector< std::pair< int, int > > edge_pairs_g3; |
223 | IndexMap2 index_map3 = boost::get(boost::vertex_index_t(), g3); |
224 | BGL_FORALL_EDGES_T(e, g3, Graph2) |
225 | { |
226 | edge_pairs_g3.push_back(std::make_pair( |
227 | get(index_map3, source(e, g3)), get(index_map3, target(e, g3)))); |
228 | } |
229 | // Normalize the edge pairs for comparison |
230 | if (boost::is_convertible< |
231 | typename boost::graph_traits< Graph1 >::directed_category*, |
232 | boost::undirected_tag* >::value |
233 | || boost::is_convertible< |
234 | typename boost::graph_traits< Graph2 >::directed_category*, |
235 | boost::undirected_tag* >::value) |
236 | { |
237 | for (size_t i = 0; i < edge_pairs_g1.size(); ++i) |
238 | { |
239 | if (edge_pairs_g1[i].first < edge_pairs_g1[i].second) |
240 | { |
241 | std::swap(a&: edge_pairs_g1[i].first, b&: edge_pairs_g1[i].second); |
242 | } |
243 | } |
244 | for (size_t i = 0; i < edge_pairs_g3.size(); ++i) |
245 | { |
246 | if (edge_pairs_g3[i].first < edge_pairs_g3[i].second) |
247 | { |
248 | std::swap(a&: edge_pairs_g3[i].first, b&: edge_pairs_g3[i].second); |
249 | } |
250 | } |
251 | } |
252 | std::sort(first: edge_pairs_g1.begin(), last: edge_pairs_g1.end()); |
253 | std::sort(first: edge_pairs_g3.begin(), last: edge_pairs_g3.end()); |
254 | edge_pairs_g1.erase(first: std::unique(first: edge_pairs_g1.begin(), last: edge_pairs_g1.end()), |
255 | last: edge_pairs_g1.end()); |
256 | edge_pairs_g3.erase(first: std::unique(first: edge_pairs_g3.begin(), last: edge_pairs_g3.end()), |
257 | last: edge_pairs_g3.end()); |
258 | BOOST_TEST(edge_pairs_g1 == edge_pairs_g3); |
259 | } |
260 | |
261 | template < typename Graph > void test_remove_edges() |
262 | { |
263 | using namespace boost; |
264 | |
265 | // Build a 2-vertex graph |
266 | Graph g(2); |
267 | add_edge(vertex(0, g), vertex(1, g), g); |
268 | BOOST_TEST(num_vertices(g) == 2); |
269 | BOOST_TEST(num_edges(g) == 1); |
270 | remove_edge(vertex(0, g), vertex(1, g), g); |
271 | BOOST_TEST(num_edges(g) == 0); |
272 | |
273 | // Make sure we don't decrement the edge count if the edge doesn't actually |
274 | // exist. |
275 | remove_edge(vertex(0, g), vertex(1, g), g); |
276 | BOOST_TEST(num_edges(g) == 0); |
277 | } |
278 | |
279 | int main(int, char*[]) |
280 | { |
281 | // Use setS to keep out edges in order, so they match the adjacency_matrix. |
282 | typedef boost::adjacency_list< boost::setS, boost::vecS, |
283 | boost::undirectedS > |
284 | UGraph1; |
285 | typedef boost::adjacency_matrix< boost::undirectedS > UGraph2; |
286 | run_test< UGraph1, UGraph2 >(); |
287 | |
288 | // Use setS to keep out edges in order, so they match the adjacency_matrix. |
289 | typedef boost::adjacency_list< boost::setS, boost::vecS, |
290 | boost::bidirectionalS > |
291 | BGraph1; |
292 | typedef boost::adjacency_matrix< boost::directedS > BGraph2; |
293 | run_test< BGraph1, BGraph2 >(); |
294 | |
295 | test_remove_edges< UGraph2 >(); |
296 | test_remove_edges< BGraph2 >(); |
297 | |
298 | return boost::report_errors(); |
299 | } |
300 | |