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

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