ceph/src/boost/libs/graph/test/adjacency_matrix_test.cpp

   1 /* adjacency_matrix_test.cpp source file
   2  *
   3  * Copyright Cromwell D. Enage 2004
   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 /*
  11  * Defines the std::ios class and std::cout, its global output instance.
  12  */
  13 #include <iostream>
  14
  15 /*
  16  * Defines the boost::property_map class template and the boost::get and
  17  * boost::put function templates.
  18  */
  19 #include <boost/property_map/property_map.hpp>
  20
  21 /*
  22  * Defines the boost::graph_traits class template.
  23  */
  24 #include <boost/graph/graph_traits.hpp>
  25
  26 /*
  27  * Defines the vertex and edge property tags.
  28  */
  29 #include <boost/graph/properties.hpp>
  30
  31 /*
  32  * Defines the boost::adjacency_list class template and its associated
  33  * non-member function templates.
  34  */
  35 #include <boost/graph/adjacency_list.hpp>
  36
  37 /*
  38  * Defines the boost::adjacency_matrix class template and its associated
  39  * non-member function templates.
  40  */
  41 #include <boost/graph/adjacency_matrix.hpp>
  42
  43 #include <boost/test/minimal.hpp>
  44
  45 #include <vector>
  46 #include <algorithm> // For std::sort
  47 #include <boost/type_traits/is_convertible.hpp>
  48
  49 #include <boost/graph/iteration_macros.hpp>
  50
  51 template<typename Graph1, typename Graph2>
  52 void run_test()
  53 {
  54    typedef typename boost::property_map<Graph1, boost::vertex_index_t>::type
  55            IndexMap1;
  56    typedef typename boost::property_map<Graph2, boost::vertex_index_t>::type
  57            IndexMap2;
  58
  59    Graph1 g1(24);
  60    Graph2 g2(24);
  61
  62 boost::add_edge(boost::vertex(1, g1), boost::vertex(2, g1), g1);
  63    boost::add_edge(boost::vertex(1, g2), boost::vertex(2, g2), g2);
  64    boost::add_edge(boost::vertex(2, g1), boost::vertex(10, g1), g1);
  65    boost::add_edge(boost::vertex(2, g2), boost::vertex(10, g2), g2);
  66    boost::add_edge(boost::vertex(2, g1), boost::vertex(5, g1), g1);
  67    boost::add_edge(boost::vertex(2, g2), boost::vertex(5, g2), g2);
  68    boost::add_edge(boost::vertex(3, g1), boost::vertex(10, g1), g1);
  69    boost::add_edge(boost::vertex(3, g2), boost::vertex(10, g2), g2);
  70    boost::add_edge(boost::vertex(3, g1), boost::vertex(0, g1), g1);
  71    boost::add_edge(boost::vertex(3, g2), boost::vertex(0, g2), g2);
  72    boost::add_edge(boost::vertex(4, g1), boost::vertex(5, g1), g1);
  73    boost::add_edge(boost::vertex(4, g2), boost::vertex(5, g2), g2);
  74    boost::add_edge(boost::vertex(4, g1), boost::vertex(0, g1), g1);
  75    boost::add_edge(boost::vertex(4, g2), boost::vertex(0, g2), g2);
  76    boost::add_edge(boost::vertex(5, g1), boost::vertex(14, g1), g1);
  77    boost::add_edge(boost::vertex(5, g2), boost::vertex(14, g2), g2);
  78    boost::add_edge(boost::vertex(6, g1), boost::vertex(3, g1), g1);
  79    boost::add_edge(boost::vertex(6, g2), boost::vertex(3, g2), g2);
  80    boost::add_edge(boost::vertex(7, g1), boost::vertex(17, g1), g1);
  81    boost::add_edge(boost::vertex(7, g2), boost::vertex(17, g2), g2);
  82    boost::add_edge(boost::vertex(7, g1), boost::vertex(11, g1), g1);
  83    boost::add_edge(boost::vertex(7, g2), boost::vertex(11, g2), g2);
  84    boost::add_edge(boost::vertex(8, g1), boost::vertex(17, g1), g1);
  85    boost::add_edge(boost::vertex(8, g2), boost::vertex(17, g2), g2);
  86    boost::add_edge(boost::vertex(8, g1), boost::vertex(1, g1), g1);
  87    boost::add_edge(boost::vertex(8, g2), boost::vertex(1, g2), g2);
  88    boost::add_edge(boost::vertex(9, g1), boost::vertex(11, g1), g1);
  89    boost::add_edge(boost::vertex(9, g2), boost::vertex(11, g2), g2);
  90    boost::add_edge(boost::vertex(9, g1), boost::vertex(1, g1), g1);
  91    boost::add_edge(boost::vertex(9, g2), boost::vertex(1, g2), g2);
  92    boost::add_edge(boost::vertex(10, g1), boost::vertex(19, g1), g1);
  93    boost::add_edge(boost::vertex(10, g2), boost::vertex(19, g2), g2);
  94    boost::add_edge(boost::vertex(10, g1), boost::vertex(15, g1), g1);
  95    boost::add_edge(boost::vertex(10, g2), boost::vertex(15, g2), g2);
  96    boost::add_edge(boost::vertex(10, g1), boost::vertex(8, g1), g1);
  97    boost::add_edge(boost::vertex(10, g2), boost::vertex(8, g2), g2);
  98    boost::add_edge(boost::vertex(11, g1), boost::vertex(19, g1), g1);
  99    boost::add_edge(boost::vertex(11, g2), boost::vertex(19, g2), g2);
 100    boost::add_edge(boost::vertex(11, g1), boost::vertex(15, g1), g1);
 101    boost::add_edge(boost::vertex(11, g2), boost::vertex(15, g2), g2);
 102    boost::add_edge(boost::vertex(11, g1), boost::vertex(4, g1), g1);
 103    boost::add_edge(boost::vertex(11, g2), boost::vertex(4, g2), g2);
 104    boost::add_edge(boost::vertex(12, g1), boost::vertex(19, g1), g1);
 105    boost::add_edge(boost::vertex(12, g2), boost::vertex(19, g2), g2);
 106    boost::add_edge(boost::vertex(12, g1), boost::vertex(8, g1), g1);
 107    boost::add_edge(boost::vertex(12, g2), boost::vertex(8, g2), g2);
 108    boost::add_edge(boost::vertex(12, g1), boost::vertex(4, g1), g1);
 109    boost::add_edge(boost::vertex(12, g2), boost::vertex(4, g2), g2);
 110    boost::add_edge(boost::vertex(13, g1), boost::vertex(15, g1), g1);
 111    boost::add_edge(boost::vertex(13, g2), boost::vertex(15, g2), g2);
 112    boost::add_edge(boost::vertex(13, g1), boost::vertex(8, g1), g1);
 113    boost::add_edge(boost::vertex(13, g2), boost::vertex(8, g2), g2);
 114    boost::add_edge(boost::vertex(13, g1), boost::vertex(4, g1), g1);
 115    boost::add_edge(boost::vertex(13, g2), boost::vertex(4, g2), g2);
 116    boost::add_edge(boost::vertex(14, g1), boost::vertex(22, g1), g1);
 117    boost::add_edge(boost::vertex(14, g2), boost::vertex(22, g2), g2);
 118    boost::add_edge(boost::vertex(14, g1), boost::vertex(12, g1), g1);
 119    boost::add_edge(boost::vertex(14, g2), boost::vertex(12, g2), g2);
 120    boost::add_edge(boost::vertex(15, g1), boost::vertex(22, g1), g1);
 121    boost::add_edge(boost::vertex(15, g2), boost::vertex(22, g2), g2);
 122    boost::add_edge(boost::vertex(15, g1), boost::vertex(6, g1), g1);
 123    boost::add_edge(boost::vertex(15, g2), boost::vertex(6, g2), g2);
 124    boost::add_edge(boost::vertex(16, g1), boost::vertex(12, g1), g1);
 125    boost::add_edge(boost::vertex(16, g2), boost::vertex(12, g2), g2);
 126    boost::add_edge(boost::vertex(16, g1), boost::vertex(6, g1), g1);
 127    boost::add_edge(boost::vertex(16, g2), boost::vertex(6, g2), g2);
 128    boost::add_edge(boost::vertex(17, g1), boost::vertex(20, g1), g1);
 129    boost::add_edge(boost::vertex(17, g2), boost::vertex(20, g2), g2);
 130    boost::add_edge(boost::vertex(18, g1), boost::vertex(9, g1), g1);
 131    boost::add_edge(boost::vertex(18, g2), boost::vertex(9, g2), g2);
 132    boost::add_edge(boost::vertex(19, g1), boost::vertex(23, g1), g1);
 133    boost::add_edge(boost::vertex(19, g2), boost::vertex(23, g2), g2);
 134    boost::add_edge(boost::vertex(19, g1), boost::vertex(18, g1), g1);
 135    boost::add_edge(boost::vertex(19, g2), boost::vertex(18, g2), g2);
 136    boost::add_edge(boost::vertex(20, g1), boost::vertex(23, g1), g1);
 137    boost::add_edge(boost::vertex(20, g2), boost::vertex(23, g2), g2);
 138    boost::add_edge(boost::vertex(20, g1), boost::vertex(13, g1), g1);
 139    boost::add_edge(boost::vertex(20, g2), boost::vertex(13, g2), g2);
 140    boost::add_edge(boost::vertex(21, g1), boost::vertex(18, g1), g1);
 141    boost::add_edge(boost::vertex(21, g2), boost::vertex(18, g2), g2);
 142    boost::add_edge(boost::vertex(21, g1), boost::vertex(13, g1), g1);
 143    boost::add_edge(boost::vertex(21, g2), boost::vertex(13, g2), g2);
 144    boost::add_edge(boost::vertex(22, g1), boost::vertex(21, g1), g1);
 145    boost::add_edge(boost::vertex(22, g2), boost::vertex(21, g2), g2);
 146    boost::add_edge(boost::vertex(23, g1), boost::vertex(16, g1), g1);
 147    boost::add_edge(boost::vertex(23, g2), boost::vertex(16, g2), g2);
 148
 149    IndexMap1 index_map1 = boost::get(boost::vertex_index_t(), g1);
 150    IndexMap2 index_map2 = boost::get(boost::vertex_index_t(), g2);
 151    typename boost::graph_traits<Graph1>::vertex_iterator vi1, vend1;
 152    typename boost::graph_traits<Graph2>::vertex_iterator vi2, vend2;
 153
 154    typename boost::graph_traits<Graph1>::adjacency_iterator ai1, aend1;
 155    typename boost::graph_traits<Graph2>::adjacency_iterator ai2, aend2;
 156
 157    for (boost::tie(vi1, vend1) = boost::vertices(g1), boost::tie(vi2, vend2) =boost::vertices(g2); vi1 != vend1; ++vi1, ++vi2)
 158    {
 159       BOOST_CHECK(boost::get(index_map1, *vi1) == boost::get(index_map2, *vi2));
 160
 161       for (boost::tie(ai1, aend1) = boost::adjacent_vertices(*vi1, g1),
 162              boost::tie(ai2, aend2) = boost::adjacent_vertices(*vi2, g2);
 163            ai1 != aend1;
 164            ++ai1, ++ai2)
 165       {
 166         BOOST_CHECK(boost::get(index_map1, *ai1) == boost::get(index_map2, *ai2));
 167       }
 168    }
 169
 170    typename boost::graph_traits<Graph1>::out_edge_iterator ei1, eend1;
 171    typename boost::graph_traits<Graph2>::out_edge_iterator ei2, eend2;
 172
 173    for (boost::tie(vi1, vend1) = boost::vertices(g1),
 174           boost::tie(vi2, vend2) = boost::vertices(g2); vi1 != vend1; ++vi1, ++vi2)
 175    {
 176       BOOST_CHECK(boost::get(index_map1, *vi1) == boost::get(index_map2, *vi2));
 177
 178       for (boost::tie(ei1, eend1) = boost::out_edges(*vi1, g1),
 179              boost::tie(ei2, eend2) = boost::out_edges(*vi2, g2);
 180            ei1 != eend1;
 181            ++ei1, ++ei2)
 182       {
 183         BOOST_CHECK(boost::get(index_map1, boost::target(*ei1, g1)) == boost::get(index_map2, boost::target(*ei2, g2)));
 184       }
 185    }
 186
 187    typename boost::graph_traits<Graph1>::in_edge_iterator iei1, ieend1;
 188    typename boost::graph_traits<Graph2>::in_edge_iterator iei2, ieend2;
 189
 190    for (boost::tie(vi1, vend1) = boost::vertices(g1),
 191           boost::tie(vi2, vend2) = boost::vertices(g2); vi1 != vend1; ++vi1, ++vi2)
 192    {
 193       BOOST_CHECK(boost::get(index_map1, *vi1) == boost::get(index_map2, *vi2));
 194
 195       for (boost::tie(iei1, ieend1) = boost::in_edges(*vi1, g1),
 196              boost::tie(iei2, ieend2) = boost::in_edges(*vi2, g2);
 197            iei1 != ieend1;
 198            ++iei1, ++iei2)
 199       {
 200         BOOST_CHECK(boost::get(index_map1, boost::target(*iei1, g1)) == boost::get(index_map2, boost::target(*iei2, g2)));
 201       }
 202    }
 203
 204    // Test construction from a range of pairs
 205    std::vector<std::pair<int, int> > edge_pairs_g1;
 206    BGL_FORALL_EDGES_T(e, g1, Graph1) {
 207      edge_pairs_g1.push_back(
 208        std::make_pair(get(index_map1, source(e, g1)),
 209                       get(index_map1, target(e, g1))));
 210    }
 211    Graph2 g3(edge_pairs_g1.begin(), edge_pairs_g1.end(), num_vertices(g1));
 212    BOOST_CHECK(num_vertices(g1) == num_vertices(g3));
 213    std::vector<std::pair<int, int> > edge_pairs_g3;
 214    IndexMap2 index_map3 = boost::get(boost::vertex_index_t(), g3);
 215    BGL_FORALL_EDGES_T(e, g3, Graph2) {
 216      edge_pairs_g3.push_back(
 217        std::make_pair(get(index_map3, source(e, g3)),
 218                       get(index_map3, target(e, g3))));
 219    }
 220    // Normalize the edge pairs for comparison
 221    if (boost::is_convertible<typename boost::graph_traits<Graph1>::directed_category*, boost::undirected_tag*>::value || boost::is_convertible<typename boost::graph_traits<Graph2>::directed_category*, boost::undirected_tag*>::value) {
 222      for (size_t i = 0; i < edge_pairs_g1.size(); ++i) {
 223        if (edge_pairs_g1[i].first < edge_pairs_g1[i].second) {
 224          std::swap(edge_pairs_g1[i].first, edge_pairs_g1[i].second);
 225        }
 226      }
 227      for (size_t i = 0; i < edge_pairs_g3.size(); ++i) {
 228        if (edge_pairs_g3[i].first < edge_pairs_g3[i].second) {
 229          std::swap(edge_pairs_g3[i].first, edge_pairs_g3[i].second);
 230        }
 231      }
 232    }
 233    std::sort(edge_pairs_g1.begin(), edge_pairs_g1.end());
 234    std::sort(edge_pairs_g3.begin(), edge_pairs_g3.end());
 235    edge_pairs_g1.erase(std::unique(edge_pairs_g1.begin(), edge_pairs_g1.end()), edge_pairs_g1.end());
 236    edge_pairs_g3.erase(std::unique(edge_pairs_g3.begin(), edge_pairs_g3.end()), edge_pairs_g3.end());
 237    BOOST_CHECK(edge_pairs_g1 == edge_pairs_g3);
 238 }
 239
 240 template <typename Graph>
 241 void test_remove_edges()
 242 {
 243     using namespace boost;
 244
 245     // Build a 2-vertex graph
 246     Graph g(2);
 247     add_edge(vertex(0, g), vertex(1, g), g);
 248     BOOST_CHECK(num_vertices(g) == 2);
 249     BOOST_CHECK(num_edges(g) == 1);
 250     remove_edge(vertex(0, g), vertex(1, g), g);
 251     BOOST_CHECK(num_edges(g) == 0);
 252
 253     // Make sure we don't decrement the edge count if the edge doesn't actually
 254     // exist.
 255     remove_edge(vertex(0, g), vertex(1, g), g);
 256     BOOST_CHECK(num_edges(g) == 0);
 257 }
 258
 259
 260 int test_main(int, char*[])
 261 {
 262         // Use setS to keep out edges in order, so they match the adjacency_matrix.
 263     typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS>
 264             UGraph1;
 265     typedef boost::adjacency_matrix<boost::undirectedS>
 266             UGraph2;
 267     run_test<UGraph1, UGraph2>();
 268
 269         // Use setS to keep out edges in order, so they match the adjacency_matrix.
 270     typedef boost::adjacency_list<boost::setS, boost::vecS,
 271                                     boost::bidirectionalS>
 272             BGraph1;
 273     typedef boost::adjacency_matrix<boost::directedS>
 274             BGraph2;
 275     run_test<BGraph1, BGraph2>();
 276
 277     test_remove_edges<UGraph2>();
 278     test_remove_edges<BGraph2>();
 279
 280     return 0;
 281 }
 282