1 //=======================================================================
2 // Copyright 2007 Aaron Windsor
4 // Distributed under the Boost Software License, Version 1.0. (See
5 // accompanying file LICENSE_1_0.txt or copy at
6 // http://www.boost.org/LICENSE_1_0.txt)
7 //=======================================================================
9 #include <boost/graph/adjacency_list.hpp>
10 #include <boost/graph/properties.hpp>
11 #include <boost/graph/graph_traits.hpp>
12 #include <boost/property_map/property_map.hpp>
13 #include <boost/ref.hpp>
16 #include <boost/graph/planar_face_traversal.hpp>
17 #include <boost/graph/boyer_myrvold_planar_test.hpp>
20 using namespace boost
;
24 // Some planar face traversal visitors that will
25 // print the vertices and edges on the faces
27 struct output_visitor
: public planar_face_traversal_visitor
29 void begin_face() { std::cout
<< "New face: "; }
30 void end_face() { std::cout
<< std::endl
; }
35 struct vertex_output_visitor
: public output_visitor
37 template <typename Vertex
>
38 void next_vertex(Vertex v
)
40 std::cout
<< v
<< " ";
46 struct edge_output_visitor
: public output_visitor
48 template <typename Edge
>
49 void next_edge(Edge e
)
51 std::cout
<< e
<< " ";
56 int main(int argc
, char** argv
)
59 typedef adjacency_list
63 property
<vertex_index_t
, int>,
64 property
<edge_index_t
, int>
68 // Create a graph - this is a biconnected, 3 x 3 grid.
69 // It should have four small (four vertex/four edge) faces and
70 // one large face that contains all but the interior vertex
93 // Initialize the interior edge index
94 property_map
<graph
, edge_index_t
>::type e_index
= get(edge_index
, g
);
95 graph_traits
<graph
>::edges_size_type edge_count
= 0;
96 graph_traits
<graph
>::edge_iterator ei
, ei_end
;
97 for(boost::tie(ei
, ei_end
) = edges(g
); ei
!= ei_end
; ++ei
)
98 put(e_index
, *ei
, edge_count
++);
101 // Test for planarity - we know it is planar, we just want to
102 // compute the planar embedding as a side-effect
103 typedef std::vector
< graph_traits
<graph
>::edge_descriptor
> vec_t
;
104 std::vector
<vec_t
> embedding(num_vertices(g
));
105 if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph
= g
,
106 boyer_myrvold_params::embedding
=
110 std::cout
<< "Input graph is planar" << std::endl
;
112 std::cout
<< "Input graph is not planar" << std::endl
;
115 std::cout
<< std::endl
<< "Vertices on the faces: " << std::endl
;
116 vertex_output_visitor v_vis
;
117 planar_face_traversal(g
, &embedding
[0], v_vis
);
119 std::cout
<< std::endl
<< "Edges on the faces: " << std::endl
;
120 edge_output_visitor e_vis
;
121 planar_face_traversal(g
, &embedding
[0], e_vis
);