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> planar_canonical_ordering(const Graph & g,PlanarEmbedding embedding,OutputIterator ordering,VertexIndexMap vm)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> planar_canonical_ordering(const Graph & g,PlanarEmbedding embedding,OutputIterator ordering)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