1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/graph/kamada_kawai_spring_layout.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,542 @@
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_KAMADA_KAWAI_SPRING_LAYOUT_HPP
1.13 +#define BOOST_GRAPH_KAMADA_KAWAI_SPRING_LAYOUT_HPP
1.14 +
1.15 +#include <boost/graph/graph_traits.hpp>
1.16 +#include <boost/graph/johnson_all_pairs_shortest.hpp>
1.17 +#include <boost/type_traits/is_convertible.hpp>
1.18 +#include <utility>
1.19 +#include <iterator>
1.20 +#include <vector>
1.21 +#include <boost/limits.hpp>
1.22 +#include <cmath>
1.23 +
1.24 +namespace boost {
1.25 + namespace detail { namespace graph {
1.26 + /**
1.27 + * Denotes an edge or display area side length used to scale a
1.28 + * Kamada-Kawai drawing.
1.29 + */
1.30 + template<bool Edge, typename T>
1.31 + struct edge_or_side
1.32 + {
1.33 + explicit edge_or_side(T value) : value(value) {}
1.34 +
1.35 + T value;
1.36 + };
1.37 +
1.38 + /**
1.39 + * Compute the edge length from an edge length. This is trivial.
1.40 + */
1.41 + template<typename Graph, typename DistanceMap, typename IndexMap,
1.42 + typename T>
1.43 + T compute_edge_length(const Graph&, DistanceMap, IndexMap,
1.44 + edge_or_side<true, T> length)
1.45 + { return length.value; }
1.46 +
1.47 + /**
1.48 + * Compute the edge length based on the display area side
1.49 + length. We do this by dividing the side length by the largest
1.50 + shortest distance between any two vertices in the graph.
1.51 + */
1.52 + template<typename Graph, typename DistanceMap, typename IndexMap,
1.53 + typename T>
1.54 + T
1.55 + compute_edge_length(const Graph& g, DistanceMap distance, IndexMap index,
1.56 + edge_or_side<false, T> length)
1.57 + {
1.58 + T result(0);
1.59 +
1.60 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
1.61 +
1.62 + for (vertex_iterator ui = vertices(g).first, end = vertices(g).second;
1.63 + ui != end; ++ui) {
1.64 + vertex_iterator vi = ui;
1.65 + for (++vi; vi != end; ++vi) {
1.66 + T dij = distance[get(index, *ui)][get(index, *vi)];
1.67 + if (dij > result) result = dij;
1.68 + }
1.69 + }
1.70 + return length.value / result;
1.71 + }
1.72 +
1.73 + /**
1.74 + * Implementation of the Kamada-Kawai spring layout algorithm.
1.75 + */
1.76 + template<typename Graph, typename PositionMap, typename WeightMap,
1.77 + typename EdgeOrSideLength, typename Done,
1.78 + typename VertexIndexMap, typename DistanceMatrix,
1.79 + typename SpringStrengthMatrix, typename PartialDerivativeMap>
1.80 + struct kamada_kawai_spring_layout_impl
1.81 + {
1.82 + typedef typename property_traits<WeightMap>::value_type weight_type;
1.83 + typedef std::pair<weight_type, weight_type> deriv_type;
1.84 + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
1.85 + typedef typename graph_traits<Graph>::vertex_descriptor
1.86 + vertex_descriptor;
1.87 +
1.88 + kamada_kawai_spring_layout_impl(
1.89 + const Graph& g,
1.90 + PositionMap position,
1.91 + WeightMap weight,
1.92 + EdgeOrSideLength edge_or_side_length,
1.93 + Done done,
1.94 + weight_type spring_constant,
1.95 + VertexIndexMap index,
1.96 + DistanceMatrix distance,
1.97 + SpringStrengthMatrix spring_strength,
1.98 + PartialDerivativeMap partial_derivatives)
1.99 + : g(g), position(position), weight(weight),
1.100 + edge_or_side_length(edge_or_side_length), done(done),
1.101 + spring_constant(spring_constant), index(index), distance(distance),
1.102 + spring_strength(spring_strength),
1.103 + partial_derivatives(partial_derivatives) {}
1.104 +
1.105 + // Compute contribution of vertex i to the first partial
1.106 + // derivatives (dE/dx_m, dE/dy_m) (for vertex m)
1.107 + deriv_type
1.108 + compute_partial_derivative(vertex_descriptor m, vertex_descriptor i)
1.109 + {
1.110 +#ifndef BOOST_NO_STDC_NAMESPACE
1.111 + using std::sqrt;
1.112 +#endif // BOOST_NO_STDC_NAMESPACE
1.113 +
1.114 + deriv_type result(0, 0);
1.115 + if (i != m) {
1.116 + weight_type x_diff = position[m].x - position[i].x;
1.117 + weight_type y_diff = position[m].y - position[i].y;
1.118 + weight_type dist = sqrt(x_diff * x_diff + y_diff * y_diff);
1.119 + result.first = spring_strength[get(index, m)][get(index, i)]
1.120 + * (x_diff - distance[get(index, m)][get(index, i)]*x_diff/dist);
1.121 + result.second = spring_strength[get(index, m)][get(index, i)]
1.122 + * (y_diff - distance[get(index, m)][get(index, i)]*y_diff/dist);
1.123 + }
1.124 +
1.125 + return result;
1.126 + }
1.127 +
1.128 + // Compute partial derivatives dE/dx_m and dE/dy_m
1.129 + deriv_type
1.130 + compute_partial_derivatives(vertex_descriptor m)
1.131 + {
1.132 +#ifndef BOOST_NO_STDC_NAMESPACE
1.133 + using std::sqrt;
1.134 +#endif // BOOST_NO_STDC_NAMESPACE
1.135 +
1.136 + deriv_type result(0, 0);
1.137 +
1.138 + // TBD: looks like an accumulate to me
1.139 + std::pair<vertex_iterator, vertex_iterator> verts = vertices(g);
1.140 + for (/* no init */; verts.first != verts.second; ++verts.first) {
1.141 + vertex_descriptor i = *verts.first;
1.142 + deriv_type deriv = compute_partial_derivative(m, i);
1.143 + result.first += deriv.first;
1.144 + result.second += deriv.second;
1.145 + }
1.146 +
1.147 + return result;
1.148 + }
1.149 +
1.150 + // The actual Kamada-Kawai spring layout algorithm implementation
1.151 + bool run()
1.152 + {
1.153 +#ifndef BOOST_NO_STDC_NAMESPACE
1.154 + using std::sqrt;
1.155 +#endif // BOOST_NO_STDC_NAMESPACE
1.156 +
1.157 + // Compute d_{ij} and place it in the distance matrix
1.158 + if (!johnson_all_pairs_shortest_paths(g, distance, index, weight,
1.159 + weight_type(0)))
1.160 + return false;
1.161 +
1.162 + // Compute L based on side length (if needed), or retrieve L
1.163 + weight_type edge_length =
1.164 + detail::graph::compute_edge_length(g, distance, index,
1.165 + edge_or_side_length);
1.166 +
1.167 + // Compute l_{ij} and k_{ij}
1.168 + const weight_type K = spring_constant;
1.169 + vertex_iterator ui, end = vertices(g).second;
1.170 + for (ui = vertices(g).first; ui != end; ++ui) {
1.171 + vertex_iterator vi = ui;
1.172 + for (++vi; vi != end; ++vi) {
1.173 + weight_type dij = distance[get(index, *ui)][get(index, *vi)];
1.174 + if (dij == (std::numeric_limits<weight_type>::max)())
1.175 + return false;
1.176 + distance[get(index, *ui)][get(index, *vi)] = edge_length * dij;
1.177 + distance[get(index, *vi)][get(index, *ui)] = edge_length * dij;
1.178 + spring_strength[get(index, *ui)][get(index, *vi)] = K/(dij*dij);
1.179 + spring_strength[get(index, *vi)][get(index, *ui)] = K/(dij*dij);
1.180 + }
1.181 + }
1.182 +
1.183 + // Compute Delta_i and find max
1.184 + vertex_descriptor p = *vertices(g).first;
1.185 + weight_type delta_p(0);
1.186 +
1.187 + for (ui = vertices(g).first; ui != end; ++ui) {
1.188 + deriv_type deriv = compute_partial_derivatives(*ui);
1.189 + put(partial_derivatives, *ui, deriv);
1.190 +
1.191 + weight_type delta =
1.192 + sqrt(deriv.first*deriv.first + deriv.second*deriv.second);
1.193 +
1.194 + if (delta > delta_p) {
1.195 + p = *ui;
1.196 + delta_p = delta;
1.197 + }
1.198 + }
1.199 +
1.200 + while (!done(delta_p, p, g, true)) {
1.201 + // The contribution p makes to the partial derivatives of
1.202 + // each vertex. Computing this (at O(n) cost) allows us to
1.203 + // update the delta_i values in O(n) time instead of O(n^2)
1.204 + // time.
1.205 + std::vector<deriv_type> p_partials(num_vertices(g));
1.206 + for (ui = vertices(g).first; ui != end; ++ui) {
1.207 + vertex_descriptor i = *ui;
1.208 + p_partials[get(index, i)] = compute_partial_derivative(i, p);
1.209 + }
1.210 +
1.211 + do {
1.212 + // Compute the 4 elements of the Jacobian
1.213 + weight_type dE_dx_dx = 0, dE_dx_dy = 0, dE_dy_dx = 0, dE_dy_dy = 0;
1.214 + for (ui = vertices(g).first; ui != end; ++ui) {
1.215 + vertex_descriptor i = *ui;
1.216 + if (i != p) {
1.217 + weight_type x_diff = position[p].x - position[i].x;
1.218 + weight_type y_diff = position[p].y - position[i].y;
1.219 + weight_type dist = sqrt(x_diff * x_diff + y_diff * y_diff);
1.220 + weight_type dist_cubed = dist * dist * dist;
1.221 + weight_type k_mi = spring_strength[get(index,p)][get(index,i)];
1.222 + weight_type l_mi = distance[get(index, p)][get(index, i)];
1.223 + dE_dx_dx += k_mi * (1 - (l_mi * y_diff * y_diff)/dist_cubed);
1.224 + dE_dx_dy += k_mi * l_mi * x_diff * y_diff / dist_cubed;
1.225 + dE_dy_dx += k_mi * l_mi * x_diff * y_diff / dist_cubed;
1.226 + dE_dy_dy += k_mi * (1 - (l_mi * x_diff * x_diff)/dist_cubed);
1.227 + }
1.228 + }
1.229 +
1.230 + // Solve for delta_x and delta_y
1.231 + weight_type dE_dx = get(partial_derivatives, p).first;
1.232 + weight_type dE_dy = get(partial_derivatives, p).second;
1.233 +
1.234 + weight_type delta_x =
1.235 + (dE_dx_dy * dE_dy - dE_dy_dy * dE_dx)
1.236 + / (dE_dx_dx * dE_dy_dy - dE_dx_dy * dE_dy_dx);
1.237 +
1.238 + weight_type delta_y =
1.239 + (dE_dx_dx * dE_dy - dE_dy_dx * dE_dx)
1.240 + / (dE_dy_dx * dE_dx_dy - dE_dx_dx * dE_dy_dy);
1.241 +
1.242 +
1.243 + // Move p by (delta_x, delta_y)
1.244 + position[p].x += delta_x;
1.245 + position[p].y += delta_y;
1.246 +
1.247 + // Recompute partial derivatives and delta_p
1.248 + deriv_type deriv = compute_partial_derivatives(p);
1.249 + put(partial_derivatives, p, deriv);
1.250 +
1.251 + delta_p =
1.252 + sqrt(deriv.first*deriv.first + deriv.second*deriv.second);
1.253 + } while (!done(delta_p, p, g, false));
1.254 +
1.255 + // Select new p by updating each partial derivative and delta
1.256 + vertex_descriptor old_p = p;
1.257 + for (ui = vertices(g).first; ui != end; ++ui) {
1.258 + deriv_type old_deriv_p = p_partials[get(index, *ui)];
1.259 + deriv_type old_p_partial =
1.260 + compute_partial_derivative(*ui, old_p);
1.261 + deriv_type deriv = get(partial_derivatives, *ui);
1.262 +
1.263 + deriv.first += old_p_partial.first - old_deriv_p.first;
1.264 + deriv.second += old_p_partial.second - old_deriv_p.second;
1.265 +
1.266 + put(partial_derivatives, *ui, deriv);
1.267 + weight_type delta =
1.268 + sqrt(deriv.first*deriv.first + deriv.second*deriv.second);
1.269 +
1.270 + if (delta > delta_p) {
1.271 + p = *ui;
1.272 + delta_p = delta;
1.273 + }
1.274 + }
1.275 + }
1.276 +
1.277 + return true;
1.278 + }
1.279 +
1.280 + const Graph& g;
1.281 + PositionMap position;
1.282 + WeightMap weight;
1.283 + EdgeOrSideLength edge_or_side_length;
1.284 + Done done;
1.285 + weight_type spring_constant;
1.286 + VertexIndexMap index;
1.287 + DistanceMatrix distance;
1.288 + SpringStrengthMatrix spring_strength;
1.289 + PartialDerivativeMap partial_derivatives;
1.290 + };
1.291 + } } // end namespace detail::graph
1.292 +
1.293 + /// States that the given quantity is an edge length.
1.294 + template<typename T>
1.295 + inline detail::graph::edge_or_side<true, T>
1.296 + edge_length(T x)
1.297 + { return detail::graph::edge_or_side<true, T>(x); }
1.298 +
1.299 + /// States that the given quantity is a display area side length.
1.300 + template<typename T>
1.301 + inline detail::graph::edge_or_side<false, T>
1.302 + side_length(T x)
1.303 + { return detail::graph::edge_or_side<false, T>(x); }
1.304 +
1.305 + /**
1.306 + * \brief Determines when to terminate layout of a particular graph based
1.307 + * on a given relative tolerance.
1.308 + */
1.309 + template<typename T = double>
1.310 + struct layout_tolerance
1.311 + {
1.312 + layout_tolerance(const T& tolerance = T(0.001))
1.313 + : tolerance(tolerance), last_energy((std::numeric_limits<T>::max)()),
1.314 + last_local_energy((std::numeric_limits<T>::max)()) { }
1.315 +
1.316 + template<typename Graph>
1.317 + bool
1.318 + operator()(T delta_p,
1.319 + typename boost::graph_traits<Graph>::vertex_descriptor p,
1.320 + const Graph& g,
1.321 + bool global)
1.322 + {
1.323 + if (global) {
1.324 + if (last_energy == (std::numeric_limits<T>::max)()) {
1.325 + last_energy = delta_p;
1.326 + return false;
1.327 + }
1.328 +
1.329 + T diff = last_energy - delta_p;
1.330 + if (diff < T(0)) diff = -diff;
1.331 + bool done = (delta_p == T(0) || diff / last_energy < tolerance);
1.332 + last_energy = delta_p;
1.333 + return done;
1.334 + } else {
1.335 + if (last_local_energy == (std::numeric_limits<T>::max)()) {
1.336 + last_local_energy = delta_p;
1.337 + return delta_p == T(0);
1.338 + }
1.339 +
1.340 + T diff = last_local_energy - delta_p;
1.341 + bool done = (delta_p == T(0) || (diff / last_local_energy) < tolerance);
1.342 + last_local_energy = delta_p;
1.343 + return done;
1.344 + }
1.345 + }
1.346 +
1.347 + private:
1.348 + T tolerance;
1.349 + T last_energy;
1.350 + T last_local_energy;
1.351 + };
1.352 +
1.353 + /** \brief Kamada-Kawai spring layout for undirected graphs.
1.354 + *
1.355 + * This algorithm performs graph layout (in two dimensions) for
1.356 + * connected, undirected graphs. It operates by relating the layout
1.357 + * of graphs to a dynamic spring system and minimizing the energy
1.358 + * within that system. The strength of a spring between two vertices
1.359 + * is inversely proportional to the square of the shortest distance
1.360 + * (in graph terms) between those two vertices. Essentially,
1.361 + * vertices that are closer in the graph-theoretic sense (i.e., by
1.362 + * following edges) will have stronger springs and will therefore be
1.363 + * placed closer together.
1.364 + *
1.365 + * Prior to invoking this algorithm, it is recommended that the
1.366 + * vertices be placed along the vertices of a regular n-sided
1.367 + * polygon.
1.368 + *
1.369 + * \param g (IN) must be a model of Vertex List Graph, Edge List
1.370 + * Graph, and Incidence Graph and must be undirected.
1.371 + *
1.372 + * \param position (OUT) must be a model of Lvalue Property Map,
1.373 + * where the value type is a class containing fields @c x and @c y
1.374 + * that will be set to the @c x and @c y coordinates of each vertex.
1.375 + *
1.376 + * \param weight (IN) must be a model of Readable Property Map,
1.377 + * which provides the weight of each edge in the graph @p g.
1.378 + *
1.379 + * \param edge_or_side_length (IN) provides either the unit length
1.380 + * @c e of an edge in the layout or the length of a side @c s of the
1.381 + * display area, and must be either @c boost::edge_length(e) or @c
1.382 + * boost::side_length(s), respectively.
1.383 + *
1.384 + * \param done (IN) is a 4-argument function object that is passed
1.385 + * the current value of delta_p (i.e., the energy of vertex @p p),
1.386 + * the vertex @p p, the graph @p g, and a boolean flag indicating
1.387 + * whether @p delta_p is the maximum energy in the system (when @c
1.388 + * true) or the energy of the vertex being moved. Defaults to @c
1.389 + * layout_tolerance instantiated over the value type of the weight
1.390 + * map.
1.391 + *
1.392 + * \param spring_constant (IN) is the constant multiplied by each
1.393 + * spring's strength. Larger values create systems with more energy
1.394 + * that can take longer to stabilize; smaller values create systems
1.395 + * with less energy that stabilize quickly but do not necessarily
1.396 + * result in pleasing layouts. The default value is 1.
1.397 + *
1.398 + * \param index (IN) is a mapping from vertices to index values
1.399 + * between 0 and @c num_vertices(g). The default is @c
1.400 + * get(vertex_index,g).
1.401 + *
1.402 + * \param distance (UTIL/OUT) will be used to store the distance
1.403 + * from every vertex to every other vertex, which is computed in the
1.404 + * first stages of the algorithm. This value's type must be a model
1.405 + * of BasicMatrix with value type equal to the value type of the
1.406 + * weight map. The default is a a vector of vectors.
1.407 + *
1.408 + * \param spring_strength (UTIL/OUT) will be used to store the
1.409 + * strength of the spring between every pair of vertices. This
1.410 + * value's type must be a model of BasicMatrix with value type equal
1.411 + * to the value type of the weight map. The default is a a vector of
1.412 + * vectors.
1.413 + *
1.414 + * \param partial_derivatives (UTIL) will be used to store the
1.415 + * partial derivates of each vertex with respect to the @c x and @c
1.416 + * y coordinates. This must be a Read/Write Property Map whose value
1.417 + * type is a pair with both types equivalent to the value type of
1.418 + * the weight map. The default is an iterator property map.
1.419 + *
1.420 + * \returns @c true if layout was successful or @c false if a
1.421 + * negative weight cycle was detected.
1.422 + */
1.423 + template<typename Graph, typename PositionMap, typename WeightMap,
1.424 + typename T, bool EdgeOrSideLength, typename Done,
1.425 + typename VertexIndexMap, typename DistanceMatrix,
1.426 + typename SpringStrengthMatrix, typename PartialDerivativeMap>
1.427 + bool
1.428 + kamada_kawai_spring_layout(
1.429 + const Graph& g,
1.430 + PositionMap position,
1.431 + WeightMap weight,
1.432 + detail::graph::edge_or_side<EdgeOrSideLength, T> edge_or_side_length,
1.433 + Done done,
1.434 + typename property_traits<WeightMap>::value_type spring_constant,
1.435 + VertexIndexMap index,
1.436 + DistanceMatrix distance,
1.437 + SpringStrengthMatrix spring_strength,
1.438 + PartialDerivativeMap partial_derivatives)
1.439 + {
1.440 + BOOST_STATIC_ASSERT((is_convertible<
1.441 + typename graph_traits<Graph>::directed_category*,
1.442 + undirected_tag*
1.443 + >::value));
1.444 +
1.445 + detail::graph::kamada_kawai_spring_layout_impl<
1.446 + Graph, PositionMap, WeightMap,
1.447 + detail::graph::edge_or_side<EdgeOrSideLength, T>, Done, VertexIndexMap,
1.448 + DistanceMatrix, SpringStrengthMatrix, PartialDerivativeMap>
1.449 + alg(g, position, weight, edge_or_side_length, done, spring_constant,
1.450 + index, distance, spring_strength, partial_derivatives);
1.451 + return alg.run();
1.452 + }
1.453 +
1.454 + /**
1.455 + * \overload
1.456 + */
1.457 + template<typename Graph, typename PositionMap, typename WeightMap,
1.458 + typename T, bool EdgeOrSideLength, typename Done,
1.459 + typename VertexIndexMap>
1.460 + bool
1.461 + kamada_kawai_spring_layout(
1.462 + const Graph& g,
1.463 + PositionMap position,
1.464 + WeightMap weight,
1.465 + detail::graph::edge_or_side<EdgeOrSideLength, T> edge_or_side_length,
1.466 + Done done,
1.467 + typename property_traits<WeightMap>::value_type spring_constant,
1.468 + VertexIndexMap index)
1.469 + {
1.470 + typedef typename property_traits<WeightMap>::value_type weight_type;
1.471 +
1.472 + typename graph_traits<Graph>::vertices_size_type n = num_vertices(g);
1.473 + typedef std::vector<weight_type> weight_vec;
1.474 +
1.475 + std::vector<weight_vec> distance(n, weight_vec(n));
1.476 + std::vector<weight_vec> spring_strength(n, weight_vec(n));
1.477 + std::vector<std::pair<weight_type, weight_type> > partial_derivatives(n);
1.478 +
1.479 + return
1.480 + kamada_kawai_spring_layout(
1.481 + g, position, weight, edge_or_side_length, done, spring_constant, index,
1.482 + distance.begin(),
1.483 + spring_strength.begin(),
1.484 + make_iterator_property_map(partial_derivatives.begin(), index,
1.485 + std::pair<weight_type, weight_type>()));
1.486 + }
1.487 +
1.488 + /**
1.489 + * \overload
1.490 + */
1.491 + template<typename Graph, typename PositionMap, typename WeightMap,
1.492 + typename T, bool EdgeOrSideLength, typename Done>
1.493 + bool
1.494 + kamada_kawai_spring_layout(
1.495 + const Graph& g,
1.496 + PositionMap position,
1.497 + WeightMap weight,
1.498 + detail::graph::edge_or_side<EdgeOrSideLength, T> edge_or_side_length,
1.499 + Done done,
1.500 + typename property_traits<WeightMap>::value_type spring_constant)
1.501 + {
1.502 + return kamada_kawai_spring_layout(g, position, weight, edge_or_side_length,
1.503 + done, spring_constant,
1.504 + get(vertex_index, g));
1.505 + }
1.506 +
1.507 + /**
1.508 + * \overload
1.509 + */
1.510 + template<typename Graph, typename PositionMap, typename WeightMap,
1.511 + typename T, bool EdgeOrSideLength, typename Done>
1.512 + bool
1.513 + kamada_kawai_spring_layout(
1.514 + const Graph& g,
1.515 + PositionMap position,
1.516 + WeightMap weight,
1.517 + detail::graph::edge_or_side<EdgeOrSideLength, T> edge_or_side_length,
1.518 + Done done)
1.519 + {
1.520 + typedef typename property_traits<WeightMap>::value_type weight_type;
1.521 + return kamada_kawai_spring_layout(g, position, weight, edge_or_side_length,
1.522 + done, weight_type(1));
1.523 + }
1.524 +
1.525 + /**
1.526 + * \overload
1.527 + */
1.528 + template<typename Graph, typename PositionMap, typename WeightMap,
1.529 + typename T, bool EdgeOrSideLength>
1.530 + bool
1.531 + kamada_kawai_spring_layout(
1.532 + const Graph& g,
1.533 + PositionMap position,
1.534 + WeightMap weight,
1.535 + detail::graph::edge_or_side<EdgeOrSideLength, T> edge_or_side_length)
1.536 + {
1.537 + typedef typename property_traits<WeightMap>::value_type weight_type;
1.538 + return kamada_kawai_spring_layout(g, position, weight, edge_or_side_length,
1.539 + layout_tolerance<weight_type>(),
1.540 + weight_type(1.0),
1.541 + get(vertex_index, g));
1.542 + }
1.543 +} // end namespace boost
1.544 +
1.545 +#endif // BOOST_GRAPH_KAMADA_KAWAI_SPRING_LAYOUT_HPP