]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
20 | namespace boost | |
21 | { | |
22 | ||
23 | ||
24 | namespace detail { | |
25 | enum planar_canonical_ordering_state | |
26 | {PCO_PROCESSED, | |
27 | PCO_UNPROCESSED, | |
28 | PCO_ONE_NEIGHBOR_PROCESSED, | |
29 | PCO_READY_TO_BE_PROCESSED}; | |
30 | } | |
31 | ||
32 | template<typename Graph, | |
33 | typename PlanarEmbedding, | |
34 | typename OutputIterator, | |
35 | typename VertexIndexMap> | |
36 | void planar_canonical_ordering(const Graph& g, | |
37 | PlanarEmbedding embedding, | |
38 | OutputIterator ordering, | |
39 | VertexIndexMap vm) | |
40 | { | |
41 | ||
42 | typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; | |
43 | typedef typename graph_traits<Graph>::edge_descriptor edge_t; | |
44 | typedef typename graph_traits<Graph>::adjacency_iterator | |
45 | adjacency_iterator_t; | |
46 | typedef typename property_traits<PlanarEmbedding>::value_type | |
47 | embedding_value_t; | |
48 | typedef typename embedding_value_t::const_iterator embedding_iterator_t; | |
49 | typedef iterator_property_map | |
50 | <typename std::vector<vertex_t>::iterator, VertexIndexMap> | |
51 | vertex_to_vertex_map_t; | |
52 | typedef iterator_property_map | |
53 | <typename std::vector<std::size_t>::iterator, VertexIndexMap> | |
54 | vertex_to_size_t_map_t; | |
55 | ||
56 | std::vector<vertex_t> processed_neighbor_vector(num_vertices(g)); | |
57 | vertex_to_vertex_map_t processed_neighbor | |
58 | (processed_neighbor_vector.begin(), vm); | |
59 | ||
60 | std::vector<std::size_t> status_vector(num_vertices(g), detail::PCO_UNPROCESSED); | |
61 | vertex_to_size_t_map_t status(status_vector.begin(), vm); | |
62 | ||
63 | std::list<vertex_t> ready_to_be_processed; | |
64 | ||
65 | vertex_t first_vertex = *vertices(g).first; | |
66 | vertex_t second_vertex = first_vertex; | |
67 | adjacency_iterator_t ai, ai_end; | |
68 | for(boost::tie(ai,ai_end) = adjacent_vertices(first_vertex,g); ai != ai_end; ++ai) | |
69 | { | |
70 | if (*ai == first_vertex) | |
71 | continue; | |
72 | second_vertex = *ai; | |
73 | break; | |
74 | } | |
75 | ||
76 | ready_to_be_processed.push_back(first_vertex); | |
77 | status[first_vertex] = detail::PCO_READY_TO_BE_PROCESSED; | |
78 | ready_to_be_processed.push_back(second_vertex); | |
79 | status[second_vertex] = detail::PCO_READY_TO_BE_PROCESSED; | |
80 | ||
81 | while(!ready_to_be_processed.empty()) | |
82 | { | |
83 | vertex_t u = ready_to_be_processed.front(); | |
84 | ready_to_be_processed.pop_front(); | |
85 | ||
86 | if (status[u] != detail::PCO_READY_TO_BE_PROCESSED && 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 = boost::next(ei) == ei_end ? ei_start : boost::next(ei); | |
103 | vertex_t v = source(e,g) == u ? target(e,g) : source(e,g); | |
104 | ||
105 | vertex_t prior_vertex = source(*prior_edge_itr, g) == u ? | |
106 | target(*prior_edge_itr, g) : source(*prior_edge_itr, g); | |
107 | vertex_t next_vertex = source(*next_edge_itr, g) == u ? | |
108 | target(*next_edge_itr, g) : source(*next_edge_itr, g); | |
109 | ||
110 | // Need prior_vertex, u, v, and next_vertex to all be | |
111 | // distinct. This is possible, since the input graph is | |
112 | // triangulated. It'll be true all the time in a simple | |
113 | // graph, but loops and parallel edges cause some complications. | |
114 | if (prior_vertex == v || prior_vertex == u) | |
115 | { | |
116 | prior_edge_itr = ei; | |
117 | continue; | |
118 | } | |
119 | ||
120 | //Skip any self-loops | |
121 | if (u == v) | |
122 | continue; | |
123 | ||
124 | // Move next_edge_itr (and next_vertex) forwards | |
125 | // past any loops or parallel edges | |
126 | while (next_vertex == v || next_vertex == u) | |
127 | { | |
128 | next_edge_itr = boost::next(next_edge_itr) == ei_end ? | |
129 | ei_start : boost::next(next_edge_itr); | |
130 | next_vertex = source(*next_edge_itr, g) == u ? | |
131 | target(*next_edge_itr, g) : source(*next_edge_itr, g); | |
132 | } | |
133 | ||
134 | ||
135 | if (status[v] == detail::PCO_UNPROCESSED) | |
136 | { | |
137 | status[v] = detail::PCO_ONE_NEIGHBOR_PROCESSED; | |
138 | processed_neighbor[v] = u; | |
139 | } | |
140 | else if (status[v] == detail::PCO_ONE_NEIGHBOR_PROCESSED) | |
141 | { | |
142 | vertex_t x = processed_neighbor[v]; | |
143 | //are edges (v,u) and (v,x) adjacent in the planar | |
144 | //embedding? if so, set status[v] = 1. otherwise, set | |
145 | //status[v] = 2. | |
146 | ||
147 | if ((next_vertex == x && | |
148 | !(first_vertex == u && second_vertex == x) | |
149 | ) | |
150 | || | |
151 | (prior_vertex == x && | |
152 | !(first_vertex == x && second_vertex == u) | |
153 | ) | |
154 | ) | |
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 | ||
184 | if (status[v] == detail::PCO_READY_TO_BE_PROCESSED) | |
185 | ready_to_be_processed.push_back(v); | |
186 | ||
187 | prior_edge_itr = ei; | |
188 | ||
189 | } | |
190 | ||
191 | status[u] = detail::PCO_PROCESSED; | |
192 | *ordering = u; | |
193 | ++ordering; | |
194 | ||
195 | } | |
196 | ||
197 | } | |
198 | ||
199 | ||
200 | template<typename Graph, typename PlanarEmbedding, typename OutputIterator> | |
201 | void planar_canonical_ordering(const Graph& g, | |
202 | PlanarEmbedding embedding, | |
203 | OutputIterator ordering | |
204 | ) | |
205 | { | |
206 | planar_canonical_ordering(g, embedding, ordering, get(vertex_index,g)); | |
207 | } | |
208 | ||
209 | ||
210 | } //namespace boost | |
211 | ||
212 | #endif //__PLANAR_CANONICAL_ORDERING_HPP__ |