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

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