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
run_test()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(edge_pairs_g1[i].first, 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(edge_pairs_g3[i].first, edge_pairs_g3[i].second);
249 }
250 }
251 }
252 std::sort(edge_pairs_g1.begin(), edge_pairs_g1.end());
253 std::sort(edge_pairs_g3.begin(), edge_pairs_g3.end());
254 edge_pairs_g1.erase(std::unique(edge_pairs_g1.begin(), edge_pairs_g1.end()),
255 edge_pairs_g1.end());
256 edge_pairs_g3.erase(std::unique(edge_pairs_g3.begin(), edge_pairs_g3.end()),
257 edge_pairs_g3.end());
258 BOOST_TEST(edge_pairs_g1 == edge_pairs_g3);
259 }
260
test_remove_edges()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
main(int,char * [])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