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