Boost logo

Boost-Commit :

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));
 }


Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk