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_CANONICAL_ORDERING_HPP__
10 #define __PLANAR_CANONICAL_ORDERING_HPP__
11
12 #include <vector>
13 #include <list>
14 #include <boost/config.hpp>
15 #include <boost/next_prior.hpp>
16 #include <boost/graph/graph_traits.hpp>
17 #include <boost/property_map/property_map.hpp>
18
19 namespace boost
20 {
21
22 namespace detail
23 {
24 enum planar_canonical_ordering_state
25 {
26 PCO_PROCESSED,
27 PCO_UNPROCESSED,
28 PCO_ONE_NEIGHBOR_PROCESSED,
29 PCO_READY_TO_BE_PROCESSED
30 };
31 }
32
33 template < typename Graph, typename PlanarEmbedding, typename OutputIterator,
34 typename VertexIndexMap >
planar_canonical_ordering(const Graph & g,PlanarEmbedding embedding,OutputIterator ordering,VertexIndexMap vm)35 void planar_canonical_ordering(const Graph& g, PlanarEmbedding embedding,
36 OutputIterator ordering, VertexIndexMap vm)
37 {
38
39 typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
40 typedef typename graph_traits< Graph >::edge_descriptor edge_t;
41 typedef
42 typename graph_traits< Graph >::adjacency_iterator adjacency_iterator_t;
43 typedef typename property_traits< PlanarEmbedding >::value_type
44 embedding_value_t;
45 typedef typename embedding_value_t::const_iterator embedding_iterator_t;
46 typedef iterator_property_map< typename std::vector< vertex_t >::iterator,
47 VertexIndexMap >
48 vertex_to_vertex_map_t;
49 typedef iterator_property_map<
50 typename std::vector< std::size_t >::iterator, VertexIndexMap >
51 vertex_to_size_t_map_t;
52
53 std::vector< vertex_t > processed_neighbor_vector(num_vertices(g));
54 vertex_to_vertex_map_t processed_neighbor(
55 processed_neighbor_vector.begin(), vm);
56
57 std::vector< std::size_t > status_vector(
58 num_vertices(g), detail::PCO_UNPROCESSED);
59 vertex_to_size_t_map_t status(status_vector.begin(), vm);
60
61 std::list< vertex_t > ready_to_be_processed;
62
63 vertex_t first_vertex = *vertices(g).first;
64 vertex_t second_vertex = first_vertex;
65 adjacency_iterator_t ai, ai_end;
66 for (boost::tie(ai, ai_end) = adjacent_vertices(first_vertex, g);
67 ai != ai_end; ++ai)
68 {
69 if (*ai == first_vertex)
70 continue;
71 second_vertex = *ai;
72 break;
73 }
74
75 ready_to_be_processed.push_back(first_vertex);
76 status[first_vertex] = detail::PCO_READY_TO_BE_PROCESSED;
77 ready_to_be_processed.push_back(second_vertex);
78 status[second_vertex] = detail::PCO_READY_TO_BE_PROCESSED;
79
80 while (!ready_to_be_processed.empty())
81 {
82 vertex_t u = ready_to_be_processed.front();
83 ready_to_be_processed.pop_front();
84
85 if (status[u] != detail::PCO_READY_TO_BE_PROCESSED
86 && u != second_vertex)
87 continue;
88
89 embedding_iterator_t ei, ei_start, ei_end;
90 embedding_iterator_t next_edge_itr, prior_edge_itr;
91
92 ei_start = embedding[u].begin();
93 ei_end = embedding[u].end();
94 prior_edge_itr = prior(ei_end);
95 while (source(*prior_edge_itr, g) == target(*prior_edge_itr, g))
96 prior_edge_itr = prior(prior_edge_itr);
97
98 for (ei = ei_start; ei != ei_end; ++ei)
99 {
100
101 edge_t e(*ei); // e = (u,v)
102 next_edge_itr
103 = boost::next(ei) == ei_end ? ei_start : boost::next(ei);
104 vertex_t v = source(e, g) == u ? target(e, g) : source(e, g);
105
106 vertex_t prior_vertex = source(*prior_edge_itr, g) == u
107 ? target(*prior_edge_itr, g)
108 : source(*prior_edge_itr, g);
109 vertex_t next_vertex = source(*next_edge_itr, g) == u
110 ? target(*next_edge_itr, g)
111 : source(*next_edge_itr, g);
112
113 // Need prior_vertex, u, v, and next_vertex to all be
114 // distinct. This is possible, since the input graph is
115 // triangulated. It'll be true all the time in a simple
116 // graph, but loops and parallel edges cause some complications.
117 if (prior_vertex == v || prior_vertex == u)
118 {
119 prior_edge_itr = ei;
120 continue;
121 }
122
123 // Skip any self-loops
124 if (u == v)
125 continue;
126
127 // Move next_edge_itr (and next_vertex) forwards
128 // past any loops or parallel edges
129 while (next_vertex == v || next_vertex == u)
130 {
131 next_edge_itr = boost::next(next_edge_itr) == ei_end
132 ? ei_start
133 : boost::next(next_edge_itr);
134 next_vertex = source(*next_edge_itr, g) == u
135 ? target(*next_edge_itr, g)
136 : source(*next_edge_itr, g);
137 }
138
139 if (status[v] == detail::PCO_UNPROCESSED)
140 {
141 status[v] = detail::PCO_ONE_NEIGHBOR_PROCESSED;
142 processed_neighbor[v] = u;
143 }
144 else if (status[v] == detail::PCO_ONE_NEIGHBOR_PROCESSED)
145 {
146 vertex_t x = processed_neighbor[v];
147 // are edges (v,u) and (v,x) adjacent in the planar
148 // embedding? if so, set status[v] = 1. otherwise, set
149 // status[v] = 2.
150
151 if ((next_vertex == x
152 && !(first_vertex == u && second_vertex == x))
153 || (prior_vertex == x
154 && !(first_vertex == x && second_vertex == u)))
155 {
156 status[v] = detail::PCO_READY_TO_BE_PROCESSED;
157 }
158 else
159 {
160 status[v] = detail::PCO_READY_TO_BE_PROCESSED + 1;
161 }
162 }
163 else if (status[v] > detail::PCO_ONE_NEIGHBOR_PROCESSED)
164 {
165 // check the two edges before and after (v,u) in the planar
166 // embedding, and update status[v] accordingly
167
168 bool processed_before = false;
169 if (status[prior_vertex] == detail::PCO_PROCESSED)
170 processed_before = true;
171
172 bool processed_after = false;
173 if (status[next_vertex] == detail::PCO_PROCESSED)
174 processed_after = true;
175
176 if (!processed_before && !processed_after)
177 ++status[v];
178
179 else if (processed_before && processed_after)
180 --status[v];
181 }
182
183 if (status[v] == detail::PCO_READY_TO_BE_PROCESSED)
184 ready_to_be_processed.push_back(v);
185
186 prior_edge_itr = ei;
187 }
188
189 status[u] = detail::PCO_PROCESSED;
190 *ordering = u;
191 ++ordering;
192 }
193 }
194
195 template < typename Graph, typename PlanarEmbedding, typename OutputIterator >
planar_canonical_ordering(const Graph & g,PlanarEmbedding embedding,OutputIterator ordering)196 void planar_canonical_ordering(
197 const Graph& g, PlanarEmbedding embedding, OutputIterator ordering)
198 {
199 planar_canonical_ordering(g, embedding, ordering, get(vertex_index, g));
200 }
201
202 } // namespace boost
203
204 #endif //__PLANAR_CANONICAL_ORDERING_HPP__
205