1 | //======================================================================= |
2 | // Copyright (c) Aaron Windsor 2007 |
3 | // |
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 | //======================================================================= |
8 | |
9 | #ifndef __PLANAR_FACE_TRAVERSAL_HPP__ |
10 | #define __PLANAR_FACE_TRAVERSAL_HPP__ |
11 | |
12 | #include <vector> |
13 | #include <set> |
14 | #include <map> |
15 | #include <boost/next_prior.hpp> |
16 | #include <boost/graph/graph_traits.hpp> |
17 | #include <boost/graph/properties.hpp> |
18 | |
19 | |
20 | namespace boost |
21 | { |
22 | |
23 | |
24 | |
25 | |
26 | struct planar_face_traversal_visitor |
27 | { |
28 | void begin_traversal() |
29 | {} |
30 | |
31 | void begin_face() |
32 | {} |
33 | |
34 | template <typename Edge> |
35 | void next_edge(Edge) |
36 | {} |
37 | |
38 | template <typename Vertex> |
39 | void next_vertex(Vertex) |
40 | {} |
41 | |
42 | void end_face() |
43 | {} |
44 | |
45 | void end_traversal() |
46 | {} |
47 | |
48 | }; |
49 | |
50 | |
51 | |
52 | |
53 | |
54 | template<typename Graph, |
55 | typename PlanarEmbedding, |
56 | typename Visitor, |
57 | typename EdgeIndexMap> |
58 | void planar_face_traversal(const Graph& g, |
59 | PlanarEmbedding embedding, |
60 | Visitor& visitor, EdgeIndexMap em |
61 | ) |
62 | { |
63 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; |
64 | typedef typename graph_traits<Graph>::edge_descriptor edge_t; |
65 | typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t; |
66 | typedef typename graph_traits<Graph>::edge_iterator edge_iterator_t; |
67 | typedef typename |
68 | property_traits<PlanarEmbedding>::value_type embedding_value_t; |
69 | typedef typename embedding_value_t::const_iterator embedding_iterator_t; |
70 | |
71 | typedef typename |
72 | std::vector< std::set<vertex_t> > distinguished_edge_storage_t; |
73 | typedef typename |
74 | std::vector< std::map<vertex_t, edge_t> > |
75 | distinguished_edge_to_edge_storage_t; |
76 | |
77 | typedef typename |
78 | boost::iterator_property_map |
79 | <typename distinguished_edge_storage_t::iterator, EdgeIndexMap> |
80 | distinguished_edge_map_t; |
81 | |
82 | typedef typename |
83 | boost::iterator_property_map |
84 | <typename distinguished_edge_to_edge_storage_t::iterator, EdgeIndexMap> |
85 | distinguished_edge_to_edge_map_t; |
86 | |
87 | distinguished_edge_storage_t visited_vector(num_edges(g)); |
88 | distinguished_edge_to_edge_storage_t next_edge_vector(num_edges(g)); |
89 | |
90 | distinguished_edge_map_t visited(visited_vector.begin(), em); |
91 | distinguished_edge_to_edge_map_t next_edge(next_edge_vector.begin(), em); |
92 | |
93 | vertex_iterator_t vi, vi_end; |
94 | typename std::vector<edge_t>::iterator ei, ei_end; |
95 | edge_iterator_t fi, fi_end; |
96 | embedding_iterator_t pi, pi_begin, pi_end; |
97 | |
98 | visitor.begin_traversal(); |
99 | |
100 | // Initialize the next_edge property map. This map is initialized from the |
101 | // PlanarEmbedding so that get(next_edge, e)[v] is the edge that comes |
102 | // after e in the clockwise embedding around vertex v. |
103 | |
104 | for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) |
105 | { |
106 | vertex_t v(*vi); |
107 | pi_begin = embedding[v].begin(); |
108 | pi_end = embedding[v].end(); |
109 | for(pi = pi_begin; pi != pi_end; ++pi) |
110 | { |
111 | edge_t e(*pi); |
112 | std::map<vertex_t, edge_t> m = get(next_edge, e); |
113 | m[v] = boost::next(pi) == pi_end ? *pi_begin : *boost::next(pi); |
114 | put(next_edge, e, m); |
115 | } |
116 | } |
117 | |
118 | // Take a copy of the edges in the graph here, since we want to accomodate |
119 | // face traversals that add edges to the graph (for triangulation, in |
120 | // particular) and don't want to use invalidated edge iterators. |
121 | // Also, while iterating over all edges in the graph, we single out |
122 | // any self-loops, which need some special treatment in the face traversal. |
123 | |
124 | std::vector<edge_t> self_loops; |
125 | std::vector<edge_t> edges_cache; |
126 | std::vector<vertex_t> vertices_in_edge; |
127 | |
128 | for(boost::tie(fi,fi_end) = edges(g); fi != fi_end; ++fi) |
129 | { |
130 | edge_t e(*fi); |
131 | edges_cache.push_back(e); |
132 | if (source(e,g) == target(e,g)) |
133 | self_loops.push_back(e); |
134 | } |
135 | |
136 | |
137 | // Iterate over all edges in the graph |
138 | ei_end = edges_cache.end(); |
139 | for(ei = edges_cache.begin(); ei != ei_end; ++ei) |
140 | { |
141 | |
142 | edge_t e(*ei); |
143 | vertices_in_edge.clear(); |
144 | vertices_in_edge.push_back(source(e,g)); |
145 | vertices_in_edge.push_back(target(e,g)); |
146 | |
147 | typename std::vector<vertex_t>::iterator vi, vi_end; |
148 | vi_end = vertices_in_edge.end(); |
149 | |
150 | //Iterate over both vertices in the current edge |
151 | for(vi = vertices_in_edge.begin(); vi != vi_end; ++vi) |
152 | { |
153 | |
154 | vertex_t v(*vi); |
155 | std::set<vertex_t> e_visited = get(visited, e); |
156 | typename std::set<vertex_t>::iterator e_visited_found |
157 | = e_visited.find(v); |
158 | |
159 | if (e_visited_found == e_visited.end()) |
160 | visitor.begin_face(); |
161 | |
162 | while (e_visited.find(v) == e_visited.end()) |
163 | { |
164 | visitor.next_vertex(v); |
165 | visitor.next_edge(e); |
166 | e_visited.insert(v); |
167 | put(visited, e, e_visited); |
168 | v = source(e,g) == v ? target(e,g) : source(e,g); |
169 | e = get(next_edge, e)[v]; |
170 | e_visited = get(visited, e); |
171 | } |
172 | |
173 | if (e_visited_found == e_visited.end()) |
174 | visitor.end_face(); |
175 | |
176 | } |
177 | |
178 | } |
179 | |
180 | // Iterate over all self-loops, visiting them once separately |
181 | // (they've already been visited once, this visitation is for |
182 | // the "inside" of the self-loop) |
183 | |
184 | ei_end = self_loops.end(); |
185 | for(ei = self_loops.begin(); ei != ei_end; ++ei) |
186 | { |
187 | visitor.begin_face(); |
188 | visitor.next_edge(*ei); |
189 | visitor.next_vertex(source(*ei,g)); |
190 | visitor.end_face(); |
191 | } |
192 | |
193 | visitor.end_traversal(); |
194 | |
195 | } |
196 | |
197 | |
198 | |
199 | template<typename Graph, typename PlanarEmbedding, typename Visitor> |
200 | inline void planar_face_traversal(const Graph& g, |
201 | PlanarEmbedding embedding, |
202 | Visitor& visitor |
203 | ) |
204 | { |
205 | planar_face_traversal(g, embedding, visitor, get(edge_index, g)); |
206 | } |
207 | |
208 | |
209 | |
210 | |
211 | } //namespace boost |
212 | |
213 | #endif //__PLANAR_FACE_TRAVERSAL_HPP__ |
214 | |