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/core/lightweight_test.hpp>
  17
  18 using namespace boost;
  19
  20 template < typename Graph > void reset_edge_index(Graph& g)
  21 {
  22     typename property_map< Graph, edge_index_t >::type index
  23         = get(edge_index, g);
  24     typename graph_traits< Graph >::edge_iterator ei, ei_end;
  25     typename graph_traits< Graph >::edges_size_type cnt = 0;
  26     for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
  27         put(index, *ei, cnt++);
  28 }
  29
  30 template < typename Graph > void make_line_graph(Graph& g, int size)
  31 {
  32     typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
  33
  34     vertex_t prev_vertex = add_vertex(g);
  35
  36     for (int i = 1; i < size; ++i)
  37     {
  38         vertex_t curr_vertex = add_vertex(g);
  39         add_edge(curr_vertex, prev_vertex, g);
  40         prev_vertex = curr_vertex;
  41     }
  42 }
  43
  44 struct UpdateVertexIndex
  45 {
  46     template < typename Graph > void update(Graph& g)
  47     {
  48         typename property_map< Graph, vertex_index_t >::type index
  49             = get(vertex_index, g);
  50         typename graph_traits< Graph >::vertex_iterator vi, vi_end;
  51         typename graph_traits< Graph >::vertices_size_type cnt = 0;
  52         for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
  53             put(index, *vi, cnt++);
  54     }
  55 };
  56
  57 struct NoVertexIndexUpdater
  58 {
  59     template < typename Graph > void update(Graph&) {}
  60 };
  61
  62 template < typename Graph, typename VertexIndexUpdater >
  63 void test_line_graph(VertexIndexUpdater vertex_index_updater, int size)
  64 {
  65
  66     Graph g;
  67     make_line_graph(g, size);
  68     vertex_index_updater.update(g);
  69     reset_edge_index(g);
  70
  71     typedef std::vector< typename graph_traits< Graph >::edge_descriptor >
  72         edge_vector_t;
  73     typedef std::vector< edge_vector_t > embedding_storage_t;
  74     typedef iterator_property_map< typename embedding_storage_t::iterator,
  75         typename property_map< Graph, vertex_index_t >::type >
  76         embedding_t;
  77
  78     embedding_storage_t embedding_storage(num_vertices(g));
  79     embedding_t embedding(embedding_storage.begin(), get(vertex_index, g));
  80
  81     typename graph_traits< Graph >::vertex_iterator vi, vi_end;
  82     for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
  83         std::copy(out_edges(*vi, g).first, out_edges(*vi, g).second,
  84             std::back_inserter(embedding[*vi]));
  85
  86     BOOST_TEST(biconnected_components(
  87                     g, make_vector_property_map< int >(get(edge_index, g)))
  88         > 1);
  89     BOOST_TEST(boyer_myrvold_planarity_test(g));
  90     make_biconnected_planar(g, embedding);
  91     reset_edge_index(g);
  92     BOOST_TEST(biconnected_components(
  93                     g, make_vector_property_map< int >(get(edge_index, g)))
  94         == 1);
  95     BOOST_TEST(boyer_myrvold_planarity_test(g));
  96 }
  97
  98 int main(int, char*[])
  99 {
 100     typedef adjacency_list< vecS, vecS, undirectedS,
 101         property< vertex_index_t, int >, property< edge_index_t, int > >
 102         VVgraph_t;
 103
 104     typedef adjacency_list< vecS, listS, undirectedS,
 105         property< vertex_index_t, int >, property< edge_index_t, int > >
 106         VLgraph_t;
 107
 108     typedef adjacency_list< listS, vecS, undirectedS,
 109         property< vertex_index_t, int >, property< edge_index_t, int > >
 110         LVgraph_t;
 111
 112     typedef adjacency_list< listS, listS, undirectedS,
 113         property< vertex_index_t, int >, property< edge_index_t, int > >
 114         LLgraph_t;
 115
 116     typedef adjacency_list< setS, setS, undirectedS,
 117         property< vertex_index_t, int >, property< edge_index_t, int > >
 118         SSgraph_t;
 119
 120     test_line_graph< VVgraph_t >(NoVertexIndexUpdater(), 10);
 121     test_line_graph< VVgraph_t >(NoVertexIndexUpdater(), 50);
 122
 123     test_line_graph< VLgraph_t >(UpdateVertexIndex(), 3);
 124     test_line_graph< VLgraph_t >(UpdateVertexIndex(), 30);
 125
 126     test_line_graph< LVgraph_t >(NoVertexIndexUpdater(), 15);
 127     test_line_graph< LVgraph_t >(NoVertexIndexUpdater(), 45);
 128
 129     test_line_graph< LLgraph_t >(UpdateVertexIndex(), 8);
 130     test_line_graph< LLgraph_t >(UpdateVertexIndex(), 19);
 131
 132     test_line_graph< SSgraph_t >(UpdateVertexIndex(), 13);
 133     test_line_graph< SSgraph_t >(UpdateVertexIndex(), 20);
 134
 135     return boost::report_errors();
 136 }