[Boost-users] [Graph] Issue with is_straight_line_drawing?

2 Oct 2008

      Hi,

I'm concerned about the output I'm getting from the
is_straight_line_drawing function in the Boost Graph library.  My
understanding was that it should report true when the graph and
positions are a planar embedding (no edge crossings).

Based on this understanding, I thought the code listed at the end of
the message should say that the drawing for a clique on 4 vertices,
with positions on a square, is not planar (see the picture below).
This arrangement has one edge crossing.  The function outputs that the
graph is a plane drawing.

Did I misunderstand what the is_straight_line_drawing function is
supposed to do?

Thanks,
David Gleich

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map.hpp>
#include <vector>

#include <boost/graph/is_straight_line_drawing.hpp>

using namespace boost;

//a class to hold the coordinates of the straight line embedding
struct coord_t {
 std::size_t x;
 std::size_t y;
};

int main(int argc, char** argv) {
 typedef adjacency_list
   < vecS, vecS, undirectedS, property<vertex_index_t, int> > graph;

 graph g(4); // make the clique on 4 vertices
 add_edge(0,1,g);  add_edge(0,2,g);  add_edge(0,3,g);
 add_edge(1,2,g);  add_edge(1,3,g);  add_edge(2,3,g);

 //Set up a property map to hold the mapping from vertices to coord_t's
 typedef std::vector< coord_t > straight_line_drawing_storage_t;
 typedef boost::iterator_property_map
   < straight_line_drawing_storage_t::iterator,
     property_map<graph, vertex_index_t>::type
...
straight_line_drawing_t;

 straight_line_drawing_storage_t straight_line_drawing_storage
   (num_vertices(g));
 straight_line_drawing_t straight_line_drawing
   (straight_line_drawing_storage.begin(),
    get(vertex_index,g)
    );
 /*
  should be
      0
    / | \
   3--|--1
    \ | /
      2
  which is not a plane drawing.
 */
 straight_line_drawing[0].x = 1;   straight_line_drawing[0].y = 2;
 straight_line_drawing[1].x = 2;   straight_line_drawing[1].y = 1;
 straight_line_drawing[2].x = 1;   straight_line_drawing[2].y = 0;
 straight_line_drawing[3].x = 0;   straight_line_drawing[3].y = 1;

 if (is_straight_line_drawing(g, straight_line_drawing))
   std::cout << "Is a plane drawing." << std::endl;
 else
   std::cout << "Is not a plane drawing." << std::endl;

 return 0;
}

/*  Compiling and example
$ g++ -v
Using built-in specs.
Target: x86_64-linux-gnu
Configured with: ../src/configure -v
--enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr
--enable-shared --with-system-zlib --libexecdir=/usr/lib
--without-included-gettext --enable-threads=posix --enable-nls
--with-gxx-include-dir=/usr/include/c++/4.2 --program-suffix=-4.2
--enable-clocale=gnu --enable-libstdcxx-debug --enable-objc-gc
--enable-mpfr --enable-checking=release --build=x86_64-linux-gnu
--host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.2.3 (Ubuntu 4.2.3-2ubuntu7)

$g++ is_straight_line_drawing.cpp -I/home/dgleich/dev/lib/boost_1_36_0/
$./a.out
Is a plane drawing.

Should be

Is not a plane drawing.
 */