1 //=======================================================================
2 // Copyright 2002 Indiana University.
3 // Authors: Andrew Lumsdaine, Lie-Quan Lee, 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 #ifndef BOOST_GRAPH_TEST_HPP
11 #define BOOST_GRAPH_TEST_HPP
12 
13 #include <vector>
14 #include <boost/test/minimal.hpp>
15 #include <boost/graph/filtered_graph.hpp>
16 #include <boost/graph/iteration_macros.hpp>
17 #include <boost/graph/isomorphism.hpp>
18 #include <boost/graph/copy.hpp>
19 #include <boost/graph/graph_utility.hpp> // for connects
20 #include <boost/range.hpp>
21 #include <boost/range/algorithm/find_if.hpp>
22 
23 
24 // UNDER CONSTRUCTION
25 
26 namespace boost {
27 
28   template <typename Graph>
29   struct graph_test
30   {
31 
32     typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
33     typedef typename graph_traits<Graph>::edge_descriptor edge_t;
34     typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
35     typedef typename graph_traits<Graph>::degree_size_type deg_size_t;
36     typedef typename graph_traits<Graph>::edges_size_type e_size_t;
37     typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iter;
38     typedef typename property_map<Graph, vertex_index_t>::type index_map_t;
39     typedef iterator_property_map<typename std::vector<vertex_t>::iterator,
40       index_map_t,vertex_t,vertex_t&> IsoMap;
41 
42     struct ignore_vertex {
ignore_vertexboost::graph_test::ignore_vertex43       ignore_vertex() { }
ignore_vertexboost::graph_test::ignore_vertex44       ignore_vertex(vertex_t v) : v(v) { }
operator ()boost::graph_test::ignore_vertex45       bool operator()(vertex_t x) const { return x != v; }
46       vertex_t v;
47     };
48     struct ignore_edge {
ignore_edgeboost::graph_test::ignore_edge49       ignore_edge() { }
ignore_edgeboost::graph_test::ignore_edge50       ignore_edge(edge_t e) : e(e) { }
operator ()boost::graph_test::ignore_edge51       bool operator()(edge_t x) const { return x != e; }
52       edge_t e;
53     };
54     struct ignore_edges {
ignore_edgesboost::graph_test::ignore_edges55       ignore_edges(vertex_t s, vertex_t t, const Graph& g)
56         : s(s), t(t), g(g) { }
operator ()boost::graph_test::ignore_edges57       bool operator()(edge_t x) const {
58         return !(source(x, g) == s && target(x, g) == t);
59       }
60       vertex_t s; vertex_t t; const Graph& g;
61     };
62 
63     //=========================================================================
64     // Traversal Operations
65 
test_incidence_graphboost::graph_test66     void test_incidence_graph
67        (const std::vector<vertex_t>& vertex_set,
68         const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,
69         const Graph& g)
70     {
71       typedef typename std::vector<vertex_t>::const_iterator vertex_iter;
72       typedef typename std::vector< std::pair<vertex_t, vertex_t> >
73         ::const_iterator edge_iter;
74       typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iter;
75 
76       for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) {
77         vertex_t u = *ui;
78         std::vector<vertex_t> adj;
79         for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e)
80           if (e->first == u)
81             adj.push_back(e->second);
82 
83         std::pair<out_edge_iter, out_edge_iter> p = out_edges(u, g);
84         BOOST_CHECK(out_degree(u, g) == adj.size());
85         BOOST_CHECK(deg_size_t(std::distance(p.first, p.second))
86                    == out_degree(u, g));
87         for (; p.first != p.second; ++p.first) {
88           edge_t e = *p.first;
89           BOOST_CHECK(source(e, g) == u);
90           BOOST_CHECK(container_contains(adj, target(e, g)) == true);
91         }
92       }
93     }
94 
test_bidirectional_graphboost::graph_test95     void test_bidirectional_graph
96       (const std::vector<vertex_t>& vertex_set,
97        const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,
98        const Graph& g)
99     {
100       typedef typename std::vector<vertex_t>::const_iterator vertex_iter;
101       typedef typename std::vector< std::pair<vertex_t, vertex_t> >
102         ::const_iterator edge_iter;
103       typedef typename graph_traits<Graph>::in_edge_iterator in_edge_iter;
104 
105       for (vertex_iter vi = vertex_set.begin(); vi != vertex_set.end(); ++vi) {
106         vertex_t v = *vi;
107         std::vector<vertex_t> inv_adj;
108         for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e)
109           if (e->second == v)
110             inv_adj.push_back(e->first);
111 
112         std::pair<in_edge_iter, in_edge_iter> p = in_edges(v, g);
113         BOOST_CHECK(in_degree(v, g) == inv_adj.size());
114         BOOST_CHECK(deg_size_t(std::distance(p.first, p.second))
115                    == in_degree(v, g));
116         for (; p.first != p.second; ++p.first) {
117           edge_t e = *p.first;
118           BOOST_CHECK(target(e, g) == v);
119           BOOST_CHECK(container_contains(inv_adj, source(e, g)) == true);
120         }
121       }
122     }
123 
test_adjacency_graphboost::graph_test124     void test_adjacency_graph
125       (const std::vector<vertex_t>& vertex_set,
126        const std::vector< std::pair<vertex_t,vertex_t> >& edge_set,
127        const Graph& g)
128     {
129       typedef typename std::vector<vertex_t>::const_iterator vertex_iter;
130       typedef typename std::vector<std::pair<vertex_t,vertex_t> >
131         ::const_iterator edge_iter;
132       typedef typename graph_traits<Graph>::adjacency_iterator adj_iter;
133 
134       for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) {
135         vertex_t u = *ui;
136         std::vector<vertex_t> adj;
137         for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e)
138           if (e->first == u)
139             adj.push_back(e->second);
140 
141         std::pair<adj_iter, adj_iter> p = adjacent_vertices(u, g);
142         BOOST_CHECK(deg_size_t(std::distance(p.first, p.second)) == adj.size());
143         for (; p.first != p.second; ++p.first) {
144           vertex_t v = *p.first;
145           BOOST_CHECK(container_contains(adj, v) == true);
146         }
147       }
148     }
149 
test_vertex_list_graphboost::graph_test150     void test_vertex_list_graph
151       (const std::vector<vertex_t>& vertex_set, const Graph& g)
152     {
153       typedef typename graph_traits<Graph>::vertex_iterator v_iter;
154       std::pair<v_iter, v_iter> p = vertices(g);
155       BOOST_CHECK(num_vertices(g) == vertex_set.size());
156       v_size_t n = (size_t)std::distance(p.first, p.second);
157       BOOST_CHECK(n == num_vertices(g));
158       for (; p.first != p.second; ++p.first) {
159         vertex_t v = *p.first;
160         BOOST_CHECK(container_contains(vertex_set, v) == true);
161       }
162     }
163 
test_edge_list_graphboost::graph_test164     void test_edge_list_graph
165       (const std::vector<vertex_t>& vertex_set,
166        const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,
167        const Graph& g)
168     {
169       typedef typename graph_traits<Graph>::edge_iterator e_iter;
170       std::pair<e_iter, e_iter> p = edges(g);
171       BOOST_CHECK(num_edges(g) == edge_set.size());
172       e_size_t m = std::distance(p.first, p.second);
173       BOOST_CHECK(m == num_edges(g));
174       for (; p.first != p.second; ++p.first) {
175         edge_t e = *p.first;
176         BOOST_CHECK(find_if(edge_set, connects(source(e, g), target(e, g), g)) != boost::end(edge_set));
177         BOOST_CHECK(container_contains(vertex_set, source(e, g)) == true);
178         BOOST_CHECK(container_contains(vertex_set, target(e, g)) == true);
179       }
180     }
181 
test_adjacency_matrixboost::graph_test182     void test_adjacency_matrix
183       (const std::vector<vertex_t>& vertex_set,
184        const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,
185        const Graph& g)
186     {
187       std::pair<edge_t, bool> p;
188       for (typename std::vector<std::pair<vertex_t, vertex_t> >
189              ::const_iterator i = edge_set.begin();
190            i != edge_set.end(); ++i) {
191         p = edge(i->first, i->second, g);
192         BOOST_CHECK(p.second == true);
193         BOOST_CHECK(source(p.first, g) == i->first);
194         BOOST_CHECK(target(p.first, g) == i->second);
195       }
196       typename std::vector<vertex_t>::const_iterator j, k;
197       for (j = vertex_set.begin(); j != vertex_set.end(); ++j)
198         for (k = vertex_set.begin(); k != vertex_set.end(); ++k) {
199           p = edge(*j, *k, g);
200           if (p.second == true)
201             BOOST_CHECK(find_if(edge_set,
202               connects(source(p.first, g), target(p.first, g), g)) != boost::end(edge_set));
203         }
204     }
205 
206     //=========================================================================
207     // Mutating Operations
208 
test_add_vertexboost::graph_test209     void test_add_vertex(Graph& g)
210     {
211       Graph cpy;
212       std::vector<vertex_t> iso_vec(num_vertices(g));
213       IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
214       copy_graph(g, cpy, orig_to_copy(iso_map));
215 
216       BOOST_CHECK((verify_isomorphism(g, cpy, iso_map)));
217 
218       vertex_t v = add_vertex(g);
219 
220       BOOST_CHECK(num_vertices(g) == num_vertices(cpy) + 1);
221 
222       BOOST_CHECK(out_degree(v, g) == 0);
223 
224       // Make sure the rest of the graph stayed the same
225       BOOST_CHECK((verify_isomorphism
226                   (make_filtered_graph(g, keep_all(), ignore_vertex(v)), cpy,
227                    iso_map)));
228     }
229 
test_add_edgeboost::graph_test230     void test_add_edge(vertex_t u, vertex_t v, Graph& g)
231     {
232       Graph cpy;
233       std::vector<vertex_t> iso_vec(num_vertices(g));
234       IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
235       copy_graph(g, cpy, orig_to_copy(iso_map));
236 
237       bool parallel_edge_exists = container_contains(adjacent_vertices(u, g), v);
238 
239       std::pair<edge_t, bool> p = add_edge(u, v, g);
240       edge_t e = p.first;
241       bool added = p.second;
242 
243       if (is_undirected(g) && u == v) // self edge
244         BOOST_CHECK(added == false);
245       else if (parallel_edge_exists)
246         BOOST_CHECK(allows_parallel_edges(g) && added == true
247                    || !allows_parallel_edges(g) && added == false);
248       else
249         BOOST_CHECK(added == true);
250 
251       if (p.second == true) { // edge added
252         BOOST_CHECK(num_edges(g) == num_edges(cpy) + 1);
253 
254         BOOST_CHECK(container_contains(out_edges(u, g), e) == true);
255 
256         BOOST_CHECK((verify_isomorphism
257                     (make_filtered_graph(g, ignore_edge(e)), cpy, iso_map)));
258       }
259       else { // edge not added
260         if (! (is_undirected(g) && u == v)) {
261           // e should be a parallel edge
262           BOOST_CHECK(source(e, g) == u);
263           BOOST_CHECK(target(e, g) == v);
264         }
265         // The graph should not be changed.
266         BOOST_CHECK((verify_isomorphism(g, cpy, iso_map)));
267       }
268     } // test_add_edge()
269 
270 
test_remove_edgeboost::graph_test271     void test_remove_edge(vertex_t u, vertex_t v, Graph& g)
272     {
273       Graph cpy;
274       std::vector<vertex_t> iso_vec(num_vertices(g));
275       IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
276       copy_graph(g, cpy, orig_to_copy(iso_map));
277 
278       deg_size_t occurances = count(adjacent_vertices(u, g), v);
279 
280       remove_edge(u, v, g);
281 
282       BOOST_CHECK(num_edges(g) + occurances == num_edges(cpy));
283       BOOST_CHECK((verify_isomorphism
284                   (g, make_filtered_graph(cpy, ignore_edges(u,v,cpy)),
285                    iso_map)));
286     }
287 
test_remove_edgeboost::graph_test288     void test_remove_edge(edge_t e, Graph& g)
289     {
290       Graph cpy;
291       std::vector<vertex_t> iso_vec(num_vertices(g));
292       IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
293       copy_graph(g, cpy, orig_to_copy(iso_map));
294 
295       vertex_t u = source(e, g), v = target(e, g);
296       deg_size_t occurances = count(adjacent_vertices(u, g), v);
297 
298       remove_edge(e, g);
299 
300       BOOST_CHECK(num_edges(g) + 1 == num_edges(cpy));
301       BOOST_CHECK(count(adjacent_vertices(u, g), v) + 1 == occurances);
302       BOOST_CHECK((verify_isomorphism
303                   (g, make_filtered_graph(cpy, ignore_edge(e)),
304                    iso_map)));
305     }
306 
test_clear_vertexboost::graph_test307     void test_clear_vertex(vertex_t v, Graph& g)
308     {
309       Graph cpy;
310       std::vector<vertex_t> iso_vec(num_vertices(g));
311       IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
312       copy_graph(g, cpy, orig_to_copy(iso_map));
313 
314       clear_vertex(v, g);
315 
316       BOOST_CHECK(out_degree(v, g) == 0);
317       BOOST_CHECK(num_vertices(g) == num_vertices(cpy));
318       BOOST_CHECK((verify_isomorphism
319                   (g, make_filtered_graph(cpy, keep_all(), ignore_vertex(v)),
320                    iso_map)));
321     }
322 
323     //=========================================================================
324     // Property Map
325 
326     template <typename PropVal, typename PropertyTag>
test_readable_vertex_property_graphboost::graph_test327     void test_readable_vertex_property_graph
328       (const std::vector<PropVal>& vertex_prop, PropertyTag tag, const Graph& g)
329     {
330       typedef typename property_map<Graph, PropertyTag>::const_type const_Map;
331       const_Map pmap = get(tag, g);
332       typename std::vector<PropVal>::const_iterator i = vertex_prop.begin();
333 
334   for (typename boost::graph_traits<Graph>::vertex_iterator
335            bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second;
336        bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9)
337     for (typename boost::graph_traits<Graph>::vertex_descriptor v;
338          bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false;
339          ++bgl_first_9) {
340       //BGL_FORALL_VERTICES_T(v, g, Graph) {
341         typename property_traits<const_Map>::value_type
342           pval1 = get(pmap, v), pval2 = get(tag, g, v);
343         BOOST_CHECK(pval1 == pval2);
344         BOOST_CHECK(pval1 == *i++);
345       }
346     }
347 
348     template <typename PropVal, typename PropertyTag>
test_vertex_property_graphboost::graph_test349     void test_vertex_property_graph
350       (const std::vector<PropVal>& vertex_prop, PropertyTag tag, Graph& g)
351     {
352       typedef typename property_map<Graph, PropertyTag>::type PMap;
353       PMap pmap = get(tag, g);
354       typename std::vector<PropVal>::const_iterator i = vertex_prop.begin();
355   for (typename boost::graph_traits<Graph>::vertex_iterator
356            bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second;
357        bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9)
358     for (typename boost::graph_traits<Graph>::vertex_descriptor v;
359          bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false;
360          ++bgl_first_9)
361       //      BGL_FORALL_VERTICES_T(v, g, Graph)
362         put(pmap, v, *i++);
363 
364       test_readable_vertex_property_graph(vertex_prop, tag, g);
365 
366       BGL_FORALL_VERTICES_T(v, g, Graph)
367         put(pmap, v, vertex_prop[0]);
368 
369       typename std::vector<PropVal>::const_iterator j = vertex_prop.begin();
370       BGL_FORALL_VERTICES_T(v, g, Graph)
371         put(tag, g, v, *j++);
372 
373       test_readable_vertex_property_graph(vertex_prop, tag, g);
374     }
375 
376 
377   };
378 
379 
380 } // namespace boost
381 
382 #include <boost/graph/iteration_macros_undef.hpp>
383 
384 #endif // BOOST_GRAPH_TEST_HPP
385