Newbie: BGL & planar graphs

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Newbie: BGL & planar graphs

Boost - Users mailing list
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
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: Newbie: BGL & planar graphs

Boost - Users mailing list
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
<[hidden email]> 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
> [hidden email]
> 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
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|

Re: Newbie: BGL & planar graphs

Boost - Users mailing list
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 <[hidden email]> 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
<[hidden email]> 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
> [hidden email]
> 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
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users


_______________________________________________
Boost-users mailing list
[hidden email]
https://lists.boost.org/mailman/listinfo.cgi/boost-users