[Boost-commit] svn:boost r56732 - trunk/boost/graph

Subject: [Boost-commit] svn:boost r56732 - trunk/boost/graph
From: jewillco_at_[hidden]
Date: 2009-10-12 11:01:30

Author: jewillco
Date: 2009-10-12 11:01:29 EDT (Mon, 12 Oct 2009)
New Revision: 56732
URL: http://svn.boost.org/trac/boost/changeset/56732

Log:
Fixed bugs in F-R layout
Text files modified: 
   trunk/boost/graph/fruchterman_reingold.hpp |    66 ++++++++++++++++++++--------------------
   1 files changed, 33 insertions(+), 33 deletions(-)

Modified: trunk/boost/graph/fruchterman_reingold.hpp
==============================================================================
--- trunk/boost/graph/fruchterman_reingold.hpp	(original)
+++ trunk/boost/graph/fruchterman_reingold.hpp	2009-10-12 11:01:29 EDT (Mon, 12 Oct 2009)
@@ -118,9 +118,9 @@
     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][0] + topology.extent()[0] / 2) / two_k);
+        std::size_t((get(position, *v)[0] + topology.extent()[0] / 2) / two_k);
       std::size_t row    =
-        std::size_t((position[*v][1] + topology.extent()[1] / 2) / two_k);
+        std::size_t((get(position, *v)[1] + topology.extent()[1] / 2) / two_k);
 
       if (column >= columns) column = columns - 1;
       if (row >= rows) row = rows - 1;
@@ -152,7 +152,8 @@
                 bucket_t& other_bucket
                   = buckets[other_row * columns + other_column];
                 for (v = other_bucket.begin(); v != other_bucket.end(); ++v) {
-                  double dist = topology.distance(position[*u], position[*v]);
+                  double dist =
+                    topology.distance(get(position, *u), get(position, *v));
                   if (dist < two_k) apply_force(*u, *v);
                 }
               }
@@ -184,10 +185,10 @@
   typedef typename Topology::point_difference_type point_difference_type;
 
   // Find min/max ranges
-  Point min_point = position[*vertices(g).first], max_point = min_point;
+  Point min_point = get(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]);
+    min_point = topology.pointwise_min(min_point, get(position, v));
+    max_point = topology.pointwise_max(max_point, get(position, v));
   }
 
   Point old_origin = topology.move_position_toward(min_point, 0.5, max_point);
@@ -197,21 +198,24 @@
 
   // Scale to bounding box provided
   BGL_FORALL_VERTICES_T(v, g, Graph) {
-    point_difference_type relative_loc = topology.difference(position[v], old_origin);
+    point_difference_type relative_loc = topology.difference(get(position, v), old_origin);
     relative_loc = (relative_loc / old_size) * new_size;
-    position[v] = topology.adjust(new_origin, relative_loc);
+    put(position, v, topology.adjust(new_origin, relative_loc));
   }
 }
 
 namespace detail {
-  template<typename Topology>
+  template<typename Topology, typename PropMap, typename Vertex>
   void 
   maybe_jitter_point(const Topology& topology,
-                     typename Topology::point_type& p1, const typename Topology::point_type& p2)
+                     const PropMap& pm, Vertex v,
+                     const typename Topology::point_type& p2)
   {
     double too_close = topology.norm(topology.extent()) / 10000.;
-    if (topology.distance(p1, p2) < too_close) {
-      p1 = topology.move_position_toward(p1, 1./200, topology.random_point());
+    if (topology.distance(get(pm, v), p2) < too_close) {
+      put(pm, v, 
+          topology.move_position_toward(get(pm, v), 1./200,
+                                        topology.random_point()));
     }
   }
 
@@ -236,18 +240,20 @@
       if (u != v) {
         // When the vertices land on top of each other, move the
         // first vertex away from the boundaries.
-        maybe_jitter_point(topology, position[u], position[v]);
+        maybe_jitter_point(topology, position, u, get(position, v));
 
-        double dist = topology.distance(position[u], position[v]);
+        double dist = topology.distance(get(position, u), get(position, v));
+        typename Topology::point_difference_type dispv = get(displacement, v);
         if (dist == 0.) {
           for (std::size_t i = 0; i < Point::dimensions; ++i) {
-            displacement[v][i] += 0.01;
+            dispv[i] += 0.01;
           }
         } else {
           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]);
+          dispv += (fr / dist) *
+                   topology.difference(get(position, v), get(position, u));
         }
+        put(displacement, v, dispv);
       }
     }
 
@@ -294,7 +300,7 @@
     // Calculate repulsive forces
     vertex_iterator v, v_end;
     for (tie(v, v_end) = vertices(g); v != v_end; ++v)
-      displacement[*v] = typename Topology::point_difference_type();
+      put(displacement, *v, typename Topology::point_difference_type());
     force_pairs(g, apply_force);
 
     // Calculate attractive forces
@@ -305,14 +311,15 @@
 
       // When the vertices land on top of each other, move the
       // first vertex away from the boundaries.
-      ::boost::detail::maybe_jitter_point(topology, position[u], position[v]);
+      ::boost::detail::maybe_jitter_point(topology, position, u, get(position, v));
 
-      typename Topology::point_difference_type delta = topology.difference(position[v], position[u]);
-      double dist = topology.distance(position[u], position[v]);
+      typename Topology::point_difference_type delta =
+        topology.difference(get(position, v), get(position, u));
+      double dist = topology.distance(get(position, u), get(position, v));
       double fa = attractive_force(*e, k, dist, g);
 
-      displacement[v] -= (fa / dist) * delta;
-      displacement[u] += (fa / dist) * delta;
+      put(displacement, v, get(displacement, v) - (fa / dist) * delta);
+      put(displacement, u, get(displacement, u) + (fa / dist) * delta);
     }
 
     if (double temp = cool()) {
@@ -320,16 +327,9 @@
       BGL_FORALL_VERTICES_T (v, g, Graph) {
         BOOST_USING_STD_MIN();
         BOOST_USING_STD_MAX();
-        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
+        double disp_size = topology.norm(get(displacement, v));
+        put(position, v, topology.adjust(get(position, v), get(displacement, v) * (min BOOST_PREVENT_MACRO_SUBSTITUTION (disp_size, temp) / disp_size)));
+        put(position, v, topology.bound(get(position, v)));
       }
     } else {
       break;