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