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

Subject: Re: [Boost-users] [Graph] Issue with is_straight_line_drawing?
From: Gevorg Voskanyan (v_gevorg_at_[hidden])
Date: 2008-10-03 07:41:41

David Gleich wrote:

> 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 
> #include 
> #include 
> #include 
> #include 
> #include 
> 
> #include 
> 
> 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> 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::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.
> */

Hi David,

is_straight_line_drawing() is actually correct here because your test graph can be drawn in a way that has no edge crossing.
Consider for example this one:

 3 --- 1
 \  \ /  /
  \  0 /
   \ | /
    \|/
     2

Sorry for my perhaps clumsy ASCII drawing, but you get the idea.

Hope this helps,

Gevorg