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