source: NonGTP/Boost/boost/graph/graph_test.hpp @ 857

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