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

   1 //=======================================================================
   2 // Copyright 2007 Aaron Windsor
   3 //
   4 // Distributed under the Boost Software License, Version 1.0. (See
   5 // accompanying file LICENSE_1_0.txt or copy at
   6 // http://www.boost.org/LICENSE_1_0.txt)
   7 //=======================================================================
   8
   9 #include <boost/graph/adjacency_list.hpp>
  10 #include <boost/graph/properties.hpp>
  11 #include <boost/graph/make_biconnected_planar.hpp>
  12 #include <boost/graph/biconnected_components.hpp>
  13 #include <boost/graph/boyer_myrvold_planar_test.hpp>
  14 #include <boost/property_map/property_map.hpp>
  15 #include <boost/property_map/vector_property_map.hpp>
  16 #include <boost/test/minimal.hpp>
  17
  18
  19 using namespace boost;
  20
  21
  22 template <typename Graph>
  23 void reset_edge_index(Graph& g)
  24 {
  25   typename property_map<Graph, edge_index_t>::type index = get(edge_index, g);
  26   typename graph_traits<Graph>::edge_iterator ei, ei_end;
  27   typename graph_traits<Graph>::edges_size_type cnt = 0;
  28   for(boost::tie(ei,ei_end) = edges(g); ei != ei_end; ++ei)
  29     put(index, *ei, cnt++);
  30 }
  31
  32
  33 template <typename Graph>
  34 void make_line_graph(Graph& g, int size)
  35 {
  36   typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
  37
  38   vertex_t prev_vertex = add_vertex(g);
  39
  40   for(int i = 1; i < size; ++i)
  41     {
  42       vertex_t curr_vertex = add_vertex(g);
  43       add_edge(curr_vertex, prev_vertex, g);
  44       prev_vertex = curr_vertex;
  45     }
  46 }
  47
  48
  49 struct UpdateVertexIndex
  50 {
  51   template <typename Graph>
  52   void update(Graph& g)
  53   {
  54     typename property_map<Graph, vertex_index_t>::type index = get(vertex_index, g);
  55     typename graph_traits<Graph>::vertex_iterator vi, vi_end;
  56     typename graph_traits<Graph>::vertices_size_type cnt = 0;
  57     for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
  58       put(index, *vi, cnt++);
  59   }
  60 };
  61
  62
  63 struct NoVertexIndexUpdater
  64 {
  65   template <typename Graph> void update(Graph&) {}
  66 };
  67
  68
  69
  70 template <typename Graph, typename VertexIndexUpdater>
  71 void test_line_graph(VertexIndexUpdater vertex_index_updater, int size)
  72 {
  73
  74   Graph g;
  75   make_line_graph(g, size);
  76   vertex_index_updater.update(g);
  77   reset_edge_index(g);
  78
  79   typedef std::vector< typename graph_traits<Graph>::edge_descriptor > edge_vector_t;
  80   typedef std::vector< edge_vector_t > embedding_storage_t;
  81   typedef iterator_property_map
  82     < typename embedding_storage_t::iterator,
  83       typename property_map<Graph, vertex_index_t>::type
  84     > embedding_t;
  85
  86   embedding_storage_t embedding_storage(num_vertices(g));
  87   embedding_t embedding(embedding_storage.begin(), get(vertex_index, g));
  88
  89   typename graph_traits<Graph>::vertex_iterator vi, vi_end;
  90   for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
  91     std::copy(out_edges(*vi,g).first, out_edges(*vi,g).second, std::back_inserter(embedding[*vi]));
  92
  93   BOOST_CHECK(biconnected_components(g, make_vector_property_map<int>(get(edge_index,g))) > 1);
  94   BOOST_CHECK(boyer_myrvold_planarity_test(g));
  95   make_biconnected_planar(g, embedding);
  96   reset_edge_index(g);
  97   BOOST_CHECK(biconnected_components(g, make_vector_property_map<int>(get(edge_index,g))) == 1);
  98   BOOST_CHECK(boyer_myrvold_planarity_test(g));
  99
 100 }
 101
 102
 103
 104
 105
 106 int test_main(int, char* [])
 107 {
 108   typedef adjacency_list
 109     <vecS,
 110     vecS,
 111     undirectedS,
 112     property<vertex_index_t, int>,
 113     property<edge_index_t, int>
 114     >
 115     VVgraph_t;
 116
 117   typedef adjacency_list
 118     <vecS,
 119     listS,
 120     undirectedS,
 121     property<vertex_index_t, int>,
 122     property<edge_index_t, int>
 123     >
 124     VLgraph_t;
 125
 126   typedef adjacency_list
 127     <listS,
 128     vecS,
 129     undirectedS,
 130     property<vertex_index_t, int>,
 131     property<edge_index_t, int>
 132     >
 133     LVgraph_t;
 134
 135   typedef adjacency_list
 136     <listS,
 137     listS,
 138     undirectedS,
 139     property<vertex_index_t, int>,
 140     property<edge_index_t, int>
 141     >
 142     LLgraph_t;
 143
 144   typedef adjacency_list
 145     <setS,
 146     setS,
 147     undirectedS,
 148     property<vertex_index_t, int>,
 149     property<edge_index_t, int>
 150     >
 151     SSgraph_t;
 152
 153   test_line_graph<VVgraph_t>(NoVertexIndexUpdater(), 10);
 154   test_line_graph<VVgraph_t>(NoVertexIndexUpdater(), 50);
 155
 156   test_line_graph<VLgraph_t>(UpdateVertexIndex(), 3);
 157   test_line_graph<VLgraph_t>(UpdateVertexIndex(), 30);
 158
 159   test_line_graph<LVgraph_t>(NoVertexIndexUpdater(), 15);
 160   test_line_graph<LVgraph_t>(NoVertexIndexUpdater(), 45);
 161
 162   test_line_graph<LLgraph_t>(UpdateVertexIndex(), 8);
 163   test_line_graph<LLgraph_t>(UpdateVertexIndex(), 19);
 164
 165   test_line_graph<SSgraph_t>(UpdateVertexIndex(), 13);
 166   test_line_graph<SSgraph_t>(UpdateVertexIndex(), 20);
 167
 168   return 0;
 169 }