ceph/src/boost/libs/graph/test/parallel_edges_loops_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 /*
  10
  11 This test is almost identical to all_planar_input_files_test.cpp
  12 except that parallel edges and loops are added to the graphs as
  13 they are read in.
  14
  15 This test needs to be linked against Boost.Filesystem.
  16
  17 */
  18
  19 #define BOOST_FILESYSTEM_VERSION 3
  20
  21 #include <iostream>
  22 #include <fstream>
  23 #include <vector>
  24 #include <string>
  25 #include <utility>
  26
  27
  28 #include <boost/property_map/property_map.hpp>
  29 #include <boost/lexical_cast.hpp>
  30 #include <boost/tuple/tuple.hpp>
  31 #include <boost/filesystem.hpp>
  32 #include <boost/algorithm/string.hpp>
  33 #include <boost/test/minimal.hpp>
  34
  35
  36 #include <boost/graph/adjacency_list.hpp>
  37 #include <boost/graph/depth_first_search.hpp>
  38 #include <boost/graph/properties.hpp>
  39 #include <boost/graph/graph_traits.hpp>
  40 #include <boost/graph/planar_canonical_ordering.hpp>
  41 #include <boost/graph/make_connected.hpp>
  42 #include <boost/graph/make_biconnected_planar.hpp>
  43 #include <boost/graph/make_maximal_planar.hpp>
  44 #include <boost/graph/is_straight_line_drawing.hpp>
  45 #include <boost/graph/is_kuratowski_subgraph.hpp>
  46 #include <boost/graph/chrobak_payne_drawing.hpp>
  47 #include <boost/graph/boyer_myrvold_planar_test.hpp>
  48 #include <boost/graph/planar_detail/add_edge_visitors.hpp>
  49
  50
  51
  52
  53
  54
  55 using namespace boost;
  56
  57 struct coord_t
  58 {
  59   std::size_t x;
  60   std::size_t y;
  61 };
  62
  63
  64
  65 template <typename Graph>
  66 void read_dimacs(Graph& g, const std::string& filename)
  67 {
  68
  69   // every <vertex_stride>th vertex has a self-loop
  70   int vertex_stride = 5;
  71
  72   // on vertices with self loops, there are between 1 and
  73   // <max_loop_multiplicity> loops
  74   int max_loop_multiplicity = 6;
  75
  76   // every <edge_stride>th edge is a parallel edge
  77   int edge_stride = 7;
  78
  79   // parallel edges come in groups of 2 to <max_edge_multiplicity> + 1
  80   int max_edge_multiplicity = 5;
  81
  82   typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
  83   typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
  84   std::vector<vertex_t> vertices_by_index;
  85
  86   std::ifstream in(filename.c_str());
  87
  88   long num_edges_added = 0;
  89   long num_parallel_edges = 0;
  90
  91   while (!in.eof())
  92     {
  93
  94       char buffer[256];
  95       in.getline(buffer, 256);
  96       std::string s(buffer);
  97
  98       if (s.size() == 0)
  99         continue;
 100
 101       std::vector<std::string> v;
 102       split(v, buffer, is_any_of(" \t\n"));
 103
 104       if (v[0] == "p")
 105         {
 106           //v[1] == "edge"
 107           long num_vertices = boost::lexical_cast<long>(v[2].c_str());
 108           g = Graph(num_vertices);
 109
 110
 111           vertex_iterator_t vi, vi_end;
 112           long count = 0;
 113           long mult_count = 0;
 114           for(boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
 115             {
 116               if (count % vertex_stride == 0)
 117                 {
 118                   for(int i = 0;
 119                       i < (mult_count % max_loop_multiplicity) + 1;
 120                       ++i
 121                       )
 122                     {
 123                       add_edge(*vi, *vi, g);
 124                     }
 125                   ++mult_count;
 126                 }
 127               ++count;
 128             }
 129
 130           std::copy(vertices(g).first,
 131                     vertices(g).second,
 132                     std::back_inserter(vertices_by_index)
 133                     );
 134         }
 135       else if (v[0] == "e")
 136         {
 137           add_edge(vertices_by_index[boost::lexical_cast<long>(v[1].c_str())],
 138                    vertices_by_index[boost::lexical_cast<long>(v[2].c_str())],
 139                    g);
 140
 141           if (num_edges_added % edge_stride == 0)
 142             {
 143               for(int i = 0;
 144                   i < (num_parallel_edges % max_edge_multiplicity) + 1;
 145                   ++i
 146                   )
 147                 {
 148                   add_edge(vertices_by_index
 149                              [boost::lexical_cast<long>(v[1].c_str())],
 150                            vertices_by_index
 151                              [boost::lexical_cast<long>(v[2].c_str())],
 152                            g);
 153                 }
 154               ++num_parallel_edges;
 155             }
 156           ++num_edges_added;
 157
 158         }
 159     }
 160 }
 161
 162
 163
 164
 165 struct face_counter : planar_face_traversal_visitor
 166 {
 167
 168   face_counter() : m_num_faces(0) {}
 169
 170   void begin_face() { ++m_num_faces; }
 171
 172   long num_faces() { return m_num_faces; }
 173
 174 private:
 175
 176   long m_num_faces;
 177
 178 };
 179
 180
 181
 182
 183
 184
 185 int test_graph(const std::string& dimacs_filename)
 186 {
 187
 188   typedef adjacency_list<listS,
 189                          vecS,
 190                          undirectedS,
 191                          property<vertex_index_t, int>,
 192                          property<edge_index_t, int> > graph;
 193
 194   typedef graph_traits<graph>::edge_descriptor edge_t;
 195   typedef graph_traits<graph>::edge_iterator edge_iterator_t;
 196   typedef graph_traits<graph>::vertex_iterator vertex_iterator_t;
 197   typedef graph_traits<graph>::edges_size_type e_size_t;
 198   typedef graph_traits<graph>::vertex_descriptor vertex_t;
 199   typedef edge_index_update_visitor<property_map<graph, edge_index_t>::type>
 200     edge_visitor_t;
 201
 202   vertex_iterator_t vi, vi_end;
 203   edge_iterator_t ei, ei_end;
 204
 205   graph g;
 206   read_dimacs(g, dimacs_filename);
 207
 208   // Initialize the interior edge index
 209   property_map<graph, edge_index_t>::type e_index = get(edge_index, g);
 210   e_size_t edge_count = 0;
 211   for(boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
 212     put(e_index, *ei, edge_count++);
 213
 214   // Initialize the interior vertex index - not needed if the vertices
 215   // are stored with a vecS
 216   /*
 217   property_map<graph, vertex_index_t>::type v_index = get(vertex_index, g);
 218   v_size_t vertex_count = 0;
 219   for(boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi)
 220     put(v_index, *vi, vertex_count++);
 221   */
 222
 223   // This edge_updater will automatically update the interior edge
 224   // index of the graph as edges are created.
 225   edge_visitor_t edge_updater(get(edge_index, g), num_edges(g));
 226
 227   // The input graph may not be maximal planar, but the Chrobak-Payne straight
 228   // line drawing needs a maximal planar graph as input. So, we make a copy of
 229   // the original graph here, then add edges to the graph to make it maximal
 230   // planar. When we're done creating a drawing of the maximal planar graph,
 231   // we can use the same mapping of vertices to points on the grid to embed the
 232   // original, non-maximal graph.
 233   graph g_copy(g);
 234
 235   // Add edges to make g connected, if it isn't already
 236   make_connected(g, get(vertex_index, g), edge_updater);
 237
 238   std::vector<graph_traits<graph>::edge_descriptor> kuratowski_edges;
 239
 240   typedef std::vector< std::vector<edge_t> > edge_permutation_storage_t;
 241   typedef boost::iterator_property_map
 242     < edge_permutation_storage_t::iterator,
 243       property_map<graph, vertex_index_t>::type
 244     >
 245     edge_permutation_t;
 246
 247   edge_permutation_storage_t edge_permutation_storage(num_vertices(g));
 248   edge_permutation_t perm(edge_permutation_storage.begin(),
 249                           get(vertex_index,g)
 250                           );
 251
 252   // Test for planarity, computing the planar embedding or the kuratowski
 253   // subgraph.
 254   if (!boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
 255                                     boyer_myrvold_params::embedding = perm,
 256                                     boyer_myrvold_params::kuratowski_subgraph
 257                                     = std::back_inserter(kuratowski_edges)
 258                                     )
 259       )
 260     {
 261       std::cerr << "Not planar. ";
 262       BOOST_REQUIRE(is_kuratowski_subgraph
 263                     (g, kuratowski_edges.begin(), kuratowski_edges.end())
 264                     );
 265
 266       return 0;
 267     }
 268
 269   // If we get this far, we have a connected planar graph.
 270   make_biconnected_planar(g, perm, get(edge_index, g), edge_updater);
 271
 272   // Compute the planar embedding of the (now) biconnected planar graph
 273   BOOST_CHECK (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
 274                                             boyer_myrvold_params::embedding
 275                                               = perm
 276                                             )
 277                );
 278
 279   // If we get this far, we have a biconnected planar graph
 280   make_maximal_planar(g, perm, get(vertex_index,g), get(edge_index,g),
 281                       edge_updater);
 282
 283   // Now the graph is triangulated - we can compute the final planar embedding
 284   BOOST_CHECK (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
 285                                             boyer_myrvold_params::embedding
 286                                               = perm
 287                                             )
 288                );
 289
 290   // Make sure Euler's formula holds
 291   face_counter vis;
 292   planar_face_traversal(g, perm, vis, get(edge_index, g));
 293
 294   BOOST_CHECK(num_vertices(g) - num_edges(g) + vis.num_faces() == 2);
 295
 296   // Compute a planar canonical ordering of the vertices
 297   std::vector<vertex_t> ordering;
 298   planar_canonical_ordering(g, perm, std::back_inserter(ordering));
 299
 300   BOOST_CHECK(ordering.size() == num_vertices(g));
 301
 302   typedef std::vector< coord_t > drawing_storage_t;
 303   typedef boost::iterator_property_map
 304     < drawing_storage_t::iterator, property_map<graph, vertex_index_t>::type >
 305     drawing_map_t;
 306
 307   drawing_storage_t drawing_vector(num_vertices(g));
 308   drawing_map_t drawing(drawing_vector.begin(), get(vertex_index,g));
 309
 310   // Compute a straight line drawing
 311   chrobak_payne_straight_line_drawing(g,
 312                                       perm,
 313                                       ordering.begin(),
 314                                       ordering.end(),
 315                                       drawing
 316                                       );
 317
 318   std::cerr << "Planar. ";
 319   BOOST_REQUIRE (is_straight_line_drawing(g, drawing));
 320
 321   return 0;
 322 }
 323
 324
 325
 326
 327
 328
 329
 330 int test_main(int argc, char* argv[])
 331 {
 332
 333   std::string input_directory_str = "planar_input_graphs";
 334   if (argc > 1)
 335     {
 336       input_directory_str = std::string(argv[1]);
 337     }
 338
 339   std::cout << "Reading planar input files from " << input_directory_str
 340             << std::endl;
 341
 342   filesystem::path input_directory =
 343     filesystem::system_complete(filesystem::path(input_directory_str));
 344   const std::string dimacs_extension = ".dimacs";
 345
 346   filesystem::directory_iterator dir_end;
 347   for( filesystem::directory_iterator dir_itr(input_directory);
 348        dir_itr != dir_end; ++dir_itr)
 349   {
 350
 351     if (dir_itr->path().extension() != dimacs_extension)
 352       continue;
 353
 354     std::cerr << "Testing " << dir_itr->path().leaf() << "... ";
 355     BOOST_REQUIRE (test_graph(dir_itr->path().string()) == 0);
 356
 357     std::cerr << std::endl;
 358   }
 359
 360   return 0;
 361
 362 }