1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
//=======================================================================
// Copyright 2007 Aaron Windsor
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map.hpp>
#include <boost/ref.hpp>
#include <vector>
#include <boost/graph/make_biconnected_planar.hpp>
#include <boost/graph/make_maximal_planar.hpp>
#include <boost/graph/planar_face_traversal.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>
// This example shows how to start with a connected planar graph
// and add edges to make the graph maximal planar (triangulated.)
// Any maximal planar simple graph on n vertices has 3n - 6 edges and
// 2n - 4 faces, a consequence of Euler's formula.
using namespace boost;
// This visitor is passed to planar_face_traversal to count the
// number of faces.
struct face_counter : public planar_face_traversal_visitor
{
face_counter() : count(0) {}
void begin_face() { ++count; }
int count;
};
int main(int argc, char** argv)
{
typedef adjacency_list
< vecS,
vecS,
undirectedS,
property<vertex_index_t, int>,
property<edge_index_t, int>
>
graph;
// Create the graph - a straight line
graph g(10);
add_edge(0,1,g);
add_edge(1,2,g);
add_edge(2,3,g);
add_edge(3,4,g);
add_edge(4,5,g);
add_edge(5,6,g);
add_edge(6,7,g);
add_edge(7,8,g);
add_edge(8,9,g);
std::cout << "Since the input graph is planar with " << num_vertices(g)
<< " vertices," << std::endl
<< "The output graph should be planar with "
<< 3*num_vertices(g) - 6 << " edges and "
<< 2*num_vertices(g) - 4 << " faces." << std::endl;
//Initialize the interior edge index
property_map<graph, edge_index_t>::type e_index = get(edge_index, g);
graph_traits<graph>::edges_size_type edge_count = 0;
graph_traits<graph>::edge_iterator ei, ei_end;
for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
put(e_index, *ei, edge_count++);
//Test for planarity; compute the planar embedding as a side-effect
typedef std::vector< graph_traits<graph>::edge_descriptor > vec_t;
std::vector<vec_t> embedding(num_vertices(g));
if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
boyer_myrvold_params::embedding =
&embedding[0]
)
)
std::cout << "Input graph is planar" << std::endl;
else
std::cout << "Input graph is not planar" << std::endl;
make_biconnected_planar(g, &embedding[0]);
// Re-initialize the edge index, since we just added a few edges
edge_count = 0;
for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
put(e_index, *ei, edge_count++);
//Test for planarity again; compute the planar embedding as a side-effect
if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
boyer_myrvold_params::embedding =
&embedding[0]
)
)
std::cout << "After calling make_biconnected, the graph is still planar"
<< std::endl;
else
std::cout << "After calling make_biconnected, the graph is not planar"
<< std::endl;
make_maximal_planar(g, &embedding[0]);
// Re-initialize the edge index, since we just added a few edges
edge_count = 0;
for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
put(e_index, *ei, edge_count++);
// Test for planarity one final time; compute the planar embedding as a
// side-effect
std::cout << "After calling make_maximal_planar, the final graph ";
if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
boyer_myrvold_params::embedding =
&embedding[0]
)
)
std::cout << "is planar." << std::endl;
else
std::cout << "is not planar." << std::endl;
std::cout << "The final graph has " << num_edges(g)
<< " edges." << std::endl;
face_counter count_visitor;
planar_face_traversal(g, &embedding[0], count_visitor);
std::cout << "The final graph has " << count_visitor.count << " faces."
<< std::endl;
return 0;
}
|
