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>
15 #include <boost/graph/planar_canonical_ordering.hpp>
16 #include <boost/graph/is_straight_line_drawing.hpp>
17 #include <boost/graph/chrobak_payne_drawing.hpp>
18 #include <boost/graph/boyer_myrvold_planar_test.hpp>
22 using namespace boost
;
24 //a class to hold the coordinates of the straight line embedding
32 int main(int argc
, char** argv
)
34 typedef adjacency_list
38 property
<vertex_index_t
, int>
43 //Define the storage type for the planar embedding
44 typedef std::vector
< std::vector
< graph_traits
<graph
>::edge_descriptor
> >
46 typedef boost::iterator_property_map
47 < embedding_storage_t::iterator
,
48 property_map
<graph
, vertex_index_t
>::type
54 // Create the graph - a maximal planar graph on 7 vertices. The functions
55 // planar_canonical_ordering and chrobak_payne_straight_line_drawing both
56 // require a maximal planar graph. If you start with a graph that isn't
57 // maximal planar (or you're not sure), you can use the functions
58 // make_connected, make_biconnected_planar, and make_maximal planar in
59 // sequence to add a set of edges to any undirected planar graph to make
81 // Create the planar embedding
82 embedding_storage_t
embedding_storage(num_vertices(g
));
83 embedding_t
embedding(embedding_storage
.begin(), get(vertex_index
,g
));
85 boyer_myrvold_planarity_test(boyer_myrvold_params::graph
= g
,
86 boyer_myrvold_params::embedding
= embedding
91 // Find a canonical ordering
92 std::vector
<graph_traits
<graph
>::vertex_descriptor
> ordering
;
93 planar_canonical_ordering(g
, embedding
, std::back_inserter(ordering
));
96 //Set up a property map to hold the mapping from vertices to coord_t's
97 typedef std::vector
< coord_t
> straight_line_drawing_storage_t
;
98 typedef boost::iterator_property_map
99 < straight_line_drawing_storage_t::iterator
,
100 property_map
<graph
, vertex_index_t
>::type
102 straight_line_drawing_t
;
104 straight_line_drawing_storage_t straight_line_drawing_storage
106 straight_line_drawing_t straight_line_drawing
107 (straight_line_drawing_storage
.begin(),
113 // Compute the straight line drawing
114 chrobak_payne_straight_line_drawing(g
,
118 straight_line_drawing
123 std::cout
<< "The straight line drawing is: " << std::endl
;
124 graph_traits
<graph
>::vertex_iterator vi
, vi_end
;
125 for(boost::tie(vi
,vi_end
) = vertices(g
); vi
!= vi_end
; ++vi
)
127 coord_t
coord(get(straight_line_drawing
,*vi
));
128 std::cout
<< *vi
<< " -> (" << coord
.x
<< ", " << coord
.y
<< ")"
132 // Verify that the drawing is actually a plane drawing
133 if (is_straight_line_drawing(g
, straight_line_drawing
))
134 std::cout
<< "Is a plane drawing." << std::endl
;
136 std::cout
<< "Is not a plane drawing." << std::endl
;