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>
20 using namespace boost
;
22 // a class to hold the coordinates of the straight line embedding
29 int main(int argc
, char** argv
)
31 typedef adjacency_list
< vecS
, vecS
, undirectedS
,
32 property
< vertex_index_t
, int > >
35 // Define the storage type for the planar embedding
36 typedef std::vector
< std::vector
< graph_traits
< graph
>::edge_descriptor
> >
38 typedef boost::iterator_property_map
< embedding_storage_t::iterator
,
39 property_map
< graph
, vertex_index_t
>::type
>
42 // Create the graph - a maximal planar graph on 7 vertices. The functions
43 // planar_canonical_ordering and chrobak_payne_straight_line_drawing both
44 // require a maximal planar graph. If you start with a graph that isn't
45 // maximal planar (or you're not sure), you can use the functions
46 // make_connected, make_biconnected_planar, and make_maximal planar in
47 // sequence to add a set of edges to any undirected planar graph to make
67 // Create the planar embedding
68 embedding_storage_t
embedding_storage(num_vertices(g
));
69 embedding_t
embedding(embedding_storage
.begin(), get(vertex_index
, g
));
71 boyer_myrvold_planarity_test(boyer_myrvold_params::graph
= g
,
72 boyer_myrvold_params::embedding
= embedding
);
74 // Find a canonical ordering
75 std::vector
< graph_traits
< graph
>::vertex_descriptor
> ordering
;
76 planar_canonical_ordering(g
, embedding
, std::back_inserter(ordering
));
78 // Set up a property map to hold the mapping from vertices to coord_t's
79 typedef std::vector
< coord_t
> straight_line_drawing_storage_t
;
80 typedef boost::iterator_property_map
<
81 straight_line_drawing_storage_t::iterator
,
82 property_map
< graph
, vertex_index_t
>::type
>
83 straight_line_drawing_t
;
85 straight_line_drawing_storage_t
straight_line_drawing_storage(
87 straight_line_drawing_t
straight_line_drawing(
88 straight_line_drawing_storage
.begin(), get(vertex_index
, g
));
90 // Compute the straight line drawing
91 chrobak_payne_straight_line_drawing(
92 g
, embedding
, ordering
.begin(), ordering
.end(), straight_line_drawing
);
94 std::cout
<< "The straight line drawing is: " << std::endl
;
95 graph_traits
< graph
>::vertex_iterator vi
, vi_end
;
96 for (boost::tie(vi
, vi_end
) = vertices(g
); vi
!= vi_end
; ++vi
)
98 coord_t
coord(get(straight_line_drawing
, *vi
));
99 std::cout
<< *vi
<< " -> (" << coord
.x
<< ", " << coord
.y
<< ")"
103 // Verify that the drawing is actually a plane drawing
104 if (is_straight_line_drawing(g
, straight_line_drawing
))
105 std::cout
<< "Is a plane drawing." << std::endl
;
107 std::cout
<< "Is not a plane drawing." << std::endl
;