epoc32/include/stdapis/boost/graph/graph_test.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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