ceph/src/boost/libs/graph/test/basic_planarity_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/boyer_myrvold_planar_test.hpp>
  12 #include <boost/property_map/property_map.hpp>
  13 #include <boost/property_map/vector_property_map.hpp>
  14 #include <boost/test/minimal.hpp>
  15
  16
  17 using namespace boost;
  18
  19
  20 struct VertexIndexUpdater
  21 {
  22   template <typename Graph>
  23   void reset(Graph& g)
  24   {
  25     typename property_map<Graph, vertex_index_t>::type index = get(vertex_index, g);
  26     typename graph_traits<Graph>::vertex_iterator vi, vi_end;
  27     typename graph_traits<Graph>::vertices_size_type cnt = 0;
  28     for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
  29       put(index, *vi, cnt++);
  30   }
  31 };
  32
  33 struct NoVertexIndexUpdater
  34 {
  35   template <typename Graph> void reset(Graph&) {}
  36 };
  37
  38
  39
  40 template <typename Graph, typename VertexIndexUpdater>
  41 void test_K_5(VertexIndexUpdater vertex_index)
  42 {
  43   typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
  44
  45   Graph g;
  46   vertex_t v1 = add_vertex(g);
  47   vertex_t v2 = add_vertex(g);
  48   vertex_t v3 = add_vertex(g);
  49   vertex_t v4 = add_vertex(g);
  50   vertex_t v5 = add_vertex(g);
  51   vertex_index.reset(g);
  52
  53   BOOST_CHECK(boyer_myrvold_planarity_test(g));
  54   add_edge(v1, v2, g);
  55   BOOST_CHECK(boyer_myrvold_planarity_test(g));
  56   add_edge(v1, v3, g);
  57   BOOST_CHECK(boyer_myrvold_planarity_test(g));
  58   add_edge(v1, v4, g);
  59   BOOST_CHECK(boyer_myrvold_planarity_test(g));
  60   add_edge(v1, v5, g);
  61   BOOST_CHECK(boyer_myrvold_planarity_test(g));
  62   add_edge(v2, v3, g);
  63   BOOST_CHECK(boyer_myrvold_planarity_test(g));
  64   add_edge(v2, v4, g);
  65   BOOST_CHECK(boyer_myrvold_planarity_test(g));
  66   add_edge(v2, v5, g);
  67   BOOST_CHECK(boyer_myrvold_planarity_test(g));
  68   add_edge(v3, v4, g);
  69   BOOST_CHECK(boyer_myrvold_planarity_test(g));
  70   add_edge(v3, v5, g);
  71   BOOST_CHECK(boyer_myrvold_planarity_test(g));
  72
  73   //This edge should make the graph non-planar
  74   add_edge(v4, v5, g);
  75   BOOST_CHECK(!boyer_myrvold_planarity_test(g));
  76
  77 }
  78
  79
  80
  81
  82
  83 template <typename Graph, typename VertexIndexUpdater>
  84 void test_K_3_3(VertexIndexUpdater vertex_index)
  85 {
  86   typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
  87
  88   Graph g;
  89   vertex_t v1 = add_vertex(g);
  90   vertex_t v2 = add_vertex(g);
  91   vertex_t v3 = add_vertex(g);
  92   vertex_t v4 = add_vertex(g);
  93   vertex_t v5 = add_vertex(g);
  94   vertex_t v6 = add_vertex(g);
  95   vertex_index.reset(g);
  96
  97   BOOST_CHECK(boyer_myrvold_planarity_test(g));
  98   add_edge(v1, v4, g);
  99   BOOST_CHECK(boyer_myrvold_planarity_test(g));
 100   add_edge(v1, v5, g);
 101   BOOST_CHECK(boyer_myrvold_planarity_test(g));
 102   add_edge(v1, v6, g);
 103   BOOST_CHECK(boyer_myrvold_planarity_test(g));
 104   add_edge(v2, v4, g);
 105   BOOST_CHECK(boyer_myrvold_planarity_test(g));
 106   add_edge(v2, v5, g);
 107   BOOST_CHECK(boyer_myrvold_planarity_test(g));
 108   add_edge(v2, v6, g);
 109   BOOST_CHECK(boyer_myrvold_planarity_test(g));
 110   add_edge(v3, v4, g);
 111   BOOST_CHECK(boyer_myrvold_planarity_test(g));
 112   add_edge(v3, v5, g);
 113   BOOST_CHECK(boyer_myrvold_planarity_test(g));
 114
 115   //This edge should make the graph non-planar
 116   add_edge(v3, v6, g);
 117   BOOST_CHECK(!boyer_myrvold_planarity_test(g));
 118
 119 }
 120
 121
 122
 123
 124
 125 // This test creates a maximal planar graph on num_vertices vertices,
 126 // then, if num_vertices is at least 5, adds an additional edge to
 127 // create a non-planar graph.
 128
 129 template <typename Graph, typename VertexIndexUpdater>
 130 void test_maximal_planar(VertexIndexUpdater vertex_index, std::size_t num_vertices)
 131 {
 132   typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
 133
 134   Graph g;
 135   std::vector<vertex_t> vmap;
 136   for(std::size_t i = 0; i < num_vertices; ++i)
 137     vmap.push_back(add_vertex(g));
 138
 139   vertex_index.reset(g);
 140
 141   BOOST_CHECK(boyer_myrvold_planarity_test(g));
 142   //create a cycle
 143   for(std::size_t i = 0; i < num_vertices; ++i)
 144     {
 145       add_edge(vmap[i], vmap[(i+1) % num_vertices], g);
 146       BOOST_CHECK(boyer_myrvold_planarity_test(g));
 147     }
 148
 149   //triangulate the interior of the cycle.
 150   for(std::size_t i = 2; i < num_vertices - 1; ++i)
 151     {
 152       add_edge(vmap[0], vmap[i], g);
 153       BOOST_CHECK(boyer_myrvold_planarity_test(g));
 154     }
 155
 156   //triangulate the exterior of the cycle.
 157   for(std::size_t i = 3; i < num_vertices; ++i)
 158     {
 159       add_edge(vmap[1], vmap[i], g);
 160       BOOST_CHECK(boyer_myrvold_planarity_test(g));
 161     }
 162
 163   //Now add an additional edge, forcing the graph to be non-planar.
 164   if (num_vertices > 4)
 165     {
 166       add_edge(vmap[2], vmap[4], g);
 167       BOOST_CHECK(!boyer_myrvold_planarity_test(g));
 168     }
 169
 170 }
 171
 172
 173
 174
 175
 176 int test_main(int, char* [])
 177 {
 178   typedef adjacency_list
 179     <vecS,
 180     vecS,
 181     undirectedS,
 182     property<vertex_index_t, int>
 183     >
 184     VVgraph_t;
 185
 186   typedef adjacency_list
 187     <vecS,
 188     listS,
 189     undirectedS,
 190     property<vertex_index_t, int>
 191     >
 192     VLgraph_t;
 193
 194   typedef adjacency_list
 195     <listS,
 196     vecS,
 197     undirectedS,
 198     property<vertex_index_t, int>
 199     >
 200     LVgraph_t;
 201
 202   typedef adjacency_list
 203     <listS,
 204     listS,
 205     undirectedS,
 206     property<vertex_index_t, int>
 207     >
 208     LLgraph_t;
 209
 210   typedef adjacency_list
 211     <setS,
 212     setS,
 213     undirectedS,
 214     property<vertex_index_t, int>
 215     >
 216     SSgraph_t;
 217
 218   test_K_5<VVgraph_t>(NoVertexIndexUpdater());
 219   test_K_3_3<VVgraph_t>(NoVertexIndexUpdater());
 220   test_maximal_planar<VVgraph_t>(NoVertexIndexUpdater(), 3);
 221   test_maximal_planar<VVgraph_t>(NoVertexIndexUpdater(), 6);
 222   test_maximal_planar<VVgraph_t>(NoVertexIndexUpdater(), 10);
 223   test_maximal_planar<VVgraph_t>(NoVertexIndexUpdater(), 20);
 224   test_maximal_planar<VVgraph_t>(NoVertexIndexUpdater(), 50);
 225
 226   test_K_5<VLgraph_t>(VertexIndexUpdater());
 227   test_K_3_3<VLgraph_t>(VertexIndexUpdater());
 228   test_maximal_planar<VLgraph_t>(VertexIndexUpdater(), 3);
 229   test_maximal_planar<VLgraph_t>(VertexIndexUpdater(), 6);
 230   test_maximal_planar<VLgraph_t>(VertexIndexUpdater(), 10);
 231   test_maximal_planar<VLgraph_t>(VertexIndexUpdater(), 20);
 232   test_maximal_planar<VLgraph_t>(VertexIndexUpdater(), 50);
 233
 234   test_K_5<LVgraph_t>(NoVertexIndexUpdater());
 235   test_K_3_3<LVgraph_t>(NoVertexIndexUpdater());
 236   test_maximal_planar<LVgraph_t>(NoVertexIndexUpdater(), 3);
 237   test_maximal_planar<LVgraph_t>(NoVertexIndexUpdater(), 6);
 238   test_maximal_planar<LVgraph_t>(NoVertexIndexUpdater(), 10);
 239   test_maximal_planar<LVgraph_t>(NoVertexIndexUpdater(), 20);
 240   test_maximal_planar<LVgraph_t>(NoVertexIndexUpdater(), 50);
 241
 242   test_K_5<LLgraph_t>(VertexIndexUpdater());
 243   test_K_3_3<LLgraph_t>(VertexIndexUpdater());
 244   test_maximal_planar<LLgraph_t>(VertexIndexUpdater(), 3);
 245   test_maximal_planar<LLgraph_t>(VertexIndexUpdater(), 6);
 246   test_maximal_planar<LLgraph_t>(VertexIndexUpdater(), 10);
 247   test_maximal_planar<LLgraph_t>(VertexIndexUpdater(), 20);
 248   test_maximal_planar<LLgraph_t>(VertexIndexUpdater(), 50);
 249
 250   test_K_5<SSgraph_t>(VertexIndexUpdater());
 251   test_K_3_3<SSgraph_t>(VertexIndexUpdater());
 252   test_maximal_planar<SSgraph_t>(VertexIndexUpdater(), 3);
 253   test_maximal_planar<SSgraph_t>(VertexIndexUpdater(), 6);
 254   test_maximal_planar<SSgraph_t>(VertexIndexUpdater(), 10);
 255   test_maximal_planar<SSgraph_t>(VertexIndexUpdater(), 20);
 256   test_maximal_planar<SSgraph_t>(VertexIndexUpdater(), 50);
 257
 258   return 0;
 259 }