Subject: [Boost-commit] svn:boost r52137 - in trunk: boost/graph libs/graph/test
From: jewillco_at_[hidden]
Date: 2009-04-02 13:59:25
Author: jewillco
Date: 2009-04-02 13:59:22 EDT (Thu, 02 Apr 2009)
New Revision: 52137
URL: http://svn.boost.org/trac/boost/changeset/52137
Log:
Generalized layout algorithms to use extended version of topology objects from Gursoy-Atun layout; Kamada-Kawai now supports 3-D; random layout supports arbitrary topologies
Added:
trunk/boost/graph/topology.hpp (contents, props changed)
Text files modified:
trunk/boost/graph/circle_layout.hpp | 19 +-
trunk/boost/graph/fruchterman_reingold.hpp | 294 +++++++++++++++++----------------------
trunk/boost/graph/gursoy_atun_layout.hpp | 276 -------------------------------------
trunk/boost/graph/kamada_kawai_spring_layout.hpp | 188 ++++++++++++++++--------
trunk/boost/graph/random_layout.hpp | 29 ---
trunk/libs/graph/test/layout_test.cpp | 108 ++++++++-----
6 files changed, 337 insertions(+), 577 deletions(-)
Modified: trunk/boost/graph/circle_layout.hpp
==============================================================================
--- trunk/boost/graph/circle_layout.hpp (original)
+++ trunk/boost/graph/circle_layout.hpp 2009-04-02 13:59:22 EDT (Thu, 02 Apr 2009)
@@ -9,8 +9,12 @@
#ifndef BOOST_GRAPH_CIRCLE_LAYOUT_HPP
#define BOOST_GRAPH_CIRCLE_LAYOUT_HPP
#include <boost/config/no_tr1/cmath.hpp>
+#include <boost/math/constants/constants.hpp>
#include <utility>
#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/topology.hpp>
+#include <boost/static_assert.hpp>
namespace boost {
/**
@@ -28,7 +32,8 @@
circle_graph_layout(const VertexListGraph& g, PositionMap position,
Radius radius)
{
- const double pi = 3.14159;
+ BOOST_STATIC_ASSERT (property_traits<PositionMap>::value_type::dimensions >= 2);
+ const double pi = boost::math::constants::pi<double>();
#ifndef BOOST_NO_STDC_NAMESPACE
using std::sin;
@@ -40,14 +45,12 @@
vertices_size_type n = num_vertices(g);
- typedef typename graph_traits<VertexListGraph>::vertex_iterator
- vertex_iterator;
-
vertices_size_type i = 0;
- for(std::pair<vertex_iterator, vertex_iterator> v = vertices(g);
- v.first != v.second; ++v.first, ++i) {
- position[*v.first].x = radius * cos(i * 2 * pi / n);
- position[*v.first].y = radius * sin(i * 2 * pi / n);
+ double two_pi_over_n = 2. * pi / n;
+ BGL_FORALL_VERTICES_T(v, g, VertexListGraph) {
+ position[v][0] = radius * cos(i * two_pi_over_n);
+ position[v][1] = radius * sin(i * two_pi_over_n);
+ ++i;
}
}
} // end namespace boost
Modified: trunk/boost/graph/fruchterman_reingold.hpp
==============================================================================
--- trunk/boost/graph/fruchterman_reingold.hpp (original)
+++ trunk/boost/graph/fruchterman_reingold.hpp 2009-04-02 13:59:22 EDT (Thu, 02 Apr 2009)
@@ -12,12 +12,13 @@
#include <boost/config/no_tr1/cmath.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/named_function_params.hpp>
+#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/topology.hpp> // For topology concepts
#include <vector>
#include <list>
#include <algorithm> // for std::min and std::max
#include <numeric> // for std::accumulate
#include <cmath> // for std::sqrt and std::fabs
-#include <math.h> // for hypot (not in <cmath>)
#include <functional>
#include <stdlib.h> // for drand48
@@ -91,22 +92,24 @@
}
};
-template<typename PositionMap>
+template<typename Topology, typename PositionMap>
struct grid_force_pairs
{
typedef typename property_traits<PositionMap>::value_type Point;
- typedef double Dim;
+ BOOST_STATIC_ASSERT (Point::dimensions == 2);
+ typedef typename Topology::point_difference_type point_difference_type;
template<typename Graph>
explicit
- grid_force_pairs(const Point& origin, const Point& extent,
+ grid_force_pairs(const Topology& topology,
+ const Point& origin, const point_difference_type& extent,
PositionMap position, const Graph& g)
- : width(extent.x), height(extent.y), position(position)
+ : topology(topology), extent(extent), origin(origin), position(position)
{
#ifndef BOOST_NO_STDC_NAMESPACE
using std::sqrt;
#endif // BOOST_NO_STDC_NAMESPACE
- two_k = Dim(2) * sqrt(width * height / num_vertices(g));
+ two_k = 2. * topology.volume(extent) / sqrt(num_vertices(g));
}
template<typename Graph, typename ApplyForce >
@@ -121,13 +124,13 @@
using std::sqrt;
#endif // BOOST_NO_STDC_NAMESPACE
- std::size_t columns = std::size_t(width / two_k + Dim(1));
- std::size_t rows = std::size_t(height / two_k + Dim(1));
+ std::size_t columns = std::size_t(extent[0] / two_k + 1.);
+ std::size_t rows = std::size_t(extent[1] / two_k + 1.);
buckets_t buckets(rows * columns);
vertex_iterator v, v_end;
for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
- std::size_t column = std::size_t((position[*v].x + width / 2) / two_k);
- std::size_t row = std::size_t((position[*v].y + height / 2) / two_k);
+ std::size_t column = std::size_t((position[*v][0] + extent[0] / 2) / two_k);
+ std::size_t row = std::size_t((position[*v][1] + extent[1] / 2) / two_k);
if (column >= columns) column = columns - 1;
if (row >= rows) row = rows - 1;
@@ -159,9 +162,7 @@
bucket_t& other_bucket
= buckets[other_row * columns + other_column];
for (v = other_bucket.begin(); v != other_bucket.end(); ++v) {
- Dim delta_x = position[*u].x - position[*v].x;
- Dim delta_y = position[*u].y - position[*v].y;
- Dim dist = hypot(delta_x, delta_y);
+ double dist = topology.distance(position[*u], position[*v]);
if (dist < two_k) apply_force(*u, *v);
}
}
@@ -170,97 +171,89 @@
}
private:
- Dim width;
- Dim height;
+ const Topology& topology;
+ point_difference_type extent;
+ Point origin;
PositionMap position;
- Dim two_k;
+ double two_k;
};
-template<typename PositionMap, typename Graph>
-inline grid_force_pairs<PositionMap>
+template<typename PositionMap, typename Topology, typename Graph>
+inline grid_force_pairs<Topology, PositionMap>
make_grid_force_pairs
- (typename property_traits<PositionMap>::value_type const& origin,
- typename property_traits<PositionMap>::value_type const& extent,
+ (const Topology& topology,
+ typename Topology::point_type const& origin,
+ typename Topology::point_difference_type const& extent,
const PositionMap& position, const Graph& g)
-{ return grid_force_pairs<PositionMap>(origin, extent, position, g); }
+{ return grid_force_pairs<Topology, PositionMap>(topology, origin, extent, position, g); }
-template<typename Graph, typename PositionMap, typename Dim>
+template<typename Graph, typename PositionMap, typename Topology>
void
-scale_graph(const Graph& g, PositionMap position,
- Dim left, Dim top, Dim right, Dim bottom)
+scale_graph(const Graph& g, PositionMap position, const Topology& topology,
+ typename Topology::point_type upper_left, typename Topology::point_type lower_right)
{
if (num_vertices(g) == 0) return;
- if (bottom > top) {
- using std::swap;
- swap(bottom, top);
- }
-
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
+ typedef typename Topology::point_type Point;
+ typedef typename Topology::point_difference_type point_difference_type;
// Find min/max ranges
- Dim minX = position[*vertices(g).first].x, maxX = minX;
- Dim minY = position[*vertices(g).first].y, maxY = minY;
- vertex_iterator vi, vi_end;
- for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
- BOOST_USING_STD_MIN();
- BOOST_USING_STD_MAX();
- minX = min BOOST_PREVENT_MACRO_SUBSTITUTION (minX, position[*vi].x);
- maxX = max BOOST_PREVENT_MACRO_SUBSTITUTION (maxX, position[*vi].x);
- minY = min BOOST_PREVENT_MACRO_SUBSTITUTION (minY, position[*vi].y);
- maxY = max BOOST_PREVENT_MACRO_SUBSTITUTION (maxY, position[*vi].y);
+ Point min_point = position[*vertices(g).first], max_point = min_point;
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ min_point = topology.pointwise_min(min_point, position[v]);
+ max_point = topology.pointwise_max(max_point, position[v]);
}
+ Point old_origin = topology.move_position_toward(min_point, 0.5, max_point);
+ Point new_origin = topology.move_position_toward(upper_left, 0.5, lower_right);
+ point_difference_type old_size = topology.difference(max_point, min_point);
+ point_difference_type new_size = topology.difference(lower_right, upper_left);
+
// Scale to bounding box provided
- for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
- position[*vi].x = ((position[*vi].x - minX) / (maxX - minX))
- * (right - left) + left;
- position[*vi].y = ((position[*vi].y - minY) / (maxY - minY))
- * (top - bottom) + bottom;
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ point_difference_type relative_loc = topology.difference(position[v], old_origin);
+ relative_loc = (relative_loc / old_size) * new_size;
+ position[v] = topology.adjust(new_origin, relative_loc);
}
}
namespace detail {
- template<typename Point>
+ template<typename Topology>
void
- maybe_jitter_point(Point& p1, const Point& p2, Point origin, Point extent)
+ maybe_jitter_point(const Topology& topology,
+ typename Topology::point_type& p1, const typename Topology::point_type& p2,
+ typename Topology::point_type origin, typename Topology::point_difference_type extent)
{
#ifndef BOOST_NO_STDC_NAMESPACE
using std::sqrt;
using std::fabs;
#endif // BOOST_NO_STDC_NAMESPACE
- typedef double Dim;
- Dim too_close_x = extent.x / Dim(10000);
- if (fabs(p1.x - p2.x) < too_close_x) {
- Dim dist_to_move = sqrt(extent.x) / Dim(200);
- if (p1.x - origin.x < origin.x + extent.x - p1.x)
- p1.x += dist_to_move * drand48();
- else
- p1.x -= dist_to_move * drand48();
- }
- Dim too_close_y = extent.y / Dim(10000);
- if (fabs(p1.y - p2.y) < too_close_y) {
- Dim dist_to_move = sqrt(extent.y) / Dim(200);
- if (p1.y - origin.y < origin.y + extent.y - p1.y)
- p1.y += dist_to_move * drand48();
- else
- p1.y -= dist_to_move * drand48();
+ double too_close = topology.norm(extent) / 10000.;
+ if (topology.distance(p1, p2) < too_close) {
+ double dist_to_move = sqrt(topology.norm(extent)) / 200.;
+ for (std::size_t i = 0; i < Topology::point_type::dimensions; ++i) {
+ if (p1[i] - origin[i] < origin[i] + extent[i] - p1[i])
+ p1[i] += dist_to_move * drand48();
+ else
+ p1[i] -= dist_to_move * drand48();
+ }
}
}
- template<typename PositionMap, typename DisplacementMap,
+ template<typename Topology, typename PositionMap, typename DisplacementMap,
typename RepulsiveForce, typename Graph>
struct fr_apply_force
{
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef typename property_traits<PositionMap>::value_type Point;
- typedef double Dim;
+ typedef typename Topology::point_type Point;
+ typedef typename Topology::point_difference_type PointDiff;
- fr_apply_force(const PositionMap& position,
+ fr_apply_force(const Topology& topology,
+ const PositionMap& position,
const DisplacementMap& displacement,
- Point origin, Point extent,
- RepulsiveForce repulsive_force, Dim k, const Graph& g)
- : position(position), displacement(displacement), origin(origin),
+ Point origin, PointDiff extent,
+ RepulsiveForce repulsive_force, double k, const Graph& g)
+ : topology(topology), position(position), displacement(displacement), origin(origin),
extent(extent), repulsive_force(repulsive_force), k(k), g(g)
{ }
@@ -272,75 +265,76 @@
if (u != v) {
// When the vertices land on top of each other, move the
// first vertex away from the boundaries.
- maybe_jitter_point(position[u], position[v], origin, extent);
+ maybe_jitter_point(topology, position[u], position[v], origin, extent);
- // DPG TBD: Can we use the Topology concept's
- // distance/move_position_toward to handle this?
- Dim delta_x = position[v].x - position[u].x;
- Dim delta_y = position[v].y - position[u].y;
- Dim dist = hypot(delta_x, delta_y);
- if (dist == Dim(0)) {
- displacement[v].x += 0.01;
- displacement[v].y += 0.01;
+ double dist = topology.distance(position[u], position[v]);
+ if (dist == 0.) {
+ for (std::size_t i = 0; i < Point::dimensions; ++i) {
+ displacement[v][i] += 0.01;
+ }
} else {
- Dim fr = repulsive_force(u, v, k, dist, g);
- displacement[v].x += delta_x / dist * fr;
- displacement[v].y += delta_y / dist * fr;
+ double fr = repulsive_force(u, v, k, dist, g);
+ typename Topology::point_difference_type dispv = displacement[v];
+ dispv += (fr / dist) * topology.difference(position[v], position[u]);
}
}
}
private:
+ const Topology& topology;
PositionMap position;
DisplacementMap displacement;
Point origin;
- Point extent;
+ PointDiff extent;
RepulsiveForce repulsive_force;
- Dim k;
+ double k;
const Graph& g;
};
} // end namespace detail
-template<typename Graph, typename PositionMap,
+template<typename Topology, typename Graph, typename PositionMap,
typename AttractiveForce, typename RepulsiveForce,
typename ForcePairs, typename Cooling, typename DisplacementMap>
void
fruchterman_reingold_force_directed_layout
(const Graph& g,
PositionMap position,
- typename property_traits<PositionMap>::value_type const& origin,
- typename property_traits<PositionMap>::value_type const& extent,
+ const Topology& topology,
+ typename Topology::point_type const& origin,
+ typename Topology::point_difference_type const& extent,
AttractiveForce attractive_force,
RepulsiveForce repulsive_force,
ForcePairs force_pairs,
Cooling cool,
DisplacementMap displacement)
{
- typedef typename property_traits<PositionMap>::value_type Point;
- typedef double Dim;
+ typedef typename Topology::point_type Point;
typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef typename graph_traits<Graph>::edge_iterator edge_iterator;
#ifndef BOOST_NO_STDC_NAMESPACE
using std::sqrt;
+ using std::pow;
#endif // BOOST_NO_STDC_NAMESPACE
- Dim volume = extent.x * extent.y;
+ double volume = 1.;
+ for (std::size_t i = 0; i < Topology::point_difference_type::dimensions; ++i)
+ volume *= extent[i];
// assume positions are initialized randomly
- Dim k = sqrt(volume / num_vertices(g));
+ double k = pow(volume / num_vertices(g), 1. / (double)(Topology::point_difference_type::dimensions));
- detail::fr_apply_force<PositionMap, DisplacementMap,
+ detail::fr_apply_force<Topology, PositionMap, DisplacementMap,
RepulsiveForce, Graph>
- apply_force(position, displacement, origin, extent, repulsive_force, k, g);
+ apply_force(topology, position, displacement, origin, extent, repulsive_force, k, g);
do {
// Calculate repulsive forces
vertex_iterator v, v_end;
for (tie(v, v_end) = vertices(g); v != v_end; ++v)
- displacement[*v] = Point();
+ displacement[*v] = typename Topology::point_difference_type();
force_pairs(g, apply_force);
// Calculate attractive forces
@@ -351,62 +345,32 @@
// When the vertices land on top of each other, move the
// first vertex away from the boundaries.
- ::boost::detail::maybe_jitter_point(position[u], position[v],
+ ::boost::detail::maybe_jitter_point(topology, position[u], position[v],
origin, extent);
- // DPG TBD: Can we use the Topology concept's
- // distance/move_position_toward to handle this?
- Dim delta_x = position[v].x - position[u].x;
- Dim delta_y = position[v].y - position[u].y;
- Dim dist = hypot(delta_x, delta_y);
- Dim fa = attractive_force(*e, k, dist, g);
-
- displacement[v].x -= delta_x / dist * fa;
- displacement[v].y -= delta_y / dist * fa;
- displacement[u].x += delta_x / dist * fa;
- displacement[u].y += delta_y / dist * fa;
+ typename Topology::point_difference_type delta = topology.difference(position[v], position[u]);
+ double dist = topology.distance(position[u], position[v]);
+ double fa = attractive_force(*e, k, dist, g);
+
+ displacement[v] -= (fa / dist) * delta;
+ displacement[u] += (fa / dist) * delta;
}
- if (Dim temp = cool()) {
+ if (double temp = cool()) {
// Update positions
- for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
+ BGL_FORALL_VERTICES_T (v, g, Graph) {
BOOST_USING_STD_MIN();
BOOST_USING_STD_MAX();
- Dim disp_size = hypot(displacement[*v].x, displacement[*v].y);
- {
- position[*v].x += displacement[*v].x / disp_size
- * (min)(disp_size, temp);
- if (vertex_migration) {
- position[*v].x = (min)(Dim(1.0),
- (max)(Dim(-1.0), position[*v].x));
- } else {
- position[*v].x = (min)(origin.x + extent.x,
- (max)(origin.x, position[*v].x));
- }
-
- // CEM HACK: Jitter if we're on the edges
- if(position[*v].x == 1.0f) // origin.x + extent.x)
- position[*v].x -= drand48() * .1 * extent.x;
- else if(position[*v].x == -1.0f) // origin.x)
- position[*v].x += drand48() * .1 * extent.x;
- }
- {
- position[*v].y += displacement[*v].y / disp_size
- * (min)(disp_size, temp);
- if (vertex_migration) {
- position[*v].y = (min)(Dim(1.0),
- (max)(Dim(-1.0), position[*v].y));
- } else {
- position[*v].y = (min)(origin.y + extent.y,
- (max)(origin.y, position[*v].y));
- }
-
- // CEM HACK: Jitter if we're on the edges
- if(position[*v].y == 1.0f) // origin.y + extent.y)
- position[*v].y -= drand48() * .1 * extent.y;
- else if(position[*v].y == -1.0f) // origin.y)
- position[*v].y += drand48() * .1 * extent.y;
- }
+ double disp_size = topology.norm(displacement[v]);
+ position[v] = topology.adjust(position[v], displacement[v] * (min BOOST_PREVENT_MACRO_SUBSTITUTION (disp_size, temp) / disp_size));
+ position[v] = topology.bound(position[v]);
+#if 0
+ // CEM HACK: Jitter if we're on the edges
+ if(position[v].x == 1.0f) // origin.x + extent.x)
+ position[v].x -= drand48() * .1 * extent.x;
+ else if(position[v].x == -1.0f) // origin.x)
+ position[v].x += drand48() * .1 * extent.x;
+#endif
}
} else {
break;
@@ -418,15 +382,16 @@
template<typename DisplacementMap>
struct fr_force_directed_layout
{
- template<typename Graph, typename PositionMap,
+ template<typename Topology, typename Graph, typename PositionMap,
typename AttractiveForce, typename RepulsiveForce,
typename ForcePairs, typename Cooling,
typename Param, typename Tag, typename Rest>
static void
run(const Graph& g,
PositionMap position,
- typename property_traits<PositionMap>::value_type const& origin,
- typename property_traits<PositionMap>::value_type const& extent,
+ const Topology& topology,
+ typename Topology::point_type const& origin,
+ typename Topology::point_difference_type const& extent,
AttractiveForce attractive_force,
RepulsiveForce repulsive_force,
ForcePairs force_pairs,
@@ -435,7 +400,7 @@
const bgl_named_params<Param, Tag, Rest>&)
{
fruchterman_reingold_force_directed_layout
- (g, position, origin, extent, attractive_force, repulsive_force,
+ (g, position, topology, origin, extent, attractive_force, repulsive_force,
force_pairs, cool, displacement);
}
};
@@ -443,15 +408,16 @@
template<>
struct fr_force_directed_layout<error_property_not_found>
{
- template<typename Graph, typename PositionMap,
+ template<typename Topology, typename Graph, typename PositionMap,
typename AttractiveForce, typename RepulsiveForce,
typename ForcePairs, typename Cooling,
typename Param, typename Tag, typename Rest>
static void
run(const Graph& g,
PositionMap position,
- typename property_traits<PositionMap>::value_type const& origin,
- typename property_traits<PositionMap>::value_type const& extent,
+ const Topology& topology,
+ typename Topology::point_type const& origin,
+ typename Topology::point_difference_type const& extent,
AttractiveForce attractive_force,
RepulsiveForce repulsive_force,
ForcePairs force_pairs,
@@ -459,58 +425,60 @@
error_property_not_found,
const bgl_named_params<Param, Tag, Rest>& params)
{
- typedef typename property_traits<PositionMap>::value_type Point;
- std::vector<Point> displacements(num_vertices(g));
+ typedef typename Topology::point_difference_type PointDiff;
+ std::vector<PointDiff> displacements(num_vertices(g));
fruchterman_reingold_force_directed_layout
- (g, position, origin, extent, attractive_force, repulsive_force,
+ (g, position, topology, origin, extent, attractive_force, repulsive_force,
force_pairs, cool,
make_iterator_property_map
(displacements.begin(),
choose_const_pmap(get_param(params, vertex_index), g,
vertex_index),
- Point()));
+ PointDiff()));
}
};
} // end namespace detail
-template<typename Graph, typename PositionMap, typename Param,
+template<typename Topology, typename Graph, typename PositionMap, typename Param,
typename Tag, typename Rest>
void
fruchterman_reingold_force_directed_layout
(const Graph& g,
PositionMap position,
- typename property_traits<PositionMap>::value_type const& origin,
- typename property_traits<PositionMap>::value_type const& extent,
+ const Topology& topology,
+ typename Topology::point_type const& origin,
+ typename Topology::point_difference_type const& extent,
const bgl_named_params<Param, Tag, Rest>& params)
{
typedef typename property_value<bgl_named_params<Param,Tag,Rest>,
vertex_displacement_t>::type D;
detail::fr_force_directed_layout<D>::run
- (g, position, origin, extent,
+ (g, position, topology, origin, extent,
choose_param(get_param(params, attractive_force_t()),
square_distance_attractive_force()),
choose_param(get_param(params, repulsive_force_t()),
square_distance_repulsive_force()),
choose_param(get_param(params, force_pairs_t()),
- make_grid_force_pairs(origin, extent, position, g)),
+ make_grid_force_pairs(topology, origin, extent, position, g)),
choose_param(get_param(params, cooling_t()),
linear_cooling<double>(100)),
get_param(params, vertex_displacement_t()),
params);
}
-template<typename Graph, typename PositionMap>
+template<typename Topology, typename Graph, typename PositionMap>
void
fruchterman_reingold_force_directed_layout
(const Graph& g,
PositionMap position,
- typename property_traits<PositionMap>::value_type const& origin,
- typename property_traits<PositionMap>::value_type const& extent)
+ const Topology& topology,
+ typename Topology::point_type const& origin,
+ typename Topology::point_difference_type const& extent)
{
fruchterman_reingold_force_directed_layout
- (g, position, origin, extent,
+ (g, position, topology, origin, extent,
attractive_force(square_distance_attractive_force()));
}
Modified: trunk/boost/graph/gursoy_atun_layout.hpp
==============================================================================
--- trunk/boost/graph/gursoy_atun_layout.hpp (original)
+++ trunk/boost/graph/gursoy_atun_layout.hpp 2009-04-02 13:59:22 EDT (Thu, 02 Apr 2009)
@@ -28,6 +28,7 @@
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/named_function_params.hpp>
+#include <boost/graph/topology.hpp>
namespace boost {
@@ -351,281 +352,6 @@
dummy_property_map()));
}
-/***********************************************************
- * Topologies *
- ***********************************************************/
-template<std::size_t Dims>
-class convex_topology
-{
- struct point
- {
- point() { }
- double& operator[](std::size_t i) {return values[i];}
- const double& operator[](std::size_t i) const {return values[i];}
-
- private:
- double values[Dims];
- };
-
- public:
- typedef point point_type;
-
- double distance(point a, point b) const
- {
- double dist = 0;
- for (std::size_t i = 0; i < Dims; ++i) {
- double diff = b[i] - a[i];
- dist += diff * diff;
- }
- // Exact properties of the distance are not important, as long as
- // < on what this returns matches real distances
- return dist;
- }
-
- point move_position_toward(point a, double fraction, point b) const
- {
- point result;
- for (std::size_t i = 0; i < Dims; ++i)
- result[i] = a[i] + (b[i] - a[i]) * fraction;
- return result;
- }
-};
-
-template<std::size_t Dims,
- typename RandomNumberGenerator = minstd_rand>
-class hypercube_topology : public convex_topology<Dims>
-{
- typedef uniform_01<RandomNumberGenerator, double> rand_t;
-
- public:
- typedef typename convex_topology<Dims>::point_type point_type;
-
- explicit hypercube_topology(double scaling = 1.0)
- : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)),
- scaling(scaling)
- { }
-
- hypercube_topology(RandomNumberGenerator& gen, double scaling = 1.0)
- : gen_ptr(), rand(new rand_t(gen)), scaling(scaling) { }
-
- point_type random_point() const
- {
- point_type p;
- for (std::size_t i = 0; i < Dims; ++i)
- p[i] = (*rand)() * scaling;
- return p;
- }
-
- private:
- shared_ptr<RandomNumberGenerator> gen_ptr;
- shared_ptr<rand_t> rand;
- double scaling;
-};
-
-template<typename RandomNumberGenerator = minstd_rand>
-class square_topology : public hypercube_topology<2, RandomNumberGenerator>
-{
- typedef hypercube_topology<2, RandomNumberGenerator> inherited;
-
- public:
- explicit square_topology(double scaling = 1.0) : inherited(scaling) { }
-
- square_topology(RandomNumberGenerator& gen, double scaling = 1.0)
- : inherited(gen, scaling) { }
-};
-
-template<typename RandomNumberGenerator = minstd_rand>
-class cube_topology : public hypercube_topology<3, RandomNumberGenerator>
-{
- typedef hypercube_topology<3, RandomNumberGenerator> inherited;
-
- public:
- explicit cube_topology(double scaling = 1.0) : inherited(scaling) { }
-
- cube_topology(RandomNumberGenerator& gen, double scaling = 1.0)
- : inherited(gen, scaling) { }
-};
-
-template<std::size_t Dims,
- typename RandomNumberGenerator = minstd_rand>
-class ball_topology : public convex_topology<Dims>
-{
- typedef uniform_01<RandomNumberGenerator, double> rand_t;
-
- public:
- typedef typename convex_topology<Dims>::point_type point_type;
-
- explicit ball_topology(double radius = 1.0)
- : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)),
- radius(radius)
- { }
-
- ball_topology(RandomNumberGenerator& gen, double radius = 1.0)
- : gen_ptr(), rand(new rand_t(gen)), radius(radius) { }
-
- point_type random_point() const
- {
- point_type p;
- double dist_sum;
- do {
- dist_sum = 0.0;
- for (std::size_t i = 0; i < Dims; ++i) {
- double x = (*rand)() * 2*radius - radius;
- p[i] = x;
- dist_sum += x * x;
- }
- } while (dist_sum > radius*radius);
- return p;
- }
-
- private:
- shared_ptr<RandomNumberGenerator> gen_ptr;
- shared_ptr<rand_t> rand;
- double radius;
-};
-
-template<typename RandomNumberGenerator = minstd_rand>
-class circle_topology : public ball_topology<2, RandomNumberGenerator>
-{
- typedef ball_topology<2, RandomNumberGenerator> inherited;
-
- public:
- explicit circle_topology(double radius = 1.0) : inherited(radius) { }
-
- circle_topology(RandomNumberGenerator& gen, double radius = 1.0)
- : inherited(gen, radius) { }
-};
-
-template<typename RandomNumberGenerator = minstd_rand>
-class sphere_topology : public ball_topology<3, RandomNumberGenerator>
-{
- typedef ball_topology<3, RandomNumberGenerator> inherited;
-
- public:
- explicit sphere_topology(double radius = 1.0) : inherited(radius) { }
-
- sphere_topology(RandomNumberGenerator& gen, double radius = 1.0)
- : inherited(gen, radius) { }
-};
-
-template<typename RandomNumberGenerator = minstd_rand>
-class heart_topology
-{
- // Heart is defined as the union of three shapes:
- // Square w/ corners (+-1000, -1000), (0, 0), (0, -2000)
- // Circle centered at (-500, -500) radius 500*sqrt(2)
- // Circle centered at (500, -500) radius 500*sqrt(2)
- // Bounding box (-1000, -2000) - (1000, 500*(sqrt(2) - 1))
-
- struct point
- {
- point() { values[0] = 0.0; values[1] = 0.0; }
- point(double x, double y) { values[0] = x; values[1] = y; }
-
- double& operator[](std::size_t i) { return values[i]; }
- double operator[](std::size_t i) const { return values[i]; }
-
- private:
- double values[2];
- };
-
- bool in_heart(point p) const
- {
-#ifndef BOOST_NO_STDC_NAMESPACE
- using std::abs;
- using std::pow;
-#endif
-
- if (p[1] < abs(p[0]) - 2000) return false; // Bottom
- if (p[1] <= -1000) return true; // Diagonal of square
- if (pow(p[0] - -500, 2) + pow(p[1] - -500, 2) <= 500000)
- return true; // Left circle
- if (pow(p[0] - 500, 2) + pow(p[1] - -500, 2) <= 500000)
- return true; // Right circle
- return false;
- }
-
- bool segment_within_heart(point p1, point p2) const
- {
- // Assumes that p1 and p2 are within the heart
- if ((p1[0] < 0) == (p2[0] < 0)) return true; // Same side of symmetry line
- if (p1[0] == p2[0]) return true; // Vertical
- double slope = (p2[1] - p1[1]) / (p2[0] - p1[0]);
- double intercept = p1[1] - p1[0] * slope;
- if (intercept > 0) return false; // Crosses between circles
- return true;
- }
-
- typedef uniform_01<RandomNumberGenerator, double> rand_t;
-
- public:
- typedef point point_type;
-
- heart_topology()
- : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)) { }
-
- heart_topology(RandomNumberGenerator& gen)
- : gen_ptr(), rand(new rand_t(gen)) { }
-
- point random_point() const
- {
-#ifndef BOOST_NO_STDC_NAMESPACE
- using std::sqrt;
-#endif
-
- point result;
- double sqrt2 = sqrt(2.);
- do {
- result[0] = (*rand)() * (1000 + 1000 * sqrt2) - (500 + 500 * sqrt2);
- result[1] = (*rand)() * (2000 + 500 * (sqrt2 - 1)) - 2000;
- } while (!in_heart(result));
- return result;
- }
-
- double distance(point a, point b) const
- {
-#ifndef BOOST_NO_STDC_NAMESPACE
- using std::sqrt;
-#endif
- if (segment_within_heart(a, b)) {
- // Straight line
- return sqrt((b[0] - a[0]) * (b[0] - a[0]) + (b[1] - a[1]) * (b[1] - a[1]));
- } else {
- // Straight line bending around (0, 0)
- return sqrt(a[0] * a[0] + a[1] * a[1]) + sqrt(b[0] * b[0] + b[1] * b[1]);
- }
- }
-
- point move_position_toward(point a, double fraction, point b) const
- {
-#ifndef BOOST_NO_STDC_NAMESPACE
- using std::sqrt;
-#endif
-
- if (segment_within_heart(a, b)) {
- // Straight line
- return point(a[0] + (b[0] - a[0]) * fraction,
- a[1] + (b[1] - a[1]) * fraction);
- } else {
- double distance_to_point_a = sqrt(a[0] * a[0] + a[1] * a[1]);
- double distance_to_point_b = sqrt(b[0] * b[0] + b[1] * b[1]);
- double location_of_point = distance_to_point_a /
- (distance_to_point_a + distance_to_point_b);
- if (fraction < location_of_point)
- return point(a[0] * (1 - fraction / location_of_point),
- a[1] * (1 - fraction / location_of_point));
- else
- return point(
- b[0] * ((fraction - location_of_point) / (1 - location_of_point)),
- b[1] * ((fraction - location_of_point) / (1 - location_of_point)));
- }
- }
-
- private:
- shared_ptr<RandomNumberGenerator> gen_ptr;
- shared_ptr<rand_t> rand;
-};
-
} // namespace boost
#endif // BOOST_GRAPH_GURSOY_ATUN_LAYOUT_HPP
Modified: trunk/boost/graph/kamada_kawai_spring_layout.hpp
==============================================================================
--- trunk/boost/graph/kamada_kawai_spring_layout.hpp (original)
+++ trunk/boost/graph/kamada_kawai_spring_layout.hpp 2009-04-02 13:59:22 EDT (Thu, 02 Apr 2009)
@@ -10,6 +10,8 @@
#define BOOST_GRAPH_KAMADA_KAWAI_SPRING_LAYOUT_HPP
#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/topology.hpp>
+#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/johnson_all_pairs_shortest.hpp>
#include <boost/type_traits/is_convertible.hpp>
#include <utility>
@@ -68,21 +70,81 @@
}
/**
+ * Dense linear solver for fixed-size matrices.
+ */
+ template <std::size_t Size>
+ struct linear_solver {
+ // Indices in mat are (row, column)
+ // template <typename Vec>
+ // static Vec solve(double mat[Size][Size], Vec rhs);
+ };
+
+ template <>
+ struct linear_solver<1> {
+ template <typename Vec>
+ static Vec solve(double mat[1][1], Vec rhs) {
+ return rhs / mat[0][0];
+ }
+ };
+
+ // These are from http://en.wikipedia.org/wiki/Cramer%27s_rule
+ template <>
+ struct linear_solver<2> {
+ template <typename Vec>
+ static Vec solve(double mat[2][2], Vec rhs) {
+ double denom = mat[0][0] * mat[1][1] - mat[1][0] * mat[0][1];
+ double x_num = rhs[0] * mat[1][1] - rhs[1] * mat[0][1];
+ double y_num = mat[0][0] * rhs[1] - mat[1][0] * rhs[0] ;
+ Vec result;
+ result[0] = x_num / denom;
+ result[1] = y_num / denom;
+ return result;
+ }
+ };
+
+ template <>
+ struct linear_solver<3> {
+ template <typename Vec>
+ static Vec solve(double mat[2][2], Vec rhs) {
+ double denom = mat[0][0] * (mat[1][1] * mat[2][2] - mat[2][1] * mat[1][2])
+ - mat[1][0] * (mat[0][1] * mat[2][2] - mat[2][1] * mat[0][2])
+ + mat[2][0] * (mat[0][1] * mat[1][2] - mat[1][1] * mat[0][2]);
+ double x_num = rhs[0] * (mat[1][1] * mat[2][2] - mat[2][1] * mat[1][2])
+ - rhs[1] * (mat[0][1] * mat[2][2] - mat[2][1] * mat[0][2])
+ + rhs[2] * (mat[0][1] * mat[1][2] - mat[1][1] * mat[0][2]);
+ double y_num = mat[0][0] * (rhs[1] * mat[2][2] - rhs[2] * mat[1][2])
+ - mat[1][0] * (rhs[0] * mat[2][2] - rhs[2] * mat[0][2])
+ + mat[2][0] * (rhs[0] * mat[1][2] - rhs[1] * mat[0][2]);
+ double z_num = mat[0][0] * (mat[1][1] * rhs[2] - mat[2][1] * rhs[1] )
+ - mat[1][0] * (mat[0][1] * rhs[2] - mat[2][1] * rhs[0] )
+ + mat[2][0] * (mat[0][1] * rhs[1] - mat[1][1] * rhs[0] );
+ Vec result;
+ result[0] = x_num / denom;
+ result[1] = y_num / denom;
+ result[2] = z_num / denom;
+ return result;
+ }
+ };
+
+ /**
* Implementation of the Kamada-Kawai spring layout algorithm.
*/
- template<typename Graph, typename PositionMap, typename WeightMap,
+ template<typename Topology, typename Graph, typename PositionMap, typename WeightMap,
typename EdgeOrSideLength, typename Done,
typename VertexIndexMap, typename DistanceMatrix,
typename SpringStrengthMatrix, typename PartialDerivativeMap>
struct kamada_kawai_spring_layout_impl
{
typedef typename property_traits<WeightMap>::value_type weight_type;
- typedef std::pair<weight_type, weight_type> deriv_type;
+ typedef typename Topology::point_type Point;
+ typedef typename Topology::point_difference_type point_difference_type;
+ typedef point_difference_type deriv_type;
typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
typedef typename graph_traits<Graph>::vertex_descriptor
vertex_descriptor;
kamada_kawai_spring_layout_impl(
+ const Topology& topology,
const Graph& g,
PositionMap position,
WeightMap weight,
@@ -93,7 +155,7 @@
DistanceMatrix distance,
SpringStrengthMatrix spring_strength,
PartialDerivativeMap partial_derivatives)
- : g(g), position(position), weight(weight),
+ : topology(topology), g(g), position(position), weight(weight),
edge_or_side_length(edge_or_side_length), done(done),
spring_constant(spring_constant), index(index), distance(distance),
spring_strength(spring_strength),
@@ -108,15 +170,12 @@
using std::sqrt;
#endif // BOOST_NO_STDC_NAMESPACE
- deriv_type result(0, 0);
+ deriv_type result;
if (i != m) {
- weight_type x_diff = position[m].x - position[i].x;
- weight_type y_diff = position[m].y - position[i].y;
- weight_type dist = sqrt(x_diff * x_diff + y_diff * y_diff);
- result.first = spring_strength[get(index, m)][get(index, i)]
- * (x_diff - distance[get(index, m)][get(index, i)]*x_diff/dist);
- result.second = spring_strength[get(index, m)][get(index, i)]
- * (y_diff - distance[get(index, m)][get(index, i)]*y_diff/dist);
+ point_difference_type diff = topology.difference(position[m], position[i]);
+ weight_type dist = topology.norm(diff);
+ result = spring_strength[get(index, m)][get(index, i)]
+ * (diff - distance[get(index, m)][get(index, i)]/dist*diff);
}
return result;
@@ -130,15 +189,12 @@
using std::sqrt;
#endif // BOOST_NO_STDC_NAMESPACE
- deriv_type result(0, 0);
+ deriv_type result;
// TBD: looks like an accumulate to me
- std::pair<vertex_iterator, vertex_iterator> verts = vertices(g);
- for (/* no init */; verts.first != verts.second; ++verts.first) {
- vertex_descriptor i = *verts.first;
+ BGL_FORALL_VERTICES_T(i, g, Graph) {
deriv_type deriv = compute_partial_derivative(m, i);
- result.first += deriv.first;
- result.second += deriv.second;
+ result += deriv;
}
return result;
@@ -185,8 +241,7 @@
deriv_type deriv = compute_partial_derivatives(*ui);
put(partial_derivatives, *ui, deriv);
- weight_type delta =
- sqrt(deriv.first*deriv.first + deriv.second*deriv.second);
+ weight_type delta = topology.norm(deriv);
if (delta > delta_p) {
p = *ui;
@@ -206,47 +261,48 @@
}
do {
- // Compute the 4 elements of the Jacobian
- weight_type dE_dx_dx = 0, dE_dx_dy = 0, dE_dy_dx = 0, dE_dy_dy = 0;
+ // Compute the elements of the Jacobian
+ // From
+ // http://www.cs.panam.edu/~rfowler/papers/1994_kumar_fowler_A_Spring_UTPACSTR.pdf
+ // with the bugs fixed in the off-diagonal case
+ weight_type dE_d_d[Point::dimensions][Point::dimensions];
+ for (std::size_t i = 0; i < Point::dimensions; ++i)
+ for (std::size_t j = 0; j < Point::dimensions; ++j)
+ dE_d_d[i][j] = 0.;
for (ui = vertices(g).first; ui != end; ++ui) {
vertex_descriptor i = *ui;
if (i != p) {
- weight_type x_diff = position[p].x - position[i].x;
- weight_type y_diff = position[p].y - position[i].y;
- weight_type dist = sqrt(x_diff * x_diff + y_diff * y_diff);
- weight_type dist_cubed = dist * dist * dist;
+ point_difference_type diff = topology.difference(position[p], position[i]);
+ weight_type dist = topology.norm(diff);
+ weight_type dist_squared = dist * dist;
+ weight_type inv_dist_cubed = 1. / (dist_squared * dist);
weight_type k_mi = spring_strength[get(index,p)][get(index,i)];
weight_type l_mi = distance[get(index, p)][get(index, i)];
- dE_dx_dx += k_mi * (1 - (l_mi * y_diff * y_diff)/dist_cubed);
- dE_dx_dy += k_mi * l_mi * x_diff * y_diff / dist_cubed;
- dE_dy_dx += k_mi * l_mi * x_diff * y_diff / dist_cubed;
- dE_dy_dy += k_mi * (1 - (l_mi * x_diff * x_diff)/dist_cubed);
+ for (std::size_t i = 0; i < Point::dimensions; ++i) {
+ for (std::size_t j = 0; j < Point::dimensions; ++j) {
+ if (i == j) {
+ dE_d_d[i][i] += k_mi * (1 + (l_mi * (diff[i] * diff[i] - dist_squared) * inv_dist_cubed));
+ } else {
+ dE_d_d[i][j] += k_mi * l_mi * diff[i] * diff[j] * inv_dist_cubed;
+ }
+ }
+ }
}
}
- // Solve for delta_x and delta_y
- weight_type dE_dx = get(partial_derivatives, p).first;
- weight_type dE_dy = get(partial_derivatives, p).second;
-
- weight_type delta_x =
- (dE_dx_dy * dE_dy - dE_dy_dy * dE_dx)
- / (dE_dx_dx * dE_dy_dy - dE_dx_dy * dE_dy_dx);
-
- weight_type delta_y =
- (dE_dx_dx * dE_dy - dE_dy_dx * dE_dx)
- / (dE_dy_dx * dE_dx_dy - dE_dx_dx * dE_dy_dy);
-
-
- // Move p by (delta_x, delta_y)
- position[p].x += delta_x;
- position[p].y += delta_y;
+ deriv_type dE_d = get(partial_derivatives, p);
+
+ // Solve dE_d_d * delta = dE_d to get delta
+ point_difference_type delta = -linear_solver<Point::dimensions>::solve(dE_d_d, dE_d);
+
+ // Move p by delta
+ position[p] = topology.adjust(position[p], delta);
// Recompute partial derivatives and delta_p
deriv_type deriv = compute_partial_derivatives(p);
put(partial_derivatives, p, deriv);
- delta_p =
- sqrt(deriv.first*deriv.first + deriv.second*deriv.second);
+ delta_p = topology.norm(deriv);
} while (!done(delta_p, p, g, false));
// Select new p by updating each partial derivative and delta
@@ -257,12 +313,10 @@
compute_partial_derivative(*ui, old_p);
deriv_type deriv = get(partial_derivatives, *ui);
- deriv.first += old_p_partial.first - old_deriv_p.first;
- deriv.second += old_p_partial.second - old_deriv_p.second;
+ deriv += old_p_partial - old_deriv_p;
put(partial_derivatives, *ui, deriv);
- weight_type delta =
- sqrt(deriv.first*deriv.first + deriv.second*deriv.second);
+ weight_type delta = topology.norm(deriv);
if (delta > delta_p) {
p = *ui;
@@ -274,6 +328,7 @@
return true;
}
+ const Topology& topology;
const Graph& g;
PositionMap position;
WeightMap weight;
@@ -417,7 +472,7 @@
* \returns @c true if layout was successful or @c false if a
* negative weight cycle was detected.
*/
- template<typename Graph, typename PositionMap, typename WeightMap,
+ template<typename Topology, typename Graph, typename PositionMap, typename WeightMap,
typename T, bool EdgeOrSideLength, typename Done,
typename VertexIndexMap, typename DistanceMatrix,
typename SpringStrengthMatrix, typename PartialDerivativeMap>
@@ -426,6 +481,7 @@
const Graph& g,
PositionMap position,
WeightMap weight,
+ const Topology& topology,
detail::graph::edge_or_side<EdgeOrSideLength, T> edge_or_side_length,
Done done,
typename property_traits<WeightMap>::value_type spring_constant,
@@ -440,10 +496,10 @@
>::value));
detail::graph::kamada_kawai_spring_layout_impl<
- Graph, PositionMap, WeightMap,
+ Topology, Graph, PositionMap, WeightMap,
detail::graph::edge_or_side<EdgeOrSideLength, T>, Done, VertexIndexMap,
DistanceMatrix, SpringStrengthMatrix, PartialDerivativeMap>
- alg(g, position, weight, edge_or_side_length, done, spring_constant,
+ alg(topology, g, position, weight, edge_or_side_length, done, spring_constant,
index, distance, spring_strength, partial_derivatives);
return alg.run();
}
@@ -451,7 +507,7 @@
/**
* \overload
*/
- template<typename Graph, typename PositionMap, typename WeightMap,
+ template<typename Topology, typename Graph, typename PositionMap, typename WeightMap,
typename T, bool EdgeOrSideLength, typename Done,
typename VertexIndexMap>
bool
@@ -459,6 +515,7 @@
const Graph& g,
PositionMap position,
WeightMap weight,
+ const Topology& topology,
detail::graph::edge_or_side<EdgeOrSideLength, T> edge_or_side_length,
Done done,
typename property_traits<WeightMap>::value_type spring_constant,
@@ -471,32 +528,33 @@
std::vector<weight_vec> distance(n, weight_vec(n));
std::vector<weight_vec> spring_strength(n, weight_vec(n));
- std::vector<std::pair<weight_type, weight_type> > partial_derivatives(n);
+ std::vector<typename Topology::point_difference_type> partial_derivatives(n);
return
kamada_kawai_spring_layout(
- g, position, weight, edge_or_side_length, done, spring_constant, index,
+ g, position, weight, topology, edge_or_side_length, done, spring_constant, index,
distance.begin(),
spring_strength.begin(),
make_iterator_property_map(partial_derivatives.begin(), index,
- std::pair<weight_type, weight_type>()));
+ typename Topology::point_difference_type()));
}
/**
* \overload
*/
- template<typename Graph, typename PositionMap, typename WeightMap,
+ template<typename Topology, typename Graph, typename PositionMap, typename WeightMap,
typename T, bool EdgeOrSideLength, typename Done>
bool
kamada_kawai_spring_layout(
const Graph& g,
PositionMap position,
WeightMap weight,
+ const Topology& topology,
detail::graph::edge_or_side<EdgeOrSideLength, T> edge_or_side_length,
Done done,
typename property_traits<WeightMap>::value_type spring_constant)
{
- return kamada_kawai_spring_layout(g, position, weight, edge_or_side_length,
+ return kamada_kawai_spring_layout(g, position, weight, topology, edge_or_side_length,
done, spring_constant,
get(vertex_index, g));
}
@@ -504,35 +562,37 @@
/**
* \overload
*/
- template<typename Graph, typename PositionMap, typename WeightMap,
+ template<typename Topology, typename Graph, typename PositionMap, typename WeightMap,
typename T, bool EdgeOrSideLength, typename Done>
bool
kamada_kawai_spring_layout(
const Graph& g,
PositionMap position,
WeightMap weight,
+ const Topology& topology,
detail::graph::edge_or_side<EdgeOrSideLength, T> edge_or_side_length,
Done done)
{
typedef typename property_traits<WeightMap>::value_type weight_type;
- return kamada_kawai_spring_layout(g, position, weight, edge_or_side_length,
+ return kamada_kawai_spring_layout(g, position, weight, topology, edge_or_side_length,
done, weight_type(1));
}
/**
* \overload
*/
- template<typename Graph, typename PositionMap, typename WeightMap,
+ template<typename Topology, typename Graph, typename PositionMap, typename WeightMap,
typename T, bool EdgeOrSideLength>
bool
kamada_kawai_spring_layout(
const Graph& g,
PositionMap position,
WeightMap weight,
+ const Topology& topology,
detail::graph::edge_or_side<EdgeOrSideLength, T> edge_or_side_length)
{
typedef typename property_traits<WeightMap>::value_type weight_type;
- return kamada_kawai_spring_layout(g, position, weight, edge_or_side_length,
+ return kamada_kawai_spring_layout(g, position, weight, topology, edge_or_side_length,
layout_tolerance<weight_type>(),
weight_type(1.0),
get(vertex_index, g));
Modified: trunk/boost/graph/random_layout.hpp
==============================================================================
--- trunk/boost/graph/random_layout.hpp (original)
+++ trunk/boost/graph/random_layout.hpp 2009-04-02 13:59:22 EDT (Thu, 02 Apr 2009)
@@ -15,36 +15,19 @@
#include <boost/random/uniform_real.hpp>
#include <boost/type_traits/is_integral.hpp>
#include <boost/mpl/if.hpp>
+#include <boost/graph/iteration_macros.hpp>
namespace boost {
-template<typename Graph, typename PositionMap,
- typename RandomNumberGenerator>
+template<typename Topology,
+ typename Graph, typename PositionMap>
void
random_graph_layout
(const Graph& g, PositionMap position_map,
- typename property_traits<PositionMap>::value_type const& origin,
- typename property_traits<PositionMap>::value_type const& extent,
- RandomNumberGenerator& gen)
+ const Topology& topology)
{
- typedef typename property_traits<PositionMap>::value_type Point;
- typedef double Dimension;
-
- typedef typename mpl::if_<is_integral<Dimension>,
- uniform_int<Dimension>,
- uniform_real<Dimension> >::type distrib_t;
- typedef typename mpl::if_<is_integral<Dimension>,
- RandomNumberGenerator&,
- uniform_01<RandomNumberGenerator, Dimension> >
- ::type gen_t;
-
- gen_t my_gen(gen);
- distrib_t x(origin.x, origin.x + extent.x);
- distrib_t y(origin.y, origin.y + extent.y);
- typename graph_traits<Graph>::vertex_iterator vi, vi_end;
- for(tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
- position_map[*vi].x = x(my_gen);
- position_map[*vi].y = y(my_gen);
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ put(position_map, v, topology.random_point());
}
}
Added: trunk/boost/graph/topology.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/topology.hpp 2009-04-02 13:59:22 EDT (Thu, 02 Apr 2009)
@@ -0,0 +1,527 @@
+// Copyright 2009 The Trustees of Indiana University.
+
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// Authors: Jeremiah Willcock
+// Douglas Gregor
+// Andrew Lumsdaine
+#ifndef BOOST_GRAPH_TOPOLOGY_HPP
+#define BOOST_GRAPH_TOPOLOGY_HPP
+
+#include <boost/config/no_tr1/cmath.hpp>
+#include <cmath>
+#include <boost/random/uniform_01.hpp>
+#include <boost/random/linear_congruential.hpp>
+#include <boost/math/constants/constants.hpp>
+#include <boost/algorithm/minmax.hpp>
+#include <boost/config.hpp> // For BOOST_STATIC_CONSTANT
+#include <boost/math/special_functions/hypot.hpp>
+
+// Classes and concepts to represent points in a space, with distance and move
+// operations (used for Gurson-Atun layout), plus other things like bounding
+// boxes used for other layout algorithms.
+
+namespace boost {
+
+/***********************************************************
+ * Topologies *
+ ***********************************************************/
+template<std::size_t Dims>
+class convex_topology
+{
+ struct point
+ {
+ BOOST_STATIC_CONSTANT(std::size_t, dimensions = Dims);
+ point() { }
+ double& operator[](std::size_t i) {return values[i];}
+ const double& operator[](std::size_t i) const {return values[i];}
+
+ private:
+ double values[Dims];
+ };
+
+ struct point_difference
+ {
+ BOOST_STATIC_CONSTANT(std::size_t, dimensions = Dims);
+ point_difference() {
+ for (std::size_t i = 0; i < Dims; ++i) values[i] = 0.;
+ }
+ double& operator[](std::size_t i) {return values[i];}
+ const double& operator[](std::size_t i) const {return values[i];}
+
+ friend point_difference operator+(const point_difference& a, const point_difference& b) {
+ point_difference result;
+ for (std::size_t i = 0; i < Dims; ++i)
+ result[i] = a[i] + b[i];
+ return result;
+ }
+
+ friend point_difference& operator+=(point_difference& a, const point_difference& b) {
+ for (std::size_t i = 0; i < Dims; ++i)
+ a[i] += b[i];
+ return a;
+ }
+
+ friend point_difference operator-(const point_difference& a) {
+ point_difference result;
+ for (std::size_t i = 0; i < Dims; ++i)
+ result[i] = -a[i];
+ return result;
+ }
+
+ friend point_difference operator-(const point_difference& a, const point_difference& b) {
+ point_difference result;
+ for (std::size_t i = 0; i < Dims; ++i)
+ result[i] = a[i] - b[i];
+ return result;
+ }
+
+ friend point_difference& operator-=(point_difference& a, const point_difference& b) {
+ for (std::size_t i = 0; i < Dims; ++i)
+ a[i] -= b[i];
+ return a;
+ }
+
+ friend point_difference operator*(const point_difference& a, const point_difference& b) {
+ point_difference result;
+ for (std::size_t i = 0; i < Dims; ++i)
+ result[i] = a[i] * b[i];
+ return result;
+ }
+
+ friend point_difference operator*(const point_difference& a, double b) {
+ point_difference result;
+ for (std::size_t i = 0; i < Dims; ++i)
+ result[i] = a[i] * b;
+ return result;
+ }
+
+ friend point_difference operator*(double a, const point_difference& b) {
+ point_difference result;
+ for (std::size_t i = 0; i < Dims; ++i)
+ result[i] = a * b[i];
+ return result;
+ }
+
+ friend point_difference operator/(const point_difference& a, const point_difference& b) {
+ point_difference result;
+ for (std::size_t i = 0; i < Dims; ++i)
+ result[i] = (b[i] == 0.) ? 0. : a[i] / b[i];
+ return result;
+ }
+
+ private:
+ double values[Dims];
+ };
+
+ public:
+ typedef point point_type;
+ typedef point_difference point_difference_type;
+
+ double distance(point a, point b) const
+ {
+ double dist = 0.;
+ for (std::size_t i = 0; i < Dims; ++i) {
+ double diff = b[i] - a[i];
+ dist = boost::math::hypot(dist, diff);
+ }
+ // Exact properties of the distance are not important, as long as
+ // < on what this returns matches real distances; l_2 is used because
+ // Fruchterman-Reingold also uses this code and it relies on l_2.
+ return dist;
+ }
+
+ point move_position_toward(point a, double fraction, point b) const
+ {
+ point result;
+ for (std::size_t i = 0; i < Dims; ++i)
+ result[i] = a[i] + (b[i] - a[i]) * fraction;
+ return result;
+ }
+
+ point_difference difference(point a, point b) const {
+ point_difference result;
+ for (std::size_t i = 0; i < Dims; ++i)
+ result[i] = a[i] - b[i];
+ return result;
+ }
+
+ point adjust(point a, point_difference delta) const {
+ point result;
+ for (std::size_t i = 0; i < Dims; ++i)
+ result[i] = a[i] + delta[i];
+ return result;
+ }
+
+ point pointwise_min(point a, point b) const {
+ BOOST_USING_STD_MIN();
+ point result;
+ for (std::size_t i = 0; i < Dims; ++i)
+ result[i] = min BOOST_PREVENT_MACRO_SUBSTITUTION (a[i], b[i]);
+ return result;
+ }
+
+ point pointwise_max(point a, point b) const {
+ BOOST_USING_STD_MAX();
+ point result;
+ for (std::size_t i = 0; i < Dims; ++i)
+ result[i] = max BOOST_PREVENT_MACRO_SUBSTITUTION (a[i], b[i]);
+ return result;
+ }
+
+ double norm(point_difference delta) const {
+ double n = 0.;
+ for (std::size_t i = 0; i < Dims; ++i)
+ n = boost::math::hypot(n, delta[i]);
+ return n;
+ }
+
+ double volume(point_difference delta) const {
+ double n = 1.;
+ for (std::size_t i = 0; i < Dims; ++i)
+ n *= delta[i];
+ return n;
+ }
+
+};
+
+template<std::size_t Dims,
+ typename RandomNumberGenerator = minstd_rand>
+class hypercube_topology : public convex_topology<Dims>
+{
+ typedef uniform_01<RandomNumberGenerator, double> rand_t;
+
+ public:
+ typedef typename convex_topology<Dims>::point_type point_type;
+ typedef typename convex_topology<Dims>::point_difference_type point_difference_type;
+
+ explicit hypercube_topology(double scaling = 1.0)
+ : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)),
+ scaling(scaling)
+ { }
+
+ hypercube_topology(RandomNumberGenerator& gen, double scaling = 1.0)
+ : gen_ptr(), rand(new rand_t(gen)), scaling(scaling) { }
+
+ point_type random_point() const
+ {
+ point_type p;
+ for (std::size_t i = 0; i < Dims; ++i)
+ p[i] = (*rand)() * scaling;
+ return p;
+ }
+
+ point_type bound(point_type a) const
+ {
+ BOOST_USING_STD_MIN();
+ BOOST_USING_STD_MAX();
+ point_type p;
+ for (std::size_t i = 0; i < Dims; ++i)
+ p[i] = min BOOST_PREVENT_MACRO_SUBSTITUTION (scaling, max BOOST_PREVENT_MACRO_SUBSTITUTION (-scaling, a[i]));
+ return p;
+ }
+
+ double distance_from_boundary(point_type a) const
+ {
+ BOOST_USING_STD_MIN();
+ BOOST_USING_STD_MAX();
+#ifndef BOOST_NO_STDC_NAMESPACE
+ using std::abs;
+#endif
+ BOOST_STATIC_ASSERT (Dims >= 1);
+ double dist = abs(scaling - a[0]);
+ for (std::size_t i = 1; i < Dims; ++i)
+ dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(scaling - a[i]));
+ return dist;
+ }
+
+ private:
+ shared_ptr<RandomNumberGenerator> gen_ptr;
+ shared_ptr<rand_t> rand;
+ double scaling;
+};
+
+template<typename RandomNumberGenerator = minstd_rand>
+class square_topology : public hypercube_topology<2, RandomNumberGenerator>
+{
+ typedef hypercube_topology<2, RandomNumberGenerator> inherited;
+
+ public:
+ explicit square_topology(double scaling = 1.0) : inherited(scaling) { }
+
+ square_topology(RandomNumberGenerator& gen, double scaling = 1.0)
+ : inherited(gen, scaling) { }
+};
+
+template<typename RandomNumberGenerator = minstd_rand>
+class rectangle_topology : public convex_topology<2>
+{
+ typedef uniform_01<RandomNumberGenerator, double> rand_t;
+
+ public:
+ rectangle_topology(double left, double top, double right, double bottom)
+ : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)),
+ left(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (left, right)),
+ top(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)),
+ right(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (left, right)),
+ bottom(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)) { }
+
+ rectangle_topology(RandomNumberGenerator& gen, double left, double top, double right, double bottom)
+ : gen_ptr(), rand(new rand_t(gen)),
+ left(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (left, right)),
+ top(std::min BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)),
+ right(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (left, right)),
+ bottom(std::max BOOST_PREVENT_MACRO_SUBSTITUTION (top, bottom)) { }
+
+ typedef typename convex_topology<2>::point_type point_type;
+ typedef typename convex_topology<2>::point_difference_type point_difference_type;
+
+ point_type random_point() const
+ {
+ point_type p;
+ p[0] = (*rand)() * (right - left) + left;
+ p[1] = (*rand)() * (bottom - top) + top;
+ return p;
+ }
+
+ point_type bound(point_type a) const
+ {
+ BOOST_USING_STD_MIN();
+ BOOST_USING_STD_MAX();
+ point_type p;
+ p[0] = min BOOST_PREVENT_MACRO_SUBSTITUTION (right, max BOOST_PREVENT_MACRO_SUBSTITUTION (left, a[0]));
+ p[1] = min BOOST_PREVENT_MACRO_SUBSTITUTION (bottom, max BOOST_PREVENT_MACRO_SUBSTITUTION (top, a[1]));
+ return p;
+ }
+
+ double distance_from_boundary(point_type a) const
+ {
+ BOOST_USING_STD_MIN();
+ BOOST_USING_STD_MAX();
+#ifndef BOOST_NO_STDC_NAMESPACE
+ using std::abs;
+#endif
+ double dist = abs(left - a[0]);
+ dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(right - a[0]));
+ dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(top - a[1]));
+ dist = min BOOST_PREVENT_MACRO_SUBSTITUTION (dist, abs(bottom - a[1]));
+ return dist;
+ }
+
+ private:
+ shared_ptr<RandomNumberGenerator> gen_ptr;
+ shared_ptr<rand_t> rand;
+ double left, top, right, bottom;
+};
+
+template<typename RandomNumberGenerator = minstd_rand>
+class cube_topology : public hypercube_topology<3, RandomNumberGenerator>
+{
+ typedef hypercube_topology<3, RandomNumberGenerator> inherited;
+
+ public:
+ explicit cube_topology(double scaling = 1.0) : inherited(scaling) { }
+
+ cube_topology(RandomNumberGenerator& gen, double scaling = 1.0)
+ : inherited(gen, scaling) { }
+};
+
+template<std::size_t Dims,
+ typename RandomNumberGenerator = minstd_rand>
+class ball_topology : public convex_topology<Dims>
+{
+ typedef uniform_01<RandomNumberGenerator, double> rand_t;
+
+ public:
+ typedef typename convex_topology<Dims>::point_type point_type;
+
+ explicit ball_topology(double radius = 1.0)
+ : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)),
+ radius(radius)
+ { }
+
+ ball_topology(RandomNumberGenerator& gen, double radius = 1.0)
+ : gen_ptr(), rand(new rand_t(gen)), radius(radius) { }
+
+ point_type random_point() const
+ {
+ point_type p;
+ double dist_sum;
+ do {
+ dist_sum = 0.0;
+ for (std::size_t i = 0; i < Dims; ++i) {
+ double x = (*rand)() * 2*radius - radius;
+ p[i] = x;
+ dist_sum += x * x;
+ }
+ } while (dist_sum > radius*radius);
+ return p;
+ }
+
+ point_type bound(point_type a) const
+ {
+ BOOST_USING_STD_MIN();
+ BOOST_USING_STD_MAX();
+ double r = 0.;
+ for (std::size_t i = 0; i < Dims; ++i)
+ r = boost::math::hypot(r, a[i]);
+ if (r <= radius) return a;
+ double scaling_factor = radius / r;
+ point_type p;
+ for (std::size_t i = 0; i < Dims; ++i)
+ p[i] = a[i] * scaling_factor;
+ return p;
+ }
+
+ double distance_from_boundary(point_type a) const
+ {
+ double r = 0.;
+ for (std::size_t i = 0; i < Dims; ++i)
+ r = boost::math::hypot(r, a[i]);
+ return radius - r;
+ }
+
+ private:
+ shared_ptr<RandomNumberGenerator> gen_ptr;
+ shared_ptr<rand_t> rand;
+ double radius;
+};
+
+template<typename RandomNumberGenerator = minstd_rand>
+class circle_topology : public ball_topology<2, RandomNumberGenerator>
+{
+ typedef ball_topology<2, RandomNumberGenerator> inherited;
+
+ public:
+ explicit circle_topology(double radius = 1.0) : inherited(radius) { }
+
+ circle_topology(RandomNumberGenerator& gen, double radius = 1.0)
+ : inherited(gen, radius) { }
+};
+
+template<typename RandomNumberGenerator = minstd_rand>
+class sphere_topology : public ball_topology<3, RandomNumberGenerator>
+{
+ typedef ball_topology<3, RandomNumberGenerator> inherited;
+
+ public:
+ explicit sphere_topology(double radius = 1.0) : inherited(radius) { }
+
+ sphere_topology(RandomNumberGenerator& gen, double radius = 1.0)
+ : inherited(gen, radius) { }
+};
+
+template<typename RandomNumberGenerator = minstd_rand>
+class heart_topology
+{
+ // Heart is defined as the union of three shapes:
+ // Square w/ corners (+-1000, -1000), (0, 0), (0, -2000)
+ // Circle centered at (-500, -500) radius 500*sqrt(2)
+ // Circle centered at (500, -500) radius 500*sqrt(2)
+ // Bounding box (-1000, -2000) - (1000, 500*(sqrt(2) - 1))
+
+ struct point
+ {
+ point() { values[0] = 0.0; values[1] = 0.0; }
+ point(double x, double y) { values[0] = x; values[1] = y; }
+
+ double& operator[](std::size_t i) { return values[i]; }
+ double operator[](std::size_t i) const { return values[i]; }
+
+ private:
+ double values[2];
+ };
+
+ bool in_heart(point p) const
+ {
+#ifndef BOOST_NO_STDC_NAMESPACE
+ using std::abs;
+ using boost::math::constants::root_two;
+#endif
+
+ if (p[1] < abs(p[0]) - 2000) return false; // Bottom
+ if (p[1] <= -1000) return true; // Diagonal of square
+ if (boost::math::hypot(p[0] - -500, p[1] - -500) <= 500. * root_two<double>())
+ return true; // Left circle
+ if (boost::math::hypot(p[0] - 500, p[1] - -500) <= 500. * root_two<double>())
+ return true; // Right circle
+ return false;
+ }
+
+ bool segment_within_heart(point p1, point p2) const
+ {
+ // Assumes that p1 and p2 are within the heart
+ if ((p1[0] < 0) == (p2[0] < 0)) return true; // Same side of symmetry line
+ if (p1[0] == p2[0]) return true; // Vertical
+ double slope = (p2[1] - p1[1]) / (p2[0] - p1[0]);
+ double intercept = p1[1] - p1[0] * slope;
+ if (intercept > 0) return false; // Crosses between circles
+ return true;
+ }
+
+ typedef uniform_01<RandomNumberGenerator, double> rand_t;
+
+ public:
+ typedef point point_type;
+
+ heart_topology()
+ : gen_ptr(new RandomNumberGenerator), rand(new rand_t(*gen_ptr)) { }
+
+ heart_topology(RandomNumberGenerator& gen)
+ : gen_ptr(), rand(new rand_t(gen)) { }
+
+ point random_point() const
+ {
+ point result;
+ using boost::math::constants::root_two;
+ do {
+ result[0] = (*rand)() * (1000 + 1000 * root_two<double>()) - (500 + 500 * root_two<double>());
+ result[1] = (*rand)() * (2000 + 500 * (root_two<double>() - 1)) - 2000;
+ } while (!in_heart(result));
+ return result;
+ }
+
+ // Not going to provide clipping to bounding region or distance from boundary
+
+ double distance(point a, point b) const
+ {
+ if (segment_within_heart(a, b)) {
+ // Straight line
+ return boost::math::hypot(b[0] - a[0], b[1] - a[1]);
+ } else {
+ // Straight line bending around (0, 0)
+ return boost::math::hypot(a[0], a[1]) + boost::math::hypot(b[0], b[1]);
+ }
+ }
+
+ point move_position_toward(point a, double fraction, point b) const
+ {
+ if (segment_within_heart(a, b)) {
+ // Straight line
+ return point(a[0] + (b[0] - a[0]) * fraction,
+ a[1] + (b[1] - a[1]) * fraction);
+ } else {
+ double distance_to_point_a = boost::math::hypot(a[0], a[1]);
+ double distance_to_point_b = boost::math::hypot(b[0], b[1]);
+ double location_of_point = distance_to_point_a /
+ (distance_to_point_a + distance_to_point_b);
+ if (fraction < location_of_point)
+ return point(a[0] * (1 - fraction / location_of_point),
+ a[1] * (1 - fraction / location_of_point));
+ else
+ return point(
+ b[0] * ((fraction - location_of_point) / (1 - location_of_point)),
+ b[1] * ((fraction - location_of_point) / (1 - location_of_point)));
+ }
+ }
+
+ private:
+ shared_ptr<RandomNumberGenerator> gen_ptr;
+ shared_ptr<rand_t> rand;
+};
+
+} // namespace boost
+
+#endif // BOOST_GRAPH_TOPOLOGY_HPP
Modified: trunk/libs/graph/test/layout_test.cpp
==============================================================================
--- trunk/libs/graph/test/layout_test.cpp (original)
+++ trunk/libs/graph/test/layout_test.cpp 2009-04-02 13:59:22 EDT (Thu, 02 Apr 2009)
@@ -23,31 +23,26 @@
enum vertex_position_t { vertex_position };
namespace boost { BOOST_INSTALL_PROPERTY(vertex, position); }
-struct point
-{
- double x, y;
- point(double x, double y): x(x), y(y) {}
- point() {}
-};
+typedef square_topology<>::point_type point;
-template<typename Graph, typename PositionMap>
-void print_graph_layout(const Graph& g, PositionMap position)
+template<typename Graph, typename PositionMap, typename Topology>
+void print_graph_layout(const Graph& g, PositionMap position, const Topology& topology)
{
- typename graph_traits<Graph>::vertex_iterator vi, vi_end;
- int xmin = 0, xmax = 0, ymin = 0, ymax = 0;
- for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
- if ((int)position[*vi].x < xmin) xmin = (int)position[*vi].x;
- if ((int)position[*vi].x > xmax) xmax = (int)position[*vi].x;
- if ((int)position[*vi].y < ymin) ymin = (int)position[*vi].y;
- if ((int)position[*vi].y > ymax) ymax = (int)position[*vi].y;
+ typedef typename Topology::point_type Point;
+ // Find min/max ranges
+ Point min_point = position[*vertices(g).first], max_point = min_point;
+ BGL_FORALL_VERTICES_T(v, g, Graph) {
+ min_point = topology.pointwise_min(min_point, position[v]);
+ max_point = topology.pointwise_max(max_point, position[v]);
}
- for (int y = ymin; y <= ymax; ++y) {
- for (int x = xmin; x <= xmax; ++x) {
+ for (int y = min_point[1]; y <= max_point[1]; ++y) {
+ for (int x = min_point[0]; x <= max_point[0]; ++x) {
+ typename graph_traits<Graph>::vertex_iterator vi, vi_end;
// Find vertex at this position
typename graph_traits<Graph>::vertices_size_type index = 0;
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi, ++index) {
- if ((int)position[*vi].x == x && (int)position[*vi].y == y)
+ if ((int)position[*vi][0] == x && (int)position[*vi][1] == y)
break;
}
@@ -67,7 +62,7 @@
typename graph_traits<Graph>::vertex_iterator vi, vi_end;
for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
out << " n" << get(vertex_index, g, *vi) << "[ pos=\""
- << (int)position[*vi].x + 25 << ", " << (int)position[*vi].y + 25
+ << (int)position[*vi][0] + 25 << ", " << (int)position[*vi][1] + 25
<< "\" ];\n";
}
@@ -98,7 +93,8 @@
circle_graph_layout(g, get(vertex_position, g), 10.0);
std::cout << "Regular polygon layout with " << n << " points.\n";
- print_graph_layout(g, get(vertex_position, g));
+ square_topology<> topology;
+ print_graph_layout(g, get(vertex_position, g), topology);
}
struct simple_edge
@@ -151,6 +147,7 @@
bool ok = kamada_kawai_spring_layout(g,
get(vertex_position, g),
get(edge_weight, g),
+ square_topology<>(50.0),
side_length(50.0));
BOOST_CHECK(ok);
@@ -192,37 +189,43 @@
bool ok = kamada_kawai_spring_layout(g,
get(vertex_position, g),
get(edge_weight, g),
+ square_topology<>(50.0),
side_length(50.0),
kamada_kawai_done());
BOOST_CHECK(ok);
std::cout << "Cube layout (Kamada-Kawai).\n";
- print_graph_layout(g, get(vertex_position, g));
+ print_graph_layout(g, get(vertex_position, g), square_topology<>(50.));
dump_graph_layout("cube", g, get(vertex_position, g));
minstd_rand gen;
- random_graph_layout(g, get(vertex_position, g),
- point(-25.0, -25.0),
- point(25.0, 25.0),
- gen);
+ typedef square_topology<> Topology;
+ Topology topology(gen, 50.0);
+ std::vector<Topology::point_difference_type> displacements(num_vertices(g));
+ Topology::point_type origin;
+ origin[0] = origin[1] = 50.0;
+ Topology::point_difference_type extent;
+ extent[0] = extent[1] = 50.0;
+ rectangle_topology<> rect_top(gen, 0, 0, 50, 50);
+ random_graph_layout(g, get(vertex_position, g), rect_top);
- std::vector<point> displacements(num_vertices(g));
fruchterman_reingold_force_directed_layout
(g,
get(vertex_position, g),
- point(50.0, 50.0),
- point(50.0, 50.0),
+ topology,
+ origin,
+ extent,
square_distance_attractive_force(),
square_distance_repulsive_force(),
all_force_pairs(),
linear_cooling<double>(100),
make_iterator_property_map(displacements.begin(),
get(vertex_index, g),
- point()));
+ Topology::point_difference_type()));
std::cout << "Cube layout (Fruchterman-Reingold).\n";
- print_graph_layout(g, get(vertex_position, g));
+ print_graph_layout(g, get(vertex_position, g), square_topology<>(50.));
dump_graph_layout("cube-fr", g, get(vertex_position, g));
}
@@ -256,37 +259,46 @@
}
std::cerr << std::endl;
+ typedef square_topology<> Topology;
+ minstd_rand gen;
+ Topology topology(gen, 50.0);
+ Topology::point_type origin;
+ origin[0] = origin[1] = 50.0;
+ Topology::point_difference_type extent;
+ extent[0] = extent[1] = 50.0;
+
circle_graph_layout(g, get(vertex_position, g), 25.0);
bool ok = kamada_kawai_spring_layout(g,
get(vertex_position, g),
get(edge_weight, g),
+ topology,
side_length(50.0),
kamada_kawai_done());
BOOST_CHECK(ok);
std::cout << "Triangular layout (Kamada-Kawai).\n";
- print_graph_layout(g, get(vertex_position, g));
+ print_graph_layout(g, get(vertex_position, g), square_topology<>(50.));
dump_graph_layout("triangular-kk", g, get(vertex_position, g));
- minstd_rand gen;
- random_graph_layout(g, get(vertex_position, g), point(-25.0, -25.0), point(25.0, 25.0),
- gen);
+ rectangle_topology<> rect_top(gen, -25, -25, 25, 25);
+ random_graph_layout(g, get(vertex_position, g), rect_top);
dump_graph_layout("random", g, get(vertex_position, g));
- std::vector<point> displacements(num_vertices(g));
+ std::vector<Topology::point_difference_type> displacements(num_vertices(g));
fruchterman_reingold_force_directed_layout
(g,
get(vertex_position, g),
- point(50.0, 50.0),
- point(50.0, 50.0),
+ topology,
+ origin,
+ extent,
attractive_force(square_distance_attractive_force()).
cooling(linear_cooling<double>(100)));
std::cout << "Triangular layout (Fruchterman-Reingold).\n";
- print_graph_layout(g, get(vertex_position, g));
+ print_graph_layout(g, get(vertex_position, g), square_topology<>(50.));
dump_graph_layout("triangular-fr", g, get(vertex_position, g));
}
@@ -326,25 +338,33 @@
bool ok = kamada_kawai_spring_layout(g,
get(vertex_position, g),
get(edge_weight, g),
+ square_topology<>(50.0),
side_length(50.0),
kamada_kawai_done());
BOOST_CHECK(!ok);
minstd_rand gen;
- random_graph_layout(g, get(vertex_position, g), point(-25.0, -25.0), point(25.0, 25.0),
- gen);
+ rectangle_topology<> rect_top(gen, -25, -25, 25, 25);
+ random_graph_layout(g, get(vertex_position, g), rect_top);
- std::vector<point> displacements(num_vertices(g));
+ typedef square_topology<> Topology;
+ Topology topology(gen, 50.0);
+ std::vector<Topology::point_difference_type> displacements(num_vertices(g));
+ Topology::point_type origin;
+ origin[0] = origin[1] = 50.0;
+ Topology::point_difference_type extent;
+ extent[0] = extent[1] = 50.0;
fruchterman_reingold_force_directed_layout
(g,
get(vertex_position, g),
- point(50.0, 50.0),
- point(50.0, 50.0),
+ topology,
+ origin,
+ extent,
attractive_force(square_distance_attractive_force()).
cooling(linear_cooling<double>(50)));
std::cout << "Disconnected layout (Fruchterman-Reingold).\n";
- print_graph_layout(g, get(vertex_position, g));
+ print_graph_layout(g, get(vertex_position, g), square_topology<>(50.));
dump_graph_layout("disconnected-fr", g, get(vertex_position, g));
}