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