epoc32/include/stdapis/boost/graph/graph_test.hpp
branchSymbian2
changeset 2 2fe1408b6811
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/epoc32/include/stdapis/boost/graph/graph_test.hpp	Tue Mar 16 16:12:26 2010 +0000
     1.3 @@ -0,0 +1,382 @@
     1.4 +//=======================================================================
     1.5 +// Copyright 2002 Indiana University.
     1.6 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
     1.7 +//
     1.8 +// Distributed under the Boost Software License, Version 1.0. (See
     1.9 +// accompanying file LICENSE_1_0.txt or copy at
    1.10 +// http://www.boost.org/LICENSE_1_0.txt)
    1.11 +//=======================================================================
    1.12 +
    1.13 +#ifndef BOOST_GRAPH_TEST_HPP
    1.14 +#define BOOST_GRAPH_TEST_HPP
    1.15 +
    1.16 +#include <vector>
    1.17 +#include <boost/test/minimal.hpp>
    1.18 +#include <boost/graph/filtered_graph.hpp>
    1.19 +#include <boost/graph/iteration_macros.hpp>
    1.20 +#include <boost/graph/isomorphism.hpp>
    1.21 +#include <boost/graph/copy.hpp>
    1.22 +#include <boost/graph/graph_utility.hpp> // for connects
    1.23 +
    1.24 +
    1.25 +// UNDER CONSTRUCTION 
    1.26 +
    1.27 +namespace boost {
    1.28 +
    1.29 +  template <typename Graph>
    1.30 +  struct graph_test
    1.31 +  {
    1.32 +  
    1.33 +    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
    1.34 +    typedef typename graph_traits<Graph>::edge_descriptor edge_t;
    1.35 +    typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
    1.36 +    typedef typename graph_traits<Graph>::degree_size_type deg_size_t;
    1.37 +    typedef typename graph_traits<Graph>::edges_size_type e_size_t;
    1.38 +    typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iter;
    1.39 +    typedef typename property_map<Graph, vertex_index_t>::type index_map_t;
    1.40 +    typedef iterator_property_map<typename std::vector<vertex_t>::iterator,
    1.41 +      index_map_t,vertex_t,vertex_t&> IsoMap;
    1.42 +
    1.43 +    struct ignore_vertex {
    1.44 +      ignore_vertex() { }
    1.45 +      ignore_vertex(vertex_t v) : v(v) { }
    1.46 +      bool operator()(vertex_t x) const { return x != v; }
    1.47 +      vertex_t v;
    1.48 +    };
    1.49 +    struct ignore_edge {
    1.50 +      ignore_edge() { }
    1.51 +      ignore_edge(edge_t e) : e(e) { }
    1.52 +      bool operator()(edge_t x) const { return x != e; }
    1.53 +      edge_t e;
    1.54 +    };
    1.55 +    struct ignore_edges {
    1.56 +      ignore_edges(vertex_t s, vertex_t t, const Graph& g) 
    1.57 +        : s(s), t(t), g(g) { }
    1.58 +      bool operator()(edge_t x) const { 
    1.59 +        return !(source(x, g) == s && target(x, g) == t);
    1.60 +      }
    1.61 +      vertex_t s; vertex_t t; const Graph& g;
    1.62 +    };
    1.63 +
    1.64 +    //=========================================================================
    1.65 +    // Traversal Operations
    1.66 +
    1.67 +    void test_incidence_graph
    1.68 +       (const std::vector<vertex_t>& vertex_set,
    1.69 +        const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,
    1.70 +        const Graph& g)
    1.71 +    {
    1.72 +      typedef typename std::vector<vertex_t>::const_iterator vertex_iter;
    1.73 +      typedef typename std::vector< std::pair<vertex_t, vertex_t> >
    1.74 +        ::const_iterator edge_iter;
    1.75 +      typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iter;
    1.76 +
    1.77 +      for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) {
    1.78 +        vertex_t u = *ui;
    1.79 +        std::vector<vertex_t> adj;
    1.80 +        for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e)
    1.81 +          if (e->first == u)
    1.82 +            adj.push_back(e->second);
    1.83 +        
    1.84 +        std::pair<out_edge_iter, out_edge_iter> p = out_edges(u, g);
    1.85 +        BOOST_CHECK(out_degree(u, g) == adj.size());
    1.86 +        BOOST_CHECK(deg_size_t(std::distance(p.first, p.second))
    1.87 +                   == out_degree(u, g));
    1.88 +        for (; p.first != p.second; ++p.first) {
    1.89 +          edge_t e = *p.first;
    1.90 +          BOOST_CHECK(source(e, g) == u);
    1.91 +          BOOST_CHECK(contains(adj, target(e, g)) == true);
    1.92 +        }
    1.93 +      }
    1.94 +    }
    1.95 +
    1.96 +    void test_bidirectional_graph
    1.97 +      (const std::vector<vertex_t>& vertex_set,
    1.98 +       const std::vector< std::pair<vertex_t, vertex_t> >& edge_set,
    1.99 +       const Graph& g)
   1.100 +    {
   1.101 +      typedef typename std::vector<vertex_t>::const_iterator vertex_iter;
   1.102 +      typedef typename std::vector< std::pair<vertex_t, vertex_t> >
   1.103 +        ::const_iterator edge_iter;
   1.104 +      typedef typename graph_traits<Graph>::in_edge_iterator in_edge_iter;
   1.105 +
   1.106 +      for (vertex_iter vi = vertex_set.begin(); vi != vertex_set.end(); ++vi) {
   1.107 +        vertex_t v = *vi;
   1.108 +        std::vector<vertex_t> inv_adj;
   1.109 +        for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e)
   1.110 +          if (e->second == v)
   1.111 +            inv_adj.push_back(e->first);
   1.112 +
   1.113 +        std::pair<in_edge_iter, in_edge_iter> p = in_edges(v, g);
   1.114 +        BOOST_CHECK(in_degree(v, g) == inv_adj.size());
   1.115 +        BOOST_CHECK(deg_size_t(std::distance(p.first, p.second))
   1.116 +                   == in_degree(v, g));
   1.117 +        for (; p.first != p.second; ++p.first) {
   1.118 +          edge_t e = *p.first;
   1.119 +          BOOST_CHECK(target(e, g) == v);
   1.120 +          BOOST_CHECK(contains(inv_adj, source(e, g)) == true);
   1.121 +        }
   1.122 +      }
   1.123 +    }
   1.124 +
   1.125 +    void test_adjacency_graph
   1.126 +      (const std::vector<vertex_t>& vertex_set,
   1.127 +       const std::vector< std::pair<vertex_t,vertex_t> >& edge_set,
   1.128 +       const Graph& g)
   1.129 +    {
   1.130 +      typedef typename std::vector<vertex_t>::const_iterator vertex_iter;
   1.131 +      typedef typename std::vector<std::pair<vertex_t,vertex_t> >
   1.132 +        ::const_iterator edge_iter;
   1.133 +      typedef typename graph_traits<Graph>::adjacency_iterator adj_iter;
   1.134 +
   1.135 +      for (vertex_iter ui = vertex_set.begin(); ui != vertex_set.end(); ++ui) {
   1.136 +        vertex_t u = *ui;
   1.137 +        std::vector<vertex_t> adj;
   1.138 +        for (edge_iter e = edge_set.begin(); e != edge_set.end(); ++e)
   1.139 +          if (e->first == u)
   1.140 +            adj.push_back(e->second);
   1.141 +
   1.142 +        std::pair<adj_iter, adj_iter> p = adjacent_vertices(u, g);
   1.143 +        BOOST_CHECK(deg_size_t(std::distance(p.first, p.second)) == adj.size());
   1.144 +        for (; p.first != p.second; ++p.first) {
   1.145 +          vertex_t v = *p.first;
   1.146 +          BOOST_CHECK(contains(adj, v) == true);
   1.147 +        }
   1.148 +      }
   1.149 +    }      
   1.150 +
   1.151 +    void test_vertex_list_graph
   1.152 +      (const std::vector<vertex_t>& vertex_set, const Graph& g)
   1.153 +    {
   1.154 +      typedef typename graph_traits<Graph>::vertex_iterator v_iter;
   1.155 +      std::pair<v_iter, v_iter> p = vertices(g);
   1.156 +      BOOST_CHECK(num_vertices(g) == vertex_set.size());
   1.157 +      v_size_t n = std::distance(p.first, p.second);
   1.158 +      BOOST_CHECK(n == num_vertices(g));
   1.159 +      for (; p.first != p.second; ++p.first) {
   1.160 +        vertex_t v = *p.first;
   1.161 +        BOOST_CHECK(contains(vertex_set, v) == true);
   1.162 +      }
   1.163 +    }
   1.164 +
   1.165 +    void test_edge_list_graph
   1.166 +      (const std::vector<vertex_t>& vertex_set, 
   1.167 +       const std::vector< std::pair<vertex_t, vertex_t> >& edge_set, 
   1.168 +       const Graph& g)
   1.169 +    {
   1.170 +      typedef typename graph_traits<Graph>::edge_iterator e_iter;
   1.171 +      std::pair<e_iter, e_iter> p = edges(g);
   1.172 +      BOOST_CHECK(num_edges(g) == edge_set.size());
   1.173 +      e_size_t m = std::distance(p.first, p.second);
   1.174 +      BOOST_CHECK(m == num_edges(g));
   1.175 +      for (; p.first != p.second; ++p.first) {
   1.176 +        edge_t e = *p.first;
   1.177 +        BOOST_CHECK(any_if(edge_set, connects(source(e, g), target(e, g), g)));
   1.178 +        BOOST_CHECK(contains(vertex_set, source(e, g)) == true);
   1.179 +        BOOST_CHECK(contains(vertex_set, target(e, g)) == true);
   1.180 +      }
   1.181 +    }
   1.182 +
   1.183 +    void test_adjacency_matrix
   1.184 +      (const std::vector<vertex_t>& vertex_set, 
   1.185 +       const std::vector< std::pair<vertex_t, vertex_t> >& edge_set, 
   1.186 +       const Graph& g)
   1.187 +    {
   1.188 +      std::pair<edge_t, bool> p;
   1.189 +      for (typename std::vector<std::pair<vertex_t, vertex_t> >
   1.190 +             ::const_iterator i = edge_set.begin();
   1.191 +           i != edge_set.end(); ++i) {
   1.192 +        p = edge(i->first, i->second, g);
   1.193 +        BOOST_CHECK(p.second == true);
   1.194 +        BOOST_CHECK(source(p.first, g) == i->first);
   1.195 +        BOOST_CHECK(target(p.first, g) == i->second);
   1.196 +      }
   1.197 +      typename std::vector<vertex_t>::const_iterator j, k;
   1.198 +      for (j = vertex_set.begin(); j != vertex_set.end(); ++j)
   1.199 +        for (k = vertex_set.begin(); k != vertex_set.end(); ++k) {
   1.200 +          p = edge(*j, *k, g);
   1.201 +          if (p.second == true)
   1.202 +            BOOST_CHECK(any_if(edge_set, 
   1.203 +              connects(source(p.first, g), target(p.first, g), g)) == true);
   1.204 +        }
   1.205 +    }
   1.206 +
   1.207 +    //=========================================================================
   1.208 +    // Mutating Operations
   1.209 +
   1.210 +    void test_add_vertex(Graph& g)
   1.211 +    {
   1.212 +      Graph cpy;
   1.213 +      std::vector<vertex_t> iso_vec(num_vertices(g));
   1.214 +      IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
   1.215 +      copy_graph(g, cpy, orig_to_copy(iso_map));
   1.216 +
   1.217 +      assert((verify_isomorphism(g, cpy, iso_map)));
   1.218 +
   1.219 +      vertex_t v = add_vertex(g);
   1.220 +      
   1.221 +      BOOST_CHECK(num_vertices(g) == num_vertices(cpy) + 1);
   1.222 +
   1.223 +      BOOST_CHECK(out_degree(v, g) == 0);
   1.224 +
   1.225 +      // Make sure the rest of the graph stayed the same
   1.226 +      BOOST_CHECK((verify_isomorphism
   1.227 +                  (make_filtered_graph(g, keep_all(), ignore_vertex(v)), cpy,
   1.228 +                   iso_map)));
   1.229 +    }
   1.230 +    
   1.231 +    void test_add_edge(vertex_t u, vertex_t v, Graph& g)
   1.232 +    {
   1.233 +      Graph cpy;
   1.234 +      std::vector<vertex_t> iso_vec(num_vertices(g));
   1.235 +      IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
   1.236 +      copy_graph(g, cpy, orig_to_copy(iso_map));
   1.237 +
   1.238 +      bool parallel_edge_exists = contains(adjacent_vertices(u, g), v);
   1.239 +      
   1.240 +      std::pair<edge_t, bool> p = add_edge(u, v, g);
   1.241 +      edge_t e = p.first;
   1.242 +      bool added = p.second;
   1.243 +
   1.244 +      if (is_undirected(g) && u == v) // self edge
   1.245 +        BOOST_CHECK(added == false);
   1.246 +      else if (parallel_edge_exists)
   1.247 +        BOOST_CHECK(allows_parallel_edges(g) && added == true
   1.248 +                   || !allows_parallel_edges(g) && added == false);
   1.249 +      else
   1.250 +        BOOST_CHECK(added == true);
   1.251 +
   1.252 +      if (p.second == true) { // edge added
   1.253 +        BOOST_CHECK(num_edges(g) == num_edges(cpy) + 1);
   1.254 +        
   1.255 +        BOOST_CHECK(contains(out_edges(u, g), e) == true);
   1.256 +        
   1.257 +        BOOST_CHECK((verify_isomorphism
   1.258 +                    (make_filtered_graph(g, ignore_edge(e)), cpy, iso_map)));
   1.259 +      }
   1.260 +      else { // edge not added
   1.261 +        if (! (is_undirected(g) && u == v)) {
   1.262 +          // e should be a parallel edge
   1.263 +          BOOST_CHECK(source(e, g) == u);
   1.264 +          BOOST_CHECK(target(e, g) == v);
   1.265 +        }
   1.266 +        // The graph should not be changed.
   1.267 +        BOOST_CHECK((verify_isomorphism(g, cpy, iso_map)));
   1.268 +      }
   1.269 +    } // test_add_edge()
   1.270 +
   1.271 +
   1.272 +    void test_remove_edge(vertex_t u, vertex_t v, Graph& g)
   1.273 +    {
   1.274 +      Graph cpy;
   1.275 +      std::vector<vertex_t> iso_vec(num_vertices(g));
   1.276 +      IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
   1.277 +      copy_graph(g, cpy, orig_to_copy(iso_map));
   1.278 +
   1.279 +      deg_size_t occurances = count(adjacent_vertices(u, g), v);
   1.280 +
   1.281 +      remove_edge(u, v, g);
   1.282 +      
   1.283 +      BOOST_CHECK(num_edges(g) + occurances == num_edges(cpy));
   1.284 +      BOOST_CHECK((verify_isomorphism
   1.285 +                  (g, make_filtered_graph(cpy, ignore_edges(u,v,cpy)),
   1.286 +                   iso_map)));
   1.287 +    }
   1.288 +
   1.289 +    void test_remove_edge(edge_t e, Graph& g)
   1.290 +    {
   1.291 +      Graph cpy;
   1.292 +      std::vector<vertex_t> iso_vec(num_vertices(g));
   1.293 +      IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
   1.294 +      copy_graph(g, cpy, orig_to_copy(iso_map));
   1.295 +
   1.296 +      vertex_t u = source(e, g), v = target(e, g);
   1.297 +      deg_size_t occurances = count(adjacent_vertices(u, g), v);
   1.298 +      
   1.299 +      remove_edge(e, g);
   1.300 +
   1.301 +      BOOST_CHECK(num_edges(g) + 1 == num_edges(cpy));
   1.302 +      BOOST_CHECK(count(adjacent_vertices(u, g), v) + 1 == occurances);
   1.303 +      BOOST_CHECK((verify_isomorphism
   1.304 +                  (g, make_filtered_graph(cpy, ignore_edge(e)),
   1.305 +                   iso_map)));
   1.306 +    }
   1.307 +
   1.308 +    void test_clear_vertex(vertex_t v, Graph& g)
   1.309 +    {
   1.310 +      Graph cpy;
   1.311 +      std::vector<vertex_t> iso_vec(num_vertices(g));
   1.312 +      IsoMap iso_map(iso_vec.begin(), get(vertex_index, g));
   1.313 +      copy_graph(g, cpy, orig_to_copy(iso_map));
   1.314 +
   1.315 +      clear_vertex(v, g);
   1.316 +
   1.317 +      BOOST_CHECK(out_degree(v, g) == 0);
   1.318 +      BOOST_CHECK(num_vertices(g) == num_vertices(cpy));
   1.319 +      BOOST_CHECK((verify_isomorphism
   1.320 +                  (g, make_filtered_graph(cpy, keep_all(), ignore_vertex(v)),
   1.321 +                   iso_map)));
   1.322 +    }
   1.323 +
   1.324 +    //=========================================================================
   1.325 +    // Property Map
   1.326 +
   1.327 +    template <typename PropVal, typename PropertyTag>
   1.328 +    void test_readable_vertex_property_graph
   1.329 +      (const std::vector<PropVal>& vertex_prop, PropertyTag, const Graph& g)
   1.330 +    {
   1.331 +      typedef typename property_map<Graph, PropertyTag>::const_type const_Map;
   1.332 +      const_Map pmap = get(PropertyTag(), g);
   1.333 +      typename std::vector<PropVal>::const_iterator i = vertex_prop.begin();
   1.334 +
   1.335 +  for (typename boost::graph_traits<Graph>::vertex_iterator 
   1.336 +           bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second;
   1.337 +       bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9)
   1.338 +    for (typename boost::graph_traits<Graph>::vertex_descriptor v;
   1.339 +         bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false;
   1.340 +         ++bgl_first_9) {
   1.341 +      //BGL_FORALL_VERTICES_T(v, g, Graph) {
   1.342 +        typename property_traits<const_Map>::value_type 
   1.343 +          pval1 = get(pmap, v), pval2 = get(PropertyTag(), g, v);
   1.344 +        BOOST_CHECK(pval1 == pval2);
   1.345 +        BOOST_CHECK(pval1 == *i++);
   1.346 +      }
   1.347 +    }
   1.348 +
   1.349 +    template <typename PropVal, typename PropertyTag>
   1.350 +    void test_vertex_property_graph
   1.351 +      (const std::vector<PropVal>& vertex_prop, PropertyTag tag, Graph& g)
   1.352 +    {
   1.353 +      typedef typename property_map<Graph, PropertyTag>::type PMap;
   1.354 +      PMap pmap = get(PropertyTag(), g);
   1.355 +      typename std::vector<PropVal>::const_iterator i = vertex_prop.begin();
   1.356 +  for (typename boost::graph_traits<Graph>::vertex_iterator 
   1.357 +           bgl_first_9 = vertices(g).first, bgl_last_9 = vertices(g).second;
   1.358 +       bgl_first_9 != bgl_last_9; bgl_first_9 = bgl_last_9)
   1.359 +    for (typename boost::graph_traits<Graph>::vertex_descriptor v;
   1.360 +         bgl_first_9 != bgl_last_9 ? (v = *bgl_first_9, true) : false;
   1.361 +         ++bgl_first_9)
   1.362 +      //      BGL_FORALL_VERTICES_T(v, g, Graph)
   1.363 +        put(pmap, v, *i++);
   1.364 +
   1.365 +      test_readable_vertex_property_graph(vertex_prop, tag, g);
   1.366 +
   1.367 +      BGL_FORALL_VERTICES_T(v, g, Graph)
   1.368 +        put(pmap, v, vertex_prop[0]);
   1.369 +      
   1.370 +      typename std::vector<PropVal>::const_iterator j = vertex_prop.begin();
   1.371 +      BGL_FORALL_VERTICES_T(v, g, Graph)
   1.372 +        put(PropertyTag(), g, v, *j++);
   1.373 +      
   1.374 +      test_readable_vertex_property_graph(vertex_prop, tag, g);      
   1.375 +    }
   1.376 +    
   1.377 +    
   1.378 +  };
   1.379 +
   1.380 +
   1.381 +} // namespace boost
   1.382 +
   1.383 +#include <boost/graph/iteration_macros_undef.hpp>
   1.384 +
   1.385 +#endif // BOOST_GRAPH_TEST_HPP