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