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 __CHROBAK_PAYNE_DRAWING_HPP__ 10 #define __CHROBAK_PAYNE_DRAWING_HPP__ 11 12 #include <vector> 13 #include <list> 14 #include <stack> 15 #include <boost/config.hpp> 16 #include <boost/graph/graph_traits.hpp> 17 #include <boost/property_map/property_map.hpp> 18 19 20 namespace boost 21 { 22 23 namespace graph { namespace detail 24 { 25 26 template<typename Graph, 27 typename VertexToVertexMap, 28 typename VertexTo1DCoordMap> accumulate_offsets(typename graph_traits<Graph>::vertex_descriptor v,std::size_t offset,const Graph & g,VertexTo1DCoordMap x,VertexTo1DCoordMap delta_x,VertexToVertexMap left,VertexToVertexMap right)29 void accumulate_offsets(typename graph_traits<Graph>::vertex_descriptor v, 30 std::size_t offset, 31 const Graph& g, 32 VertexTo1DCoordMap x, 33 VertexTo1DCoordMap delta_x, 34 VertexToVertexMap left, 35 VertexToVertexMap right) 36 { 37 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; 38 // Suggestion of explicit stack from Aaron Windsor to avoid system stack 39 // overflows. 40 typedef std::pair<vertex_descriptor, std::size_t> stack_entry; 41 std::stack<stack_entry> st; 42 st.push(stack_entry(v, offset)); 43 while (!st.empty()) { 44 vertex_descriptor v = st.top().first; 45 std::size_t offset = st.top().second; 46 st.pop(); 47 if (v != graph_traits<Graph>::null_vertex()) { 48 x[v] += delta_x[v] + offset; 49 st.push(stack_entry(left[v], x[v])); 50 st.push(stack_entry(right[v], x[v])); 51 } 52 } 53 } 54 55 } /*namespace detail*/ } /*namespace graph*/ 56 57 58 59 60 61 template<typename Graph, 62 typename PlanarEmbedding, 63 typename ForwardIterator, 64 typename GridPositionMap, 65 typename VertexIndexMap> chrobak_payne_straight_line_drawing(const Graph & g,PlanarEmbedding embedding,ForwardIterator ordering_begin,ForwardIterator ordering_end,GridPositionMap drawing,VertexIndexMap vm)66 void chrobak_payne_straight_line_drawing(const Graph& g, 67 PlanarEmbedding embedding, 68 ForwardIterator ordering_begin, 69 ForwardIterator ordering_end, 70 GridPositionMap drawing, 71 VertexIndexMap vm 72 ) 73 { 74 75 typedef typename graph_traits<Graph>::vertex_descriptor vertex_t; 76 typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t; 77 typedef typename PlanarEmbedding::value_type::const_iterator 78 edge_permutation_iterator_t; 79 typedef typename graph_traits<Graph>::vertices_size_type v_size_t; 80 typedef std::vector<vertex_t> vertex_vector_t; 81 typedef std::vector<v_size_t> vsize_vector_t; 82 typedef std::vector<bool> bool_vector_t; 83 typedef boost::iterator_property_map 84 <typename vertex_vector_t::iterator, VertexIndexMap> 85 vertex_to_vertex_map_t; 86 typedef boost::iterator_property_map 87 <typename vsize_vector_t::iterator, VertexIndexMap> 88 vertex_to_vsize_map_t; 89 typedef boost::iterator_property_map 90 <typename bool_vector_t::iterator, VertexIndexMap> 91 vertex_to_bool_map_t; 92 93 vertex_vector_t left_vector(num_vertices(g), 94 graph_traits<Graph>::null_vertex() 95 ); 96 vertex_vector_t right_vector(num_vertices(g), 97 graph_traits<Graph>::null_vertex() 98 ); 99 vsize_vector_t seen_as_right_vector(num_vertices(g), 0); 100 vsize_vector_t seen_vector(num_vertices(g), 0); 101 vsize_vector_t delta_x_vector(num_vertices(g),0); 102 vsize_vector_t y_vector(num_vertices(g)); 103 vsize_vector_t x_vector(num_vertices(g),0); 104 bool_vector_t installed_vector(num_vertices(g),false); 105 106 vertex_to_vertex_map_t left(left_vector.begin(), vm); 107 vertex_to_vertex_map_t right(right_vector.begin(), vm); 108 vertex_to_vsize_map_t seen_as_right(seen_as_right_vector.begin(), vm); 109 vertex_to_vsize_map_t seen(seen_vector.begin(), vm); 110 vertex_to_vsize_map_t delta_x(delta_x_vector.begin(), vm); 111 vertex_to_vsize_map_t y(y_vector.begin(), vm); 112 vertex_to_vsize_map_t x(x_vector.begin(), vm); 113 vertex_to_bool_map_t installed(installed_vector.begin(), vm); 114 115 v_size_t timestamp = 1; 116 vertex_vector_t installed_neighbors; 117 118 ForwardIterator itr = ordering_begin; 119 vertex_t v1 = *itr; ++itr; 120 vertex_t v2 = *itr; ++itr; 121 vertex_t v3 = *itr; ++itr; 122 123 delta_x[v2] = 1; 124 delta_x[v3] = 1; 125 126 y[v1] = 0; 127 y[v2] = 0; 128 y[v3] = 1; 129 130 right[v1] = v3; 131 right[v3] = v2; 132 133 installed[v1] = installed[v2] = installed[v3] = true; 134 135 for(ForwardIterator itr_end = ordering_end; itr != itr_end; ++itr) 136 { 137 vertex_t v = *itr; 138 139 // First, find the leftmost and rightmost neighbor of v on the outer 140 // cycle of the embedding. 141 // Note: since we're moving clockwise through the edges adjacent to v, 142 // we're actually moving from right to left among v's neighbors on the 143 // outer face (since v will be installed above them all) looking for 144 // the leftmost and rightmost installed neigbhors 145 146 vertex_t leftmost = graph_traits<Graph>::null_vertex(); 147 vertex_t rightmost = graph_traits<Graph>::null_vertex(); 148 149 installed_neighbors.clear(); 150 151 vertex_t prev_vertex = graph_traits<Graph>::null_vertex(); 152 edge_permutation_iterator_t pi, pi_end; 153 pi_end = embedding[v].end(); 154 for(pi = embedding[v].begin(); pi != pi_end; ++pi) 155 { 156 vertex_t curr_vertex = source(*pi,g) == v ? 157 target(*pi,g) : source(*pi,g); 158 159 // Skip any self-loops or parallel edges 160 if (curr_vertex == v || curr_vertex == prev_vertex) 161 continue; 162 163 if (installed[curr_vertex]) 164 { 165 seen[curr_vertex] = timestamp; 166 167 if (right[curr_vertex] != graph_traits<Graph>::null_vertex()) 168 { 169 seen_as_right[right[curr_vertex]] = timestamp; 170 } 171 installed_neighbors.push_back(curr_vertex); 172 } 173 174 prev_vertex = curr_vertex; 175 } 176 177 typename vertex_vector_t::iterator vi, vi_end; 178 vi_end = installed_neighbors.end(); 179 for(vi = installed_neighbors.begin(); vi != vi_end; ++vi) 180 { 181 if (right[*vi] == graph_traits<Graph>::null_vertex() || 182 seen[right[*vi]] != timestamp 183 ) 184 rightmost = *vi; 185 if (seen_as_right[*vi] != timestamp) 186 leftmost = *vi; 187 } 188 189 ++timestamp; 190 191 //stretch gaps 192 ++delta_x[right[leftmost]]; 193 ++delta_x[rightmost]; 194 195 //adjust offsets 196 std::size_t delta_p_q = 0; 197 vertex_t stopping_vertex = right[rightmost]; 198 for(vertex_t temp = right[leftmost]; temp != stopping_vertex; 199 temp = right[temp] 200 ) 201 { 202 delta_p_q += delta_x[temp]; 203 } 204 205 delta_x[v] = ((y[rightmost] + delta_p_q) - y[leftmost])/2; 206 y[v] = y[leftmost] + delta_x[v]; 207 delta_x[rightmost] = delta_p_q - delta_x[v]; 208 209 bool leftmost_and_rightmost_adjacent = right[leftmost] == rightmost; 210 if (!leftmost_and_rightmost_adjacent) 211 delta_x[right[leftmost]] -= delta_x[v]; 212 213 //install v 214 if (!leftmost_and_rightmost_adjacent) 215 { 216 left[v] = right[leftmost]; 217 vertex_t next_to_rightmost; 218 for(vertex_t temp = leftmost; temp != rightmost; 219 temp = right[temp] 220 ) 221 { 222 next_to_rightmost = temp; 223 } 224 225 right[next_to_rightmost] = graph_traits<Graph>::null_vertex(); 226 } 227 else 228 { 229 left[v] = graph_traits<Graph>::null_vertex(); 230 } 231 232 right[leftmost] = v; 233 right[v] = rightmost; 234 installed[v] = true; 235 236 } 237 238 graph::detail::accumulate_offsets 239 (*ordering_begin,0,g,x,delta_x,left,right); 240 241 vertex_iterator_t vi, vi_end; 242 for(boost::tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi) 243 { 244 vertex_t v(*vi); 245 drawing[v].x = x[v]; 246 drawing[v].y = y[v]; 247 } 248 249 } 250 251 252 253 254 template<typename Graph, 255 typename PlanarEmbedding, 256 typename ForwardIterator, 257 typename GridPositionMap> chrobak_payne_straight_line_drawing(const Graph & g,PlanarEmbedding embedding,ForwardIterator ord_begin,ForwardIterator ord_end,GridPositionMap drawing)258 inline void chrobak_payne_straight_line_drawing(const Graph& g, 259 PlanarEmbedding embedding, 260 ForwardIterator ord_begin, 261 ForwardIterator ord_end, 262 GridPositionMap drawing 263 ) 264 { 265 chrobak_payne_straight_line_drawing(g, 266 embedding, 267 ord_begin, 268 ord_end, 269 drawing, 270 get(vertex_index,g) 271 ); 272 } 273 274 275 276 277 } // namespace boost 278 279 #endif //__CHROBAK_PAYNE_DRAWING_HPP__ 280