1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/fruchterman_reingold.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,420 @@
1.4 +// Copyright 2004 The Trustees of Indiana University.
1.5 +
1.6 +// Distributed under the Boost Software License, Version 1.0.
1.7 +// (See accompanying file LICENSE_1_0.txt or copy at
1.8 +// http://www.boost.org/LICENSE_1_0.txt)
1.9 +
1.10 +// Authors: Douglas Gregor
1.11 +// Andrew Lumsdaine
1.12 +#ifndef BOOST_GRAPH_FRUCHTERMAN_REINGOLD_FORCE_DIRECTED_LAYOUT_HPP
1.13 +#define BOOST_GRAPH_FRUCHTERMAN_REINGOLD_FORCE_DIRECTED_LAYOUT_HPP
1.14 +
1.15 +#include <cmath>
1.16 +#include <boost/graph/graph_traits.hpp>
1.17 +#include <boost/graph/named_function_params.hpp>
1.18 +#include <boost/graph/simple_point.hpp>
1.19 +#include <vector>
1.20 +#include <list>
1.21 +#include <algorithm> // for std::min and std::max
1.22 +
1.23 +namespace boost {
1.24 +
1.25 +struct square_distance_attractive_force {
1.26 + template<typename Graph, typename T>
1.27 + T
1.28 + operator()(typename graph_traits<Graph>::edge_descriptor,
1.29 + T k,
1.30 + T d,
1.31 + const Graph&) const
1.32 + {
1.33 + return d * d / k;
1.34 + }
1.35 +};
1.36 +
1.37 +struct square_distance_repulsive_force {
1.38 + template<typename Graph, typename T>
1.39 + T
1.40 + operator()(typename graph_traits<Graph>::vertex_descriptor,
1.41 + typename graph_traits<Graph>::vertex_descriptor,
1.42 + T k,
1.43 + T d,
1.44 + const Graph&) const
1.45 + {
1.46 + return k * k / d;
1.47 + }
1.48 +};
1.49 +
1.50 +template<typename T>
1.51 +struct linear_cooling {
1.52 + typedef T result_type;
1.53 +
1.54 + linear_cooling(std::size_t iterations)
1.55 + : temp(T(iterations) / T(10)), step(0.1) { }
1.56 +
1.57 + linear_cooling(std::size_t iterations, T temp)
1.58 + : temp(temp), step(temp / T(iterations)) { }
1.59 +
1.60 + T operator()()
1.61 + {
1.62 + T old_temp = temp;
1.63 + temp -= step;
1.64 + if (temp < T(0)) temp = T(0);
1.65 + return old_temp;
1.66 + }
1.67 +
1.68 + private:
1.69 + T temp;
1.70 + T step;
1.71 +};
1.72 +
1.73 +struct all_force_pairs
1.74 +{
1.75 + template<typename Graph, typename ApplyForce >
1.76 + void operator()(const Graph& g, ApplyForce apply_force)
1.77 + {
1.78 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
1.79 + vertex_iterator v, end;
1.80 + for (tie(v, end) = vertices(g); v != end; ++v) {
1.81 + vertex_iterator u = v;
1.82 + for (++u; u != end; ++u) {
1.83 + apply_force(*u, *v);
1.84 + apply_force(*v, *u);
1.85 + }
1.86 + }
1.87 + }
1.88 +};
1.89 +
1.90 +template<typename Dim, typename PositionMap>
1.91 +struct grid_force_pairs
1.92 +{
1.93 + template<typename Graph>
1.94 + explicit
1.95 + grid_force_pairs(Dim width, Dim height, PositionMap position, const Graph& g)
1.96 + : width(width), height(height), position(position)
1.97 + {
1.98 +#ifndef BOOST_NO_STDC_NAMESPACE
1.99 + using std::sqrt;
1.100 +#endif // BOOST_NO_STDC_NAMESPACE
1.101 + two_k = Dim(2) * sqrt(width*height / num_vertices(g));
1.102 + }
1.103 +
1.104 + template<typename Graph, typename ApplyForce >
1.105 + void operator()(const Graph& g, ApplyForce apply_force)
1.106 + {
1.107 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
1.108 + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
1.109 + typedef std::list<vertex_descriptor> bucket_t;
1.110 + typedef std::vector<bucket_t> buckets_t;
1.111 +
1.112 + std::size_t columns = std::size_t(width / two_k + Dim(1));
1.113 + std::size_t rows = std::size_t(height / two_k + Dim(1));
1.114 + buckets_t buckets(rows * columns);
1.115 + vertex_iterator v, v_end;
1.116 + for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
1.117 + std::size_t column = std::size_t((position[*v].x + width / 2) / two_k);
1.118 + std::size_t row = std::size_t((position[*v].y + height / 2) / two_k);
1.119 +
1.120 + if (column >= columns) column = columns - 1;
1.121 + if (row >= rows) row = rows - 1;
1.122 + buckets[row * columns + column].push_back(*v);
1.123 + }
1.124 +
1.125 + for (std::size_t row = 0; row < rows; ++row)
1.126 + for (std::size_t column = 0; column < columns; ++column) {
1.127 + bucket_t& bucket = buckets[row * columns + column];
1.128 + typedef typename bucket_t::iterator bucket_iterator;
1.129 + for (bucket_iterator u = bucket.begin(); u != bucket.end(); ++u) {
1.130 + // Repulse vertices in this bucket
1.131 + bucket_iterator v = u;
1.132 + for (++v; v != bucket.end(); ++v) {
1.133 + apply_force(*u, *v);
1.134 + apply_force(*v, *u);
1.135 + }
1.136 +
1.137 + std::size_t adj_start_row = row == 0? 0 : row - 1;
1.138 + std::size_t adj_end_row = row == rows - 1? row : row + 1;
1.139 + std::size_t adj_start_column = column == 0? 0 : column - 1;
1.140 + std::size_t adj_end_column = column == columns - 1? column : column + 1;
1.141 + for (std::size_t other_row = adj_start_row; other_row <= adj_end_row;
1.142 + ++other_row)
1.143 + for (std::size_t other_column = adj_start_column;
1.144 + other_column <= adj_end_column; ++other_column)
1.145 + if (other_row != row || other_column != column) {
1.146 + // Repulse vertices in this bucket
1.147 + bucket_t& other_bucket
1.148 + = buckets[other_row * columns + other_column];
1.149 + for (v = other_bucket.begin(); v != other_bucket.end(); ++v)
1.150 + apply_force(*u, *v);
1.151 + }
1.152 + }
1.153 + }
1.154 + }
1.155 +
1.156 + private:
1.157 + Dim width;
1.158 + Dim height;
1.159 + PositionMap position;
1.160 + Dim two_k;
1.161 +};
1.162 +
1.163 +template<typename Dim, typename PositionMap, typename Graph>
1.164 +inline grid_force_pairs<Dim, PositionMap>
1.165 +make_grid_force_pairs(Dim width, Dim height, const PositionMap& position,
1.166 + const Graph& g)
1.167 +{ return grid_force_pairs<Dim, PositionMap>(width, height, position, g); }
1.168 +
1.169 +template<typename Graph, typename PositionMap, typename Dim>
1.170 +void
1.171 +scale_graph(const Graph& g, PositionMap position,
1.172 + Dim left, Dim top, Dim right, Dim bottom)
1.173 +{
1.174 + if (num_vertices(g) == 0) return;
1.175 +
1.176 + if (bottom > top) {
1.177 + using std::swap;
1.178 + swap(bottom, top);
1.179 + }
1.180 +
1.181 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
1.182 +
1.183 + // Find min/max ranges
1.184 + Dim minX = position[*vertices(g).first].x, maxX = minX;
1.185 + Dim minY = position[*vertices(g).first].y, maxY = minY;
1.186 + vertex_iterator vi, vi_end;
1.187 + for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
1.188 + BOOST_USING_STD_MIN();
1.189 + BOOST_USING_STD_MAX();
1.190 + minX = min BOOST_PREVENT_MACRO_SUBSTITUTION (minX, position[*vi].x);
1.191 + maxX = max BOOST_PREVENT_MACRO_SUBSTITUTION (maxX, position[*vi].x);
1.192 + minY = min BOOST_PREVENT_MACRO_SUBSTITUTION (minY, position[*vi].y);
1.193 + maxY = max BOOST_PREVENT_MACRO_SUBSTITUTION (maxY, position[*vi].y);
1.194 + }
1.195 +
1.196 + // Scale to bounding box provided
1.197 + for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
1.198 + position[*vi].x = ((position[*vi].x - minX) / (maxX - minX))
1.199 + * (right - left) + left;
1.200 + position[*vi].y = ((position[*vi].y - minY) / (maxY - minY))
1.201 + * (top - bottom) + bottom;
1.202 + }
1.203 +}
1.204 +
1.205 +namespace detail {
1.206 + template<typename PositionMap, typename DisplacementMap,
1.207 + typename RepulsiveForce, typename Dim, typename Graph>
1.208 + struct fr_apply_force
1.209 + {
1.210 + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
1.211 +
1.212 + fr_apply_force(const PositionMap& position,
1.213 + const DisplacementMap& displacement,
1.214 + RepulsiveForce repulsive_force, Dim k, const Graph& g)
1.215 + : position(position), displacement(displacement),
1.216 + repulsive_force(repulsive_force), k(k), g(g)
1.217 + { }
1.218 +
1.219 + void operator()(vertex_descriptor u, vertex_descriptor v)
1.220 + {
1.221 +#ifndef BOOST_NO_STDC_NAMESPACE
1.222 + using std::sqrt;
1.223 +#endif // BOOST_NO_STDC_NAMESPACE
1.224 + if (u != v) {
1.225 + Dim delta_x = position[v].x - position[u].x;
1.226 + Dim delta_y = position[v].y - position[u].y;
1.227 + Dim dist = sqrt(delta_x * delta_x + delta_y * delta_y);
1.228 + Dim fr = repulsive_force(u, v, k, dist, g);
1.229 + displacement[v].x += delta_x / dist * fr;
1.230 + displacement[v].y += delta_y / dist * fr;
1.231 + }
1.232 + }
1.233 +
1.234 + private:
1.235 + PositionMap position;
1.236 + DisplacementMap displacement;
1.237 + RepulsiveForce repulsive_force;
1.238 + Dim k;
1.239 + const Graph& g;
1.240 + };
1.241 +
1.242 +} // end namespace detail
1.243 +
1.244 +template<typename Graph, typename PositionMap, typename Dim,
1.245 + typename AttractiveForce, typename RepulsiveForce,
1.246 + typename ForcePairs, typename Cooling, typename DisplacementMap>
1.247 +void
1.248 +fruchterman_reingold_force_directed_layout
1.249 + (const Graph& g,
1.250 + PositionMap position,
1.251 + Dim width,
1.252 + Dim height,
1.253 + AttractiveForce attractive_force,
1.254 + RepulsiveForce repulsive_force,
1.255 + ForcePairs force_pairs,
1.256 + Cooling cool,
1.257 + DisplacementMap displacement)
1.258 +{
1.259 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
1.260 + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
1.261 + typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
1.262 +
1.263 +#ifndef BOOST_NO_STDC_NAMESPACE
1.264 + using std::sqrt;
1.265 +#endif // BOOST_NO_STDC_NAMESPACE
1.266 +
1.267 + Dim area = width * height;
1.268 + // assume positions are initialized randomly
1.269 + Dim k = sqrt(area / num_vertices(g));
1.270 +
1.271 + detail::fr_apply_force<PositionMap, DisplacementMap,
1.272 + RepulsiveForce, Dim, Graph>
1.273 + apply_force(position, displacement, repulsive_force, k, g);
1.274 +
1.275 + Dim temp = cool();
1.276 + if (temp) do {
1.277 + // Calculate repulsive forces
1.278 + vertex_iterator v, v_end;
1.279 + for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
1.280 + displacement[*v].x = 0;
1.281 + displacement[*v].y = 0;
1.282 + }
1.283 + force_pairs(g, apply_force);
1.284 +
1.285 + // Calculate attractive forces
1.286 + edge_iterator e, e_end;
1.287 + for (tie(e, e_end) = edges(g); e != e_end; ++e) {
1.288 + vertex_descriptor v = source(*e, g);
1.289 + vertex_descriptor u = target(*e, g);
1.290 + Dim delta_x = position[v].x - position[u].x;
1.291 + Dim delta_y = position[v].y - position[u].y;
1.292 + Dim dist = sqrt(delta_x * delta_x + delta_y * delta_y);
1.293 + Dim fa = attractive_force(*e, k, dist, g);
1.294 +
1.295 + displacement[v].x -= delta_x / dist * fa;
1.296 + displacement[v].y -= delta_y / dist * fa;
1.297 + displacement[u].x += delta_x / dist * fa;
1.298 + displacement[u].y += delta_y / dist * fa;
1.299 + }
1.300 +
1.301 + // Update positions
1.302 + for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
1.303 + BOOST_USING_STD_MIN();
1.304 + BOOST_USING_STD_MAX();
1.305 + Dim disp_size = sqrt(displacement[*v].x * displacement[*v].x
1.306 + + displacement[*v].y * displacement[*v].y);
1.307 + position[*v].x += displacement[*v].x / disp_size
1.308 + * min BOOST_PREVENT_MACRO_SUBSTITUTION (disp_size, temp);
1.309 + position[*v].y += displacement[*v].y / disp_size
1.310 + * min BOOST_PREVENT_MACRO_SUBSTITUTION (disp_size, temp);
1.311 + position[*v].x = min BOOST_PREVENT_MACRO_SUBSTITUTION
1.312 + (width / 2,
1.313 + max BOOST_PREVENT_MACRO_SUBSTITUTION(-width / 2,
1.314 + position[*v].x));
1.315 + position[*v].y = min BOOST_PREVENT_MACRO_SUBSTITUTION
1.316 + (height / 2,
1.317 + max BOOST_PREVENT_MACRO_SUBSTITUTION(-height / 2,
1.318 + position[*v].y));
1.319 + }
1.320 + } while (temp = cool());
1.321 +}
1.322 +
1.323 +namespace detail {
1.324 + template<typename DisplacementMap>
1.325 + struct fr_force_directed_layout
1.326 + {
1.327 + template<typename Graph, typename PositionMap, typename Dim,
1.328 + typename AttractiveForce, typename RepulsiveForce,
1.329 + typename ForcePairs, typename Cooling,
1.330 + typename Param, typename Tag, typename Rest>
1.331 + static void
1.332 + run(const Graph& g,
1.333 + PositionMap position,
1.334 + Dim width,
1.335 + Dim height,
1.336 + AttractiveForce attractive_force,
1.337 + RepulsiveForce repulsive_force,
1.338 + ForcePairs force_pairs,
1.339 + Cooling cool,
1.340 + DisplacementMap displacement,
1.341 + const bgl_named_params<Param, Tag, Rest>&)
1.342 + {
1.343 + fruchterman_reingold_force_directed_layout
1.344 + (g, position, width, height, attractive_force, repulsive_force,
1.345 + force_pairs, cool, displacement);
1.346 + }
1.347 + };
1.348 +
1.349 + template<>
1.350 + struct fr_force_directed_layout<error_property_not_found>
1.351 + {
1.352 + template<typename Graph, typename PositionMap, typename Dim,
1.353 + typename AttractiveForce, typename RepulsiveForce,
1.354 + typename ForcePairs, typename Cooling,
1.355 + typename Param, typename Tag, typename Rest>
1.356 + static void
1.357 + run(const Graph& g,
1.358 + PositionMap position,
1.359 + Dim width,
1.360 + Dim height,
1.361 + AttractiveForce attractive_force,
1.362 + RepulsiveForce repulsive_force,
1.363 + ForcePairs force_pairs,
1.364 + Cooling cool,
1.365 + error_property_not_found,
1.366 + const bgl_named_params<Param, Tag, Rest>& params)
1.367 + {
1.368 + std::vector<simple_point<Dim> > displacements(num_vertices(g));
1.369 + fruchterman_reingold_force_directed_layout
1.370 + (g, position, width, height, attractive_force, repulsive_force,
1.371 + force_pairs, cool,
1.372 + make_iterator_property_map
1.373 + (displacements.begin(),
1.374 + choose_const_pmap(get_param(params, vertex_index), g,
1.375 + vertex_index),
1.376 + simple_point<Dim>()));
1.377 + }
1.378 + };
1.379 +
1.380 +} // end namespace detail
1.381 +
1.382 +template<typename Graph, typename PositionMap, typename Dim, typename Param,
1.383 + typename Tag, typename Rest>
1.384 +void
1.385 +fruchterman_reingold_force_directed_layout
1.386 + (const Graph& g,
1.387 + PositionMap position,
1.388 + Dim width,
1.389 + Dim height,
1.390 + const bgl_named_params<Param, Tag, Rest>& params)
1.391 +{
1.392 + typedef typename property_value<bgl_named_params<Param,Tag,Rest>,
1.393 + vertex_displacement_t>::type D;
1.394 +
1.395 + detail::fr_force_directed_layout<D>::run
1.396 + (g, position, width, height,
1.397 + choose_param(get_param(params, attractive_force_t()),
1.398 + square_distance_attractive_force()),
1.399 + choose_param(get_param(params, repulsive_force_t()),
1.400 + square_distance_repulsive_force()),
1.401 + choose_param(get_param(params, force_pairs_t()),
1.402 + make_grid_force_pairs(width, height, position, g)),
1.403 + choose_param(get_param(params, cooling_t()),
1.404 + linear_cooling<Dim>(100)),
1.405 + get_param(params, vertex_displacement_t()),
1.406 + params);
1.407 +}
1.408 +
1.409 +template<typename Graph, typename PositionMap, typename Dim>
1.410 +void
1.411 +fruchterman_reingold_force_directed_layout(const Graph& g,
1.412 + PositionMap position,
1.413 + Dim width,
1.414 + Dim height)
1.415 +{
1.416 + fruchterman_reingold_force_directed_layout
1.417 + (g, position, width, height,
1.418 + attractive_force(square_distance_attractive_force()));
1.419 +}
1.420 +
1.421 +} // end namespace boost
1.422 +
1.423 +#endif // BOOST_GRAPH_FRUCHTERMAN_REINGOLD_FORCE_DIRECTED_LAYOUT_HPP