Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / graph_test.hpp
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
24 namespace 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