Newbie: BGL & planar graphs
Hello everyone! I am using BGL to test for the planarity of drawings of graphs. The coordinates are hardcoded into the source code. Here's what the graph should look like: <https://i.imgur.com/UGA0mRB.png>. This definitely isn't planar and yet is_straight_line_drawing() returns 1! I'm quite confused. Am I doing something wrong? Thank you to anyone who replies. #include <iostream> #include <vector> #include <boost/graph/adjacency_list.hpp> #include <boost/property_map/property_map.hpp> #include <boost/graph/is_straight_line_drawing.hpp> using namespace boost; typedef struct { size_t x,y; } coord_t; int main(void) { typedef adjacency_list<vecS, vecS, undirectedS, property<vertex_index_t, int> > graph; graph Moser(7); add_edge(0,1,Moser); add_edge(0,6,Moser); add_edge(0,4,Moser); add_edge(1,6,Moser); add_edge(1,2,Moser); add_edge(2,6,Moser); add_edge(2,5,Moser); add_edge(2,3,Moser); add_edge(3,4,Moser); add_edge(4,5,Moser); graph G(Moser); int k = num_vertices(G); typedef std::vector<coord_t> cvec; typedef boost::iterator_property_map <cvec::iterator, property_map<graph, vertex_index_t>::type // ? > foo_t; cvec v(num_vertices(G)); foo_t drawing(v.begin(), get(vertex_index, G)); coord_t x[k]; x[0].x = 20; x[0].y = 10; x[1].x = 50; x[1].y = 10; x[2].x = 58; x[2].y = 52; x[3].x = 00; x[3].y = 30; x[4].x = 35; x[4].y = 50; x[5].x = 12; x[5].y = 51; x[6].x = 70; x[6].y = 30; graph_traits<graph>::vertex_iterator vi, vi_end; for(boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) put(drawing, *vi, x[*vi]); if(is_straight_line_drawing(G,drawing)) std::cout << "This is a straight line planar drawing!" << std::endl; return 0; }
The graph is planar. Hint: it does not contain neither a K5 complete graph nor a K3,3 bipartite graph (see Kuratowski's theorem) lc On Sun, Dec 3, 2017 at 2:29 AM, ano kato via Boost-users <boost-users@lists.boost.org> wrote:
Hello everyone!
I am using BGL to test for the planarity of drawings of graphs. The coordinates are hardcoded into the source code. Here's what the graph should look like: <https://i.imgur.com/UGA0mRB.png>. This definitely isn't planar and yet is_straight_line_drawing() returns 1! I'm quite confused. Am I doing something wrong? Thank you to anyone who replies.
#include <iostream> #include <vector> #include <boost/graph/adjacency_list.hpp> #include <boost/property_map/property_map.hpp> #include <boost/graph/is_straight_line_drawing.hpp>
using namespace boost;
typedef struct { size_t x,y; } coord_t;
int main(void) {
typedef adjacency_list<vecS, vecS, undirectedS, property<vertex_index_t, int> > graph;
graph Moser(7); add_edge(0,1,Moser); add_edge(0,6,Moser); add_edge(0,4,Moser); add_edge(1,6,Moser); add_edge(1,2,Moser); add_edge(2,6,Moser); add_edge(2,5,Moser); add_edge(2,3,Moser); add_edge(3,4,Moser); add_edge(4,5,Moser);
graph G(Moser); int k = num_vertices(G);
typedef std::vector<coord_t> cvec; typedef boost::iterator_property_map <cvec::iterator, property_map<graph, vertex_index_t>::type // ? > foo_t;
cvec v(num_vertices(G)); foo_t drawing(v.begin(), get(vertex_index, G));
coord_t x[k]; x[0].x = 20; x[0].y = 10; x[1].x = 50; x[1].y = 10; x[2].x = 58; x[2].y = 52; x[3].x = 00; x[3].y = 30; x[4].x = 35; x[4].y = 50; x[5].x = 12; x[5].y = 51; x[6].x = 70; x[6].y = 30;
graph_traits<graph>::vertex_iterator vi, vi_end; for(boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) put(drawing, *vi, x[*vi]); if(is_straight_line_drawing(G,drawing)) std::cout << "This is a straight line planar drawing!" << std::endl; return 0; }
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org https://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Leo Cacciari Aliae nationes servitutem pati possunt. Populi Romani est propria libertas.
The graph is planar, however, the specific drawing (see pic) is not a planar drawing, yet is_straight_line_drawing returns true. See < http://www.boost.org/doc/libs/1_65_1/libs/graph/doc/is_straight_line_drawing.html>. That's what confuses me. On Tue, Dec 12, 2017 at 5:11 AM, Leo Cacciari via Boost-users < boost-users@lists.boost.org> wrote:
The graph is planar.
Hint: it does not contain neither a K5 complete graph nor a K3,3 bipartite graph (see Kuratowski's theorem)
lc
Hello everyone!
I am using BGL to test for the planarity of drawings of graphs. The coordinates are hardcoded into the source code. Here's what the graph should look like: <https://i.imgur.com/UGA0mRB.png>. This definitely isn't
On Sun, Dec 3, 2017 at 2:29 AM, ano kato via Boost-users <boost-users@lists.boost.org> wrote: planar
and yet is_straight_line_drawing() returns 1! I'm quite confused. Am I doing something wrong? Thank you to anyone who replies.
#include <iostream> #include <vector> #include <boost/graph/adjacency_list.hpp> #include <boost/property_map/property_map.hpp> #include <boost/graph/is_straight_line_drawing.hpp>
using namespace boost;
typedef struct { size_t x,y; } coord_t;
int main(void) {
typedef adjacency_list<vecS, vecS, undirectedS, property<vertex_index_t, int> > graph;
graph Moser(7); add_edge(0,1,Moser); add_edge(0,6,Moser); add_edge(0,4,Moser); add_edge(1,6,Moser); add_edge(1,2,Moser); add_edge(2,6,Moser); add_edge(2,5,Moser); add_edge(2,3,Moser); add_edge(3,4,Moser); add_edge(4,5,Moser);
graph G(Moser); int k = num_vertices(G);
typedef std::vector<coord_t> cvec; typedef boost::iterator_property_map <cvec::iterator, property_map<graph, vertex_index_t>::type // ? > foo_t;
cvec v(num_vertices(G)); foo_t drawing(v.begin(), get(vertex_index, G));
coord_t x[k]; x[0].x = 20; x[0].y = 10; x[1].x = 50; x[1].y = 10; x[2].x = 58; x[2].y = 52; x[3].x = 00; x[3].y = 30; x[4].x = 35; x[4].y = 50; x[5].x = 12; x[5].y = 51; x[6].x = 70; x[6].y = 30;
graph_traits<graph>::vertex_iterator vi, vi_end; for(boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) put(drawing, *vi, x[*vi]); if(is_straight_line_drawing(G,drawing)) std::cout << "This is a straight line planar drawing!" << std::endl; return 0; }
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org https://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Leo Cacciari
Aliae nationes servitutem pati possunt. Populi Romani est propria libertas. _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org https://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (2)
-
ano kato
-
Leo Cacciari