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

   1 //=======================================================================
   2 // Copyright 2008 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/property_map/property_map.hpp>
  10 #include <boost/test/minimal.hpp>
  11 #include <boost/graph/adjacency_list.hpp>
  12 #include <boost/graph/properties.hpp>
  13 #include <boost/graph/graph_traits.hpp>
  14 #include <boost/graph/is_straight_line_drawing.hpp>
  15
  16 #include <vector>
  17
  18 using namespace boost;
  19
  20 struct coord_t
  21 {
  22   std::size_t x;
  23   std::size_t y;
  24 };
  25
  26
  27 int test_main(int, char*[])
  28 {
  29   typedef adjacency_list< vecS, vecS, undirectedS,
  30                           property<vertex_index_t, int>
  31                          > graph_t;
  32
  33   typedef std::vector< coord_t > drawing_storage_t;
  34
  35   typedef boost::iterator_property_map
  36       < drawing_storage_t::iterator,
  37         property_map<graph_t, vertex_index_t>::type
  38        > drawing_t;
  39
  40   graph_t g(4);
  41   add_edge(0,1,g);
  42   add_edge(2,3,g);
  43
  44   drawing_storage_t drawing_storage(num_vertices(g));
  45   drawing_t drawing(drawing_storage.begin(), get(vertex_index,g));
  46
  47   // two perpendicular lines that intersect at (1,1)
  48   drawing[0].x = 1; drawing[0].y = 0;
  49   drawing[1].x = 1; drawing[1].y = 2;
  50   drawing[2].x = 0; drawing[2].y = 1;
  51   drawing[3].x = 2; drawing[3].y = 1;
  52
  53   BOOST_REQUIRE(!is_straight_line_drawing(g,drawing));
  54
  55   // two parallel horizontal lines
  56   drawing[0].x = 0; drawing[0].y = 0;
  57   drawing[1].x = 2; drawing[1].y = 0;
  58
  59   BOOST_REQUIRE(is_straight_line_drawing(g,drawing));
  60
  61   // two parallel vertical lines
  62   drawing[0].x = 0; drawing[0].y = 0;
  63   drawing[1].x = 0; drawing[1].y = 2;
  64   drawing[2].x = 1; drawing[2].y = 0;
  65   drawing[3].x = 1; drawing[3].y = 2;
  66
  67   BOOST_REQUIRE(is_straight_line_drawing(g,drawing));
  68
  69   // two lines that intersect at (1,1)
  70   drawing[0].x = 0; drawing[0].y = 0;
  71   drawing[1].x = 2; drawing[1].y = 2;
  72   drawing[2].x = 0; drawing[2].y = 2;
  73   drawing[3].x = 2; drawing[3].y = 0;
  74
  75   BOOST_REQUIRE(!is_straight_line_drawing(g,drawing));
  76
  77   // K_4 arranged in a diamond pattern, so that edges intersect
  78   g = graph_t(4);
  79   add_edge(0,1,g);
  80   add_edge(0,2,g);
  81   add_edge(0,3,g);
  82   add_edge(1,2,g);
  83   add_edge(1,3,g);
  84   add_edge(2,3,g);
  85
  86   drawing_storage = drawing_storage_t(num_vertices(g));
  87   drawing = drawing_t(drawing_storage.begin(), get(vertex_index,g));
  88
  89   drawing[0].x = 1; drawing[0].y = 2;
  90   drawing[1].x = 2; drawing[1].y = 1;
  91   drawing[2].x = 1; drawing[2].y = 0;
  92   drawing[3].x = 0; drawing[3].y = 1;
  93
  94   BOOST_REQUIRE(!is_straight_line_drawing(g, drawing));
  95
  96   // K_4 arranged so that no edges intersect
  97   drawing[0].x = 0; drawing[0].y = 0;
  98   drawing[1].x = 1; drawing[1].y = 1;
  99   drawing[2].x = 1; drawing[2].y = 2;
 100   drawing[3].x = 2; drawing[3].y = 0;
 101
 102   BOOST_REQUIRE(is_straight_line_drawing(g, drawing));
 103
 104   // a slightly more complicated example - edges (0,1) and (4,5)
 105   // intersect
 106   g = graph_t(8);
 107   add_edge(0,1,g);
 108   add_edge(2,3,g);
 109   add_edge(4,5,g);
 110   add_edge(6,7,g);
 111
 112   drawing_storage = drawing_storage_t(num_vertices(g));
 113   drawing = drawing_t(drawing_storage.begin(), get(vertex_index,g));
 114
 115   drawing[0].x = 1; drawing[0].y = 1;
 116   drawing[1].x = 5; drawing[1].y = 4;
 117   drawing[2].x = 2; drawing[2].y = 5;
 118   drawing[3].x = 4; drawing[3].y = 4;
 119   drawing[4].x = 3; drawing[4].y = 4;
 120   drawing[5].x = 3; drawing[5].y = 2;
 121   drawing[6].x = 4; drawing[6].y = 2;
 122   drawing[7].x = 1; drawing[7].y = 1;
 123
 124   BOOST_REQUIRE(!is_straight_line_drawing(g, drawing));
 125
 126   // form a graph consisting of a bunch of parallel vertical edges,
 127   // then place an edge at various positions to intersect edges
 128   g = graph_t(22);
 129   for(int i = 0; i < 11; ++i)
 130     add_edge(2*i,2*i+1,g);
 131
 132   drawing_storage = drawing_storage_t(num_vertices(g));
 133   drawing = drawing_t(drawing_storage.begin(), get(vertex_index,g));
 134
 135   for(int i = 0; i < 10; ++i)
 136     {
 137       drawing[2*i].x = i; drawing[2*i].y = 0;
 138       drawing[2*i+1].x = i; drawing[2*i+1].y = 10;
 139     }
 140
 141   // put the final edge as a horizontal edge intersecting one other edge
 142   drawing[20].x = 5; drawing[20].y = 5;
 143   drawing[21].x = 7; drawing[21].y = 5;
 144
 145   BOOST_REQUIRE(!is_straight_line_drawing(g, drawing));
 146
 147   // make the final edge a diagonal intersecting multiple edges
 148   drawing[20].x = 2; drawing[20].y = 4;
 149   drawing[21].x = 9; drawing[21].y = 7;
 150
 151   BOOST_REQUIRE(!is_straight_line_drawing(g, drawing));
 152
 153   // reverse the slope
 154   drawing[20].x = 2; drawing[20].y = 7;
 155   drawing[21].x = 9; drawing[21].y = 4;
 156
 157   BOOST_REQUIRE(!is_straight_line_drawing(g, drawing));
 158
 159   return 0;
 160 }
 161