|
Boost Users : |
Subject: Re: [Boost-users] Newbie: BGL & planar graphs
From: ano kato (nchatz314_at_[hidden])
Date: 2017-12-13 17:59:59
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_at_[hidden]> 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
>
> On Sun, Dec 3, 2017 at 2:29 AM, ano kato via Boost-users
> <boost-users_at_[hidden]> 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_at_[hidden]
> > 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_at_[hidden]
> https://lists.boost.org/mailman/listinfo.cgi/boost-users
>
Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net