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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
|
//=======================================================================
// Copyright (c) Aaron Windsor 2007
//
// 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)
//=======================================================================
#ifndef __PLANAR_FACE_TRAVERSAL_HPP__
#define __PLANAR_FACE_TRAVERSAL_HPP__
#include <vector>
#include <set>
#include <map>
#include <boost/next_prior.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/properties.hpp>
namespace boost
{
struct planar_face_traversal_visitor
{
void begin_traversal()
{}
void begin_face()
{}
template <typename Edge>
void next_edge(Edge)
{}
template <typename Vertex>
void next_vertex(Vertex)
{}
void end_face()
{}
void end_traversal()
{}
};
template<typename Graph,
typename PlanarEmbedding,
typename Visitor,
typename EdgeIndexMap>
void planar_face_traversal(const Graph& g,
PlanarEmbedding embedding,
Visitor& visitor, EdgeIndexMap em
)
{
typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
typedef typename graph_traits<Graph>::edge_descriptor edge_t;
typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
typedef typename graph_traits<Graph>::edge_iterator edge_iterator_t;
typedef typename
property_traits<PlanarEmbedding>::value_type embedding_value_t;
typedef typename embedding_value_t::const_iterator embedding_iterator_t;
typedef typename
std::vector< std::set<vertex_t> > distinguished_edge_storage_t;
typedef typename
std::vector< std::map<vertex_t, edge_t> >
distinguished_edge_to_edge_storage_t;
typedef typename
boost::iterator_property_map
<typename distinguished_edge_storage_t::iterator, EdgeIndexMap>
distinguished_edge_map_t;
typedef typename
boost::iterator_property_map
<typename distinguished_edge_to_edge_storage_t::iterator, EdgeIndexMap>
distinguished_edge_to_edge_map_t;
distinguished_edge_storage_t visited_vector(num_edges(g));
distinguished_edge_to_edge_storage_t next_edge_vector(num_edges(g));
distinguished_edge_map_t visited(visited_vector.begin(), em);
distinguished_edge_to_edge_map_t next_edge(next_edge_vector.begin(), em);
vertex_iterator_t vi, vi_end;
typename std::vector<edge_t>::iterator ei, ei_end;
edge_iterator_t fi, fi_end;
embedding_iterator_t pi, pi_begin, pi_end;
visitor.begin_traversal();
// Initialize the next_edge property map. This map is initialized from the
// PlanarEmbedding so that get(next_edge, e)[v] is the edge that comes
// after e in the clockwise embedding around vertex v.
for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
{
vertex_t v(*vi);
pi_begin = embedding[v].begin();
pi_end = embedding[v].end();
for(pi = pi_begin; pi != pi_end; ++pi)
{
edge_t e(*pi);
std::map<vertex_t, edge_t> m = get(next_edge, e);
m[v] = boost::next(pi) == pi_end ? *pi_begin : *boost::next(pi);
put(next_edge, e, m);
}
}
// Take a copy of the edges in the graph here, since we want to accomodate
// face traversals that add edges to the graph (for triangulation, in
// particular) and don't want to use invalidated edge iterators.
// Also, while iterating over all edges in the graph, we single out
// any self-loops, which need some special treatment in the face traversal.
std::vector<edge_t> self_loops;
std::vector<edge_t> edges_cache;
std::vector<vertex_t> vertices_in_edge;
for(boost::tie(fi,fi_end) = edges(g); fi != fi_end; ++fi)
{
edge_t e(*fi);
edges_cache.push_back(e);
if (source(e,g) == target(e,g))
self_loops.push_back(e);
}
// Iterate over all edges in the graph
ei_end = edges_cache.end();
for(ei = edges_cache.begin(); ei != ei_end; ++ei)
{
edge_t e(*ei);
vertices_in_edge.clear();
vertices_in_edge.push_back(source(e,g));
vertices_in_edge.push_back(target(e,g));
typename std::vector<vertex_t>::iterator vi, vi_end;
vi_end = vertices_in_edge.end();
//Iterate over both vertices in the current edge
for(vi = vertices_in_edge.begin(); vi != vi_end; ++vi)
{
vertex_t v(*vi);
std::set<vertex_t> e_visited = get(visited, e);
typename std::set<vertex_t>::iterator e_visited_found
= e_visited.find(v);
if (e_visited_found == e_visited.end())
visitor.begin_face();
while (e_visited.find(v) == e_visited.end())
{
visitor.next_vertex(v);
visitor.next_edge(e);
e_visited.insert(v);
put(visited, e, e_visited);
v = source(e,g) == v ? target(e,g) : source(e,g);
e = get(next_edge, e)[v];
e_visited = get(visited, e);
}
if (e_visited_found == e_visited.end())
visitor.end_face();
}
}
// Iterate over all self-loops, visiting them once separately
// (they've already been visited once, this visitation is for
// the "inside" of the self-loop)
ei_end = self_loops.end();
for(ei = self_loops.begin(); ei != ei_end; ++ei)
{
visitor.begin_face();
visitor.next_edge(*ei);
visitor.next_vertex(source(*ei,g));
visitor.end_face();
}
visitor.end_traversal();
}
template<typename Graph, typename PlanarEmbedding, typename Visitor>
inline void planar_face_traversal(const Graph& g,
PlanarEmbedding embedding,
Visitor& visitor
)
{
planar_face_traversal(g, embedding, visitor, get(edge_index, g));
}
} //namespace boost
#endif //__PLANAR_FACE_TRAVERSAL_HPP__
|
