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
20namespace 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;
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__
213

source code of boost/boost/graph/planar_canonical_ordering.hpp