]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright 2004 The Trustees of Indiana University. |
2 | ||
3 | // Distributed under the Boost Software License, Version 1.0. | |
4 | // (See accompanying file LICENSE_1_0.txt or copy at | |
5 | // http://www.boost.org/LICENSE_1_0.txt) | |
6 | ||
7 | // Authors: Jeremiah Willcock | |
8 | // Douglas Gregor | |
9 | // Andrew Lumsdaine | |
10 | #ifndef BOOST_GRAPH_GURSOY_ATUN_LAYOUT_HPP | |
11 | #define BOOST_GRAPH_GURSOY_ATUN_LAYOUT_HPP | |
12 | ||
13 | // Gürsoy-Atun graph layout, based on: | |
14 | // "Neighbourhood Preserving Load Balancing: A Self-Organizing Approach" | |
15 | // in 6th International Euro-Par Conference Munich, Germany, August 29 – September 1, 2000 Proceedings, | |
16 | // pp 234-241 | |
17 | // http://dx.doi.org/10.1007/3-540-44520-X_32 | |
18 | ||
19 | #include <boost/config/no_tr1/cmath.hpp> | |
20 | #include <boost/throw_exception.hpp> | |
21 | #include <boost/assert.hpp> | |
22 | #include <vector> | |
23 | #include <exception> | |
24 | #include <algorithm> | |
25 | ||
26 | #include <boost/graph/visitors.hpp> | |
27 | #include <boost/graph/properties.hpp> | |
28 | #include <boost/random/uniform_01.hpp> | |
29 | #include <boost/random/linear_congruential.hpp> | |
30 | #include <boost/shared_ptr.hpp> | |
31 | #include <boost/graph/breadth_first_search.hpp> | |
32 | #include <boost/graph/dijkstra_shortest_paths.hpp> | |
33 | #include <boost/graph/named_function_params.hpp> | |
34 | #include <boost/graph/topology.hpp> | |
35 | ||
36 | namespace boost { | |
37 | ||
38 | namespace detail { | |
39 | ||
40 | struct over_distance_limit : public std::exception {}; | |
41 | ||
42 | template <typename PositionMap, typename NodeDistanceMap, typename Topology, | |
43 | typename Graph> | |
44 | struct update_position_visitor { | |
45 | typedef typename Topology::point_type Point; | |
46 | PositionMap position_map; | |
47 | NodeDistanceMap node_distance; | |
48 | const Topology& space; | |
49 | Point input_vector; | |
50 | double distance_limit; | |
51 | double learning_constant; | |
52 | double falloff_ratio; | |
53 | ||
54 | typedef boost::on_examine_vertex event_filter; | |
55 | ||
56 | typedef typename graph_traits<Graph>::vertex_descriptor | |
57 | vertex_descriptor; | |
58 | ||
59 | update_position_visitor(PositionMap position_map, | |
60 | NodeDistanceMap node_distance, | |
61 | const Topology& space, | |
62 | const Point& input_vector, | |
63 | double distance_limit, | |
64 | double learning_constant, | |
65 | double falloff_ratio): | |
66 | position_map(position_map), node_distance(node_distance), | |
67 | space(space), | |
68 | input_vector(input_vector), distance_limit(distance_limit), | |
69 | learning_constant(learning_constant), falloff_ratio(falloff_ratio) {} | |
70 | ||
71 | void operator()(vertex_descriptor v, const Graph&) const | |
72 | { | |
73 | #ifndef BOOST_NO_STDC_NAMESPACE | |
74 | using std::pow; | |
75 | #endif | |
76 | ||
77 | if (get(node_distance, v) > distance_limit) | |
78 | BOOST_THROW_EXCEPTION(over_distance_limit()); | |
79 | Point old_position = get(position_map, v); | |
80 | double distance = get(node_distance, v); | |
81 | double fraction = | |
82 | learning_constant * pow(falloff_ratio, distance * distance); | |
83 | put(position_map, v, | |
84 | space.move_position_toward(old_position, fraction, input_vector)); | |
85 | } | |
86 | }; | |
87 | ||
88 | template<typename EdgeWeightMap> | |
89 | struct gursoy_shortest | |
90 | { | |
91 | template<typename Graph, typename NodeDistanceMap, typename UpdatePosition> | |
92 | static inline void | |
93 | run(const Graph& g, typename graph_traits<Graph>::vertex_descriptor s, | |
94 | NodeDistanceMap node_distance, UpdatePosition& update_position, | |
95 | EdgeWeightMap weight) | |
96 | { | |
97 | boost::dijkstra_shortest_paths(g, s, weight_map(weight). | |
98 | visitor(boost::make_dijkstra_visitor(std::make_pair( | |
99 | boost::record_distances(node_distance, boost::on_edge_relaxed()), | |
100 | update_position)))); | |
101 | } | |
102 | }; | |
103 | ||
104 | template<> | |
105 | struct gursoy_shortest<dummy_property_map> | |
106 | { | |
107 | template<typename Graph, typename NodeDistanceMap, typename UpdatePosition> | |
108 | static inline void | |
109 | run(const Graph& g, typename graph_traits<Graph>::vertex_descriptor s, | |
110 | NodeDistanceMap node_distance, UpdatePosition& update_position, | |
111 | dummy_property_map) | |
112 | { | |
113 | boost::breadth_first_search(g, s, | |
114 | visitor(boost::make_bfs_visitor(std::make_pair( | |
115 | boost::record_distances(node_distance, boost::on_tree_edge()), | |
116 | update_position)))); | |
117 | } | |
118 | }; | |
119 | ||
120 | } // namespace detail | |
121 | ||
122 | template <typename VertexListAndIncidenceGraph, typename Topology, | |
123 | typename PositionMap, typename Diameter, typename VertexIndexMap, | |
124 | typename EdgeWeightMap> | |
125 | void | |
126 | gursoy_atun_step | |
127 | (const VertexListAndIncidenceGraph& graph, | |
128 | const Topology& space, | |
129 | PositionMap position, | |
130 | Diameter diameter, | |
131 | double learning_constant, | |
132 | VertexIndexMap vertex_index_map, | |
133 | EdgeWeightMap weight) | |
134 | { | |
135 | #ifndef BOOST_NO_STDC_NAMESPACE | |
136 | using std::pow; | |
137 | using std::exp; | |
138 | #endif | |
139 | ||
140 | typedef typename graph_traits<VertexListAndIncidenceGraph>::vertex_iterator | |
141 | vertex_iterator; | |
142 | typedef typename graph_traits<VertexListAndIncidenceGraph>::vertex_descriptor | |
143 | vertex_descriptor; | |
144 | typedef typename Topology::point_type point_type; | |
145 | vertex_iterator i, iend; | |
146 | std::vector<double> distance_from_input_vector(num_vertices(graph)); | |
147 | typedef boost::iterator_property_map<std::vector<double>::iterator, | |
148 | VertexIndexMap, | |
149 | double, double&> | |
150 | DistanceFromInputMap; | |
151 | DistanceFromInputMap distance_from_input(distance_from_input_vector.begin(), | |
152 | vertex_index_map); | |
153 | std::vector<double> node_distance_map_vector(num_vertices(graph)); | |
154 | typedef boost::iterator_property_map<std::vector<double>::iterator, | |
155 | VertexIndexMap, | |
156 | double, double&> | |
157 | NodeDistanceMap; | |
158 | NodeDistanceMap node_distance(node_distance_map_vector.begin(), | |
159 | vertex_index_map); | |
160 | point_type input_vector = space.random_point(); | |
161 | vertex_descriptor min_distance_loc | |
162 | = graph_traits<VertexListAndIncidenceGraph>::null_vertex(); | |
163 | double min_distance = 0.0; | |
164 | bool min_distance_unset = true; | |
165 | for (boost::tie(i, iend) = vertices(graph); i != iend; ++i) { | |
166 | double this_distance = space.distance(get(position, *i), input_vector); | |
167 | put(distance_from_input, *i, this_distance); | |
168 | if (min_distance_unset || this_distance < min_distance) { | |
169 | min_distance = this_distance; | |
170 | min_distance_loc = *i; | |
171 | } | |
172 | min_distance_unset = false; | |
173 | } | |
174 | BOOST_ASSERT (!min_distance_unset); // Graph must have at least one vertex | |
175 | boost::detail::update_position_visitor< | |
176 | PositionMap, NodeDistanceMap, Topology, | |
177 | VertexListAndIncidenceGraph> | |
178 | update_position(position, node_distance, space, | |
179 | input_vector, diameter, learning_constant, | |
180 | exp(-1. / (2 * diameter * diameter))); | |
181 | std::fill(node_distance_map_vector.begin(), node_distance_map_vector.end(), 0); | |
182 | try { | |
183 | typedef detail::gursoy_shortest<EdgeWeightMap> shortest; | |
184 | shortest::run(graph, min_distance_loc, node_distance, update_position, | |
185 | weight); | |
186 | } catch (detail::over_distance_limit) { | |
187 | /* Thrown to break out of BFS or Dijkstra early */ | |
188 | } | |
189 | } | |
190 | ||
191 | template <typename VertexListAndIncidenceGraph, typename Topology, | |
192 | typename PositionMap, typename VertexIndexMap, | |
193 | typename EdgeWeightMap> | |
194 | void gursoy_atun_refine(const VertexListAndIncidenceGraph& graph, | |
195 | const Topology& space, | |
196 | PositionMap position, | |
197 | int nsteps, | |
198 | double diameter_initial, | |
199 | double diameter_final, | |
200 | double learning_constant_initial, | |
201 | double learning_constant_final, | |
202 | VertexIndexMap vertex_index_map, | |
203 | EdgeWeightMap weight) | |
204 | { | |
205 | #ifndef BOOST_NO_STDC_NAMESPACE | |
206 | using std::pow; | |
207 | using std::exp; | |
208 | #endif | |
209 | ||
210 | typedef typename graph_traits<VertexListAndIncidenceGraph>::vertex_iterator | |
211 | vertex_iterator; | |
212 | vertex_iterator i, iend; | |
213 | double diameter_ratio = (double)diameter_final / diameter_initial; | |
214 | double learning_constant_ratio = | |
215 | learning_constant_final / learning_constant_initial; | |
216 | std::vector<double> distance_from_input_vector(num_vertices(graph)); | |
217 | typedef boost::iterator_property_map<std::vector<double>::iterator, | |
218 | VertexIndexMap, | |
219 | double, double&> | |
220 | DistanceFromInputMap; | |
221 | DistanceFromInputMap distance_from_input(distance_from_input_vector.begin(), | |
222 | vertex_index_map); | |
223 | std::vector<int> node_distance_map_vector(num_vertices(graph)); | |
224 | typedef boost::iterator_property_map<std::vector<int>::iterator, | |
225 | VertexIndexMap, double, double&> | |
226 | NodeDistanceMap; | |
227 | NodeDistanceMap node_distance(node_distance_map_vector.begin(), | |
228 | vertex_index_map); | |
229 | for (int round = 0; round < nsteps; ++round) { | |
230 | double part_done = (double)round / (nsteps - 1); | |
231 | // fprintf(stderr, "%2d%% done\n", int(rint(part_done * 100.))); | |
232 | int diameter = (int)(diameter_initial * pow(diameter_ratio, part_done)); | |
233 | double learning_constant = | |
234 | learning_constant_initial * pow(learning_constant_ratio, part_done); | |
235 | gursoy_atun_step(graph, space, position, diameter, learning_constant, | |
236 | vertex_index_map, weight); | |
237 | } | |
238 | } | |
239 | ||
240 | template <typename VertexListAndIncidenceGraph, typename Topology, | |
241 | typename PositionMap, typename VertexIndexMap, | |
242 | typename EdgeWeightMap> | |
243 | void gursoy_atun_layout(const VertexListAndIncidenceGraph& graph, | |
244 | const Topology& space, | |
245 | PositionMap position, | |
246 | int nsteps, | |
247 | double diameter_initial, | |
248 | double diameter_final, | |
249 | double learning_constant_initial, | |
250 | double learning_constant_final, | |
251 | VertexIndexMap vertex_index_map, | |
252 | EdgeWeightMap weight) | |
253 | { | |
254 | typedef typename graph_traits<VertexListAndIncidenceGraph>::vertex_iterator | |
255 | vertex_iterator; | |
256 | vertex_iterator i, iend; | |
257 | for (boost::tie(i, iend) = vertices(graph); i != iend; ++i) { | |
258 | put(position, *i, space.random_point()); | |
259 | } | |
260 | gursoy_atun_refine(graph, space, | |
261 | position, nsteps, | |
262 | diameter_initial, diameter_final, | |
263 | learning_constant_initial, learning_constant_final, | |
264 | vertex_index_map, weight); | |
265 | } | |
266 | ||
267 | template <typename VertexListAndIncidenceGraph, typename Topology, | |
268 | typename PositionMap, typename VertexIndexMap> | |
269 | void gursoy_atun_layout(const VertexListAndIncidenceGraph& graph, | |
270 | const Topology& space, | |
271 | PositionMap position, | |
272 | int nsteps, | |
273 | double diameter_initial, | |
274 | double diameter_final, | |
275 | double learning_constant_initial, | |
276 | double learning_constant_final, | |
277 | VertexIndexMap vertex_index_map) | |
278 | { | |
279 | gursoy_atun_layout(graph, space, position, nsteps, | |
280 | diameter_initial, diameter_final, | |
281 | learning_constant_initial, learning_constant_final, | |
282 | vertex_index_map, dummy_property_map()); | |
283 | } | |
284 | ||
285 | template <typename VertexListAndIncidenceGraph, typename Topology, | |
286 | typename PositionMap> | |
287 | void gursoy_atun_layout(const VertexListAndIncidenceGraph& graph, | |
288 | const Topology& space, | |
289 | PositionMap position, | |
290 | int nsteps, | |
291 | double diameter_initial, | |
292 | double diameter_final = 1.0, | |
293 | double learning_constant_initial = 0.8, | |
294 | double learning_constant_final = 0.2) | |
295 | { | |
296 | gursoy_atun_layout(graph, space, position, nsteps, diameter_initial, | |
297 | diameter_final, learning_constant_initial, | |
298 | learning_constant_final, get(vertex_index, graph)); | |
299 | } | |
300 | ||
301 | template <typename VertexListAndIncidenceGraph, typename Topology, | |
302 | typename PositionMap> | |
303 | void gursoy_atun_layout(const VertexListAndIncidenceGraph& graph, | |
304 | const Topology& space, | |
305 | PositionMap position, | |
306 | int nsteps) | |
307 | { | |
308 | #ifndef BOOST_NO_STDC_NAMESPACE | |
309 | using std::sqrt; | |
310 | #endif | |
311 | ||
312 | gursoy_atun_layout(graph, space, position, nsteps, | |
313 | sqrt((double)num_vertices(graph))); | |
314 | } | |
315 | ||
316 | template <typename VertexListAndIncidenceGraph, typename Topology, | |
317 | typename PositionMap> | |
318 | void gursoy_atun_layout(const VertexListAndIncidenceGraph& graph, | |
319 | const Topology& space, | |
320 | PositionMap position) | |
321 | { | |
322 | gursoy_atun_layout(graph, space, position, num_vertices(graph)); | |
323 | } | |
324 | ||
325 | template<typename VertexListAndIncidenceGraph, typename Topology, | |
326 | typename PositionMap, typename P, typename T, typename R> | |
327 | void | |
328 | gursoy_atun_layout(const VertexListAndIncidenceGraph& graph, | |
329 | const Topology& space, | |
330 | PositionMap position, | |
331 | const bgl_named_params<P,T,R>& params) | |
332 | { | |
333 | #ifndef BOOST_NO_STDC_NAMESPACE | |
334 | using std::sqrt; | |
335 | #endif | |
336 | ||
337 | std::pair<double, double> diam(sqrt(double(num_vertices(graph))), 1.0); | |
338 | std::pair<double, double> learn(0.8, 0.2); | |
339 | gursoy_atun_layout(graph, space, position, | |
340 | choose_param(get_param(params, iterations_t()), | |
341 | num_vertices(graph)), | |
342 | choose_param(get_param(params, diameter_range_t()), | |
343 | diam).first, | |
344 | choose_param(get_param(params, diameter_range_t()), | |
345 | diam).second, | |
346 | choose_param(get_param(params, learning_constant_range_t()), | |
347 | learn).first, | |
348 | choose_param(get_param(params, learning_constant_range_t()), | |
349 | learn).second, | |
350 | choose_const_pmap(get_param(params, vertex_index), graph, | |
351 | vertex_index), | |
352 | choose_param(get_param(params, edge_weight), | |
353 | dummy_property_map())); | |
354 | } | |
355 | ||
356 | } // namespace boost | |
357 | ||
358 | #endif // BOOST_GRAPH_GURSOY_ATUN_LAYOUT_HPP |