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> |
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> |
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> |
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 | |