#include <cmath> // for std::sqrt and std::fabs
#include <functional>
-namespace boost {
-
-struct square_distance_attractive_force {
- template<typename Graph, typename T>
- T
- operator()(typename graph_traits<Graph>::edge_descriptor,
- T k,
- T d,
- const Graph&) const
- {
- return d * d / k;
- }
+namespace boost
+{
+
+struct square_distance_attractive_force
+{
+ template < typename Graph, typename T >
+ T operator()(typename graph_traits< Graph >::edge_descriptor, T k, T d,
+ const Graph&) const
+ {
+ return d * d / k;
+ }
};
-struct square_distance_repulsive_force {
- template<typename Graph, typename T>
- T
- operator()(typename graph_traits<Graph>::vertex_descriptor,
- typename graph_traits<Graph>::vertex_descriptor,
- T k,
- T d,
- const Graph&) const
- {
- return k * k / d;
- }
+struct square_distance_repulsive_force
+{
+ template < typename Graph, typename T >
+ T operator()(typename graph_traits< Graph >::vertex_descriptor,
+ typename graph_traits< Graph >::vertex_descriptor, T k, T d,
+ const Graph&) const
+ {
+ return k * k / d;
+ }
};
-template<typename T>
-struct linear_cooling {
- typedef T result_type;
+template < typename T > struct linear_cooling
+{
+ typedef T result_type;
- linear_cooling(std::size_t iterations)
- : temp(T(iterations) / T(10)), step(0.1) { }
+ linear_cooling(std::size_t iterations)
+ : temp(T(iterations) / T(10)), step(0.1)
+ {
+ }
- linear_cooling(std::size_t iterations, T temp)
- : temp(temp), step(temp / T(iterations)) { }
+ linear_cooling(std::size_t iterations, T temp)
+ : temp(temp), step(temp / T(iterations))
+ {
+ }
- T operator()()
- {
- T old_temp = temp;
- temp -= step;
- if (temp < T(0)) temp = T(0);
- return old_temp;
- }
+ T operator()()
+ {
+ T old_temp = temp;
+ temp -= step;
+ if (temp < T(0))
+ temp = T(0);
+ return old_temp;
+ }
- private:
- T temp;
- T step;
+private:
+ T temp;
+ T step;
};
struct all_force_pairs
{
- template<typename Graph, typename ApplyForce >
- void operator()(const Graph& g, ApplyForce apply_force)
- {
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
- vertex_iterator v, end;
- for (boost::tie(v, end) = vertices(g); v != end; ++v) {
- vertex_iterator u = v;
- for (++u; u != end; ++u) {
- apply_force(*u, *v);
- apply_force(*v, *u);
- }
+ template < typename Graph, typename ApplyForce >
+ void operator()(const Graph& g, ApplyForce apply_force)
+ {
+ typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator;
+ vertex_iterator v, end;
+ for (boost::tie(v, end) = vertices(g); v != end; ++v)
+ {
+ vertex_iterator u = v;
+ for (++u; u != end; ++u)
+ {
+ apply_force(*u, *v);
+ apply_force(*v, *u);
+ }
+ }
}
- }
};
-template<typename Topology, typename PositionMap>
-struct grid_force_pairs
+template < typename Topology, typename PositionMap > struct grid_force_pairs
{
- typedef typename property_traits<PositionMap>::value_type Point;
- BOOST_STATIC_ASSERT (Point::dimensions == 2);
- typedef typename Topology::point_difference_type point_difference_type;
-
- template<typename Graph>
- explicit
- grid_force_pairs(const Topology& topology,
- PositionMap position, const Graph& g)
+ typedef typename property_traits< PositionMap >::value_type Point;
+ BOOST_STATIC_ASSERT(Point::dimensions == 2);
+ typedef typename Topology::point_difference_type point_difference_type;
+
+ template < typename Graph >
+ explicit grid_force_pairs(
+ const Topology& topology, PositionMap position, const Graph& g)
: topology(topology), position(position)
- {
- two_k = 2. * this->topology.volume(this->topology.extent()) / std::sqrt((double)num_vertices(g));
- }
-
- template<typename Graph, typename ApplyForce >
- void operator()(const Graph& g, ApplyForce apply_force)
- {
- typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
- typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
- typedef std::list<vertex_descriptor> bucket_t;
- typedef std::vector<bucket_t> buckets_t;
-
- std::size_t columns = std::size_t(topology.extent()[0] / two_k + 1.);
- std::size_t rows = std::size_t(topology.extent()[1] / two_k + 1.);
- buckets_t buckets(rows * columns);
- vertex_iterator v, v_end;
- for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v) {
- std::size_t column =
- std::size_t((get(position, *v)[0] + topology.extent()[0] / 2) / two_k);
- std::size_t row =
- 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;
- buckets[row * columns + column].push_back(*v);
+ {
+ two_k = 2. * this->topology.volume(this->topology.extent())
+ / std::sqrt((double)num_vertices(g));
}
- for (std::size_t row = 0; row < rows; ++row)
- for (std::size_t column = 0; column < columns; ++column) {
- bucket_t& bucket = buckets[row * columns + column];
- typedef typename bucket_t::iterator bucket_iterator;
- for (bucket_iterator u = bucket.begin(); u != bucket.end(); ++u) {
- // Repulse vertices in this bucket
- bucket_iterator v = u;
- for (++v; v != bucket.end(); ++v) {
- apply_force(*u, *v);
- apply_force(*v, *u);
- }
-
- std::size_t adj_start_row = row == 0? 0 : row - 1;
- std::size_t adj_end_row = row == rows - 1? row : row + 1;
- std::size_t adj_start_column = column == 0? 0 : column - 1;
- std::size_t adj_end_column = column == columns - 1? column : column + 1;
- for (std::size_t other_row = adj_start_row; other_row <= adj_end_row;
- ++other_row)
- for (std::size_t other_column = adj_start_column;
- other_column <= adj_end_column; ++other_column)
- if (other_row != row || other_column != column) {
- // Repulse vertices in this bucket
- bucket_t& other_bucket
- = buckets[other_row * columns + other_column];
- for (v = other_bucket.begin(); v != other_bucket.end(); ++v) {
- double dist =
- topology.distance(get(position, *u), get(position, *v));
- if (dist < two_k) apply_force(*u, *v);
- }
- }
+ template < typename Graph, typename ApplyForce >
+ void operator()(const Graph& g, ApplyForce apply_force)
+ {
+ typedef typename graph_traits< Graph >::vertex_iterator vertex_iterator;
+ typedef
+ typename graph_traits< Graph >::vertex_descriptor vertex_descriptor;
+ typedef std::list< vertex_descriptor > bucket_t;
+ typedef std::vector< bucket_t > buckets_t;
+
+ std::size_t columns = std::size_t(topology.extent()[0] / two_k + 1.);
+ std::size_t rows = std::size_t(topology.extent()[1] / two_k + 1.);
+ buckets_t buckets(rows * columns);
+ vertex_iterator v, v_end;
+ for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v)
+ {
+ std::size_t column = std::size_t(
+ (get(position, *v)[0] + topology.extent()[0] / 2) / two_k);
+ std::size_t row = 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;
+ buckets[row * columns + column].push_back(*v);
}
- }
- }
- private:
- const Topology& topology;
- PositionMap position;
- double two_k;
+ for (std::size_t row = 0; row < rows; ++row)
+ for (std::size_t column = 0; column < columns; ++column)
+ {
+ bucket_t& bucket = buckets[row * columns + column];
+ typedef typename bucket_t::iterator bucket_iterator;
+ for (bucket_iterator u = bucket.begin(); u != bucket.end(); ++u)
+ {
+ // Repulse vertices in this bucket
+ bucket_iterator v = u;
+ for (++v; v != bucket.end(); ++v)
+ {
+ apply_force(*u, *v);
+ apply_force(*v, *u);
+ }
+
+ std::size_t adj_start_row = row == 0 ? 0 : row - 1;
+ std::size_t adj_end_row = row == rows - 1 ? row : row + 1;
+ std::size_t adj_start_column = column == 0 ? 0 : column - 1;
+ std::size_t adj_end_column
+ = column == columns - 1 ? column : column + 1;
+ for (std::size_t other_row = adj_start_row;
+ other_row <= adj_end_row; ++other_row)
+ for (std::size_t other_column = adj_start_column;
+ other_column <= adj_end_column; ++other_column)
+ if (other_row != row || other_column != column)
+ {
+ // Repulse vertices in this bucket
+ bucket_t& other_bucket
+ = buckets[other_row * columns
+ + other_column];
+ for (v = other_bucket.begin();
+ v != other_bucket.end(); ++v)
+ {
+ double dist = topology.distance(
+ get(position, *u), get(position, *v));
+ if (dist < two_k)
+ apply_force(*u, *v);
+ }
+ }
+ }
+ }
+ }
+
+private:
+ const Topology& topology;
+ PositionMap position;
+ double two_k;
};
-template<typename PositionMap, typename Topology, typename Graph>
-inline grid_force_pairs<Topology, PositionMap>
-make_grid_force_pairs
- (const Topology& topology,
- const PositionMap& position, const Graph& g)
-{ return grid_force_pairs<Topology, PositionMap>(topology, position, g); }
-
-template<typename Graph, typename PositionMap, typename Topology>
-void
-scale_graph(const Graph& g, PositionMap position, const Topology& topology,
- typename Topology::point_type upper_left, typename Topology::point_type lower_right)
+template < typename PositionMap, typename Topology, typename Graph >
+inline grid_force_pairs< Topology, PositionMap > make_grid_force_pairs(
+ const Topology& topology, const PositionMap& position, const Graph& g)
{
- if (num_vertices(g) == 0) return;
-
- typedef typename Topology::point_type Point;
- typedef typename Topology::point_difference_type point_difference_type;
-
- // Find min/max ranges
- 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, 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);
- 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
- BGL_FORALL_VERTICES_T(v, g, Graph) {
- point_difference_type relative_loc = topology.difference(get(position, v), old_origin);
- relative_loc = (relative_loc / old_size) * new_size;
- put(position, v, topology.adjust(new_origin, relative_loc));
- }
+ return grid_force_pairs< Topology, PositionMap >(topology, position, g);
}
-namespace detail {
- template<typename Topology, typename PropMap, typename Vertex>
- void
- maybe_jitter_point(const Topology& topology,
- const PropMap& pm, Vertex v,
- const typename Topology::point_type& p2)
- {
- double too_close = topology.norm(topology.extent()) / 10000.;
- if (topology.distance(get(pm, v), p2) < too_close) {
- put(pm, v,
- topology.move_position_toward(get(pm, v), 1./200,
- topology.random_point()));
- }
- }
+template < typename Graph, typename PositionMap, typename Topology >
+void 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;
- 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 Topology::point_type Point;
- typedef typename Topology::point_difference_type PointDiff;
+ typedef typename Topology::point_difference_type point_difference_type;
+
+ // Find min/max ranges
+ 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, get(position, v));
+ max_point = topology.pointwise_max(max_point, get(position, v));
+ }
- fr_apply_force(const Topology& topology,
- const PositionMap& position,
- const DisplacementMap& displacement,
- RepulsiveForce repulsive_force, double k, const Graph& g)
- : topology(topology), position(position), displacement(displacement),
- repulsive_force(repulsive_force), k(k), g(g)
- { }
+ 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);
- void operator()(vertex_descriptor u, vertex_descriptor v)
+ // Scale to bounding box provided
+ BGL_FORALL_VERTICES_T(v, g, Graph)
{
- 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, get(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) {
- dispv[i] += 0.01;
- }
- } else {
- double fr = repulsive_force(u, v, k, dist, g);
- dispv += (fr / dist) *
- topology.difference(get(position, v), get(position, u));
+ point_difference_type relative_loc
+ = topology.difference(get(position, v), old_origin);
+ relative_loc = (relative_loc / old_size) * new_size;
+ put(position, v, topology.adjust(new_origin, relative_loc));
+ }
+}
+
+namespace detail
+{
+ template < typename Topology, typename PropMap, typename Vertex >
+ void maybe_jitter_point(const Topology& topology, const PropMap& pm,
+ Vertex v, const typename Topology::point_type& p2)
+ {
+ double too_close = topology.norm(topology.extent()) / 10000.;
+ if (topology.distance(get(pm, v), p2) < too_close)
+ {
+ put(pm, v,
+ topology.move_position_toward(
+ get(pm, v), 1. / 200, topology.random_point()));
}
- put(displacement, v, dispv);
- }
}
- private:
- const Topology& topology;
- PositionMap position;
- DisplacementMap displacement;
- RepulsiveForce repulsive_force;
- double k;
- const Graph& g;
- };
+ 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 Topology::point_type Point;
+ typedef typename Topology::point_difference_type PointDiff;
+
+ fr_apply_force(const Topology& topology, const PositionMap& position,
+ const DisplacementMap& displacement, RepulsiveForce repulsive_force,
+ double k, const Graph& g)
+ : topology(topology)
+ , position(position)
+ , displacement(displacement)
+ , repulsive_force(repulsive_force)
+ , k(k)
+ , g(g)
+ {
+ }
+
+ void operator()(vertex_descriptor u, vertex_descriptor v)
+ {
+ 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, get(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)
+ {
+ dispv[i] += 0.01;
+ }
+ }
+ else
+ {
+ double fr = repulsive_force(u, v, k, dist, g);
+ dispv += (fr / dist)
+ * topology.difference(
+ get(position, v), get(position, u));
+ }
+ put(displacement, v, dispv);
+ }
+ }
+
+ private:
+ const Topology& topology;
+ PositionMap position;
+ DisplacementMap displacement;
+ RepulsiveForce repulsive_force;
+ double k;
+ const Graph& g;
+ };
} // end namespace detail
-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,
- const Topology& topology,
- AttractiveForce attractive_force,
- RepulsiveForce repulsive_force,
- ForcePairs force_pairs,
- Cooling cool,
- DisplacementMap displacement)
+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, const Topology& topology,
+ AttractiveForce attractive_force, RepulsiveForce repulsive_force,
+ ForcePairs force_pairs, Cooling cool, DisplacementMap displacement)
{
- 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;
-
- double volume = topology.volume(topology.extent());
-
- // assume positions are initialized randomly
- double k = pow(volume / num_vertices(g), 1. / (double)(Topology::point_difference_type::dimensions));
-
- detail::fr_apply_force<Topology, PositionMap, DisplacementMap,
- RepulsiveForce, Graph>
- apply_force(topology, position, displacement, repulsive_force, k, g);
-
- do {
- // Calculate repulsive forces
- vertex_iterator v, v_end;
- for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v)
- put(displacement, *v, typename Topology::point_difference_type());
- force_pairs(g, apply_force);
-
- // Calculate attractive forces
- edge_iterator e, e_end;
- for (boost::tie(e, e_end) = edges(g); e != e_end; ++e) {
- vertex_descriptor v = source(*e, g);
- vertex_descriptor u = target(*e, g);
-
- // 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, get(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);
-
- put(displacement, v, get(displacement, v) - (fa / dist) * delta);
- put(displacement, u, get(displacement, u) + (fa / dist) * delta);
- }
+ 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;
- if (double temp = cool()) {
- // Update positions
- BGL_FORALL_VERTICES_T (v, g, Graph) {
- BOOST_USING_STD_MIN();
- BOOST_USING_STD_MAX();
- 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;
- }
- } while (true);
+ double volume = topology.volume(topology.extent());
+
+ // assume positions are initialized randomly
+ double k = pow(volume / num_vertices(g),
+ 1. / (double)(Topology::point_difference_type::dimensions));
+
+ detail::fr_apply_force< Topology, PositionMap, DisplacementMap,
+ RepulsiveForce, Graph >
+ apply_force(topology, position, displacement, repulsive_force, k, g);
+
+ do
+ {
+ // Calculate repulsive forces
+ vertex_iterator v, v_end;
+ for (boost::tie(v, v_end) = vertices(g); v != v_end; ++v)
+ put(displacement, *v, typename Topology::point_difference_type());
+ force_pairs(g, apply_force);
+
+ // Calculate attractive forces
+ edge_iterator e, e_end;
+ for (boost::tie(e, e_end) = edges(g); e != e_end; ++e)
+ {
+ vertex_descriptor v = source(*e, g);
+ vertex_descriptor u = target(*e, g);
+
+ // 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, get(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);
+
+ put(displacement, v, get(displacement, v) - (fa / dist) * delta);
+ put(displacement, u, get(displacement, u) + (fa / dist) * delta);
+ }
+
+ if (double temp = cool())
+ {
+ // Update positions
+ BGL_FORALL_VERTICES_T(v, g, Graph)
+ {
+ BOOST_USING_STD_MIN();
+ BOOST_USING_STD_MAX();
+ 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;
+ }
+ } while (true);
}
-namespace detail {
- template<typename DisplacementMap>
- struct fr_force_directed_layout
- {
- 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,
- const Topology& topology,
- AttractiveForce attractive_force,
- RepulsiveForce repulsive_force,
- ForcePairs force_pairs,
- Cooling cool,
- DisplacementMap displacement,
- const bgl_named_params<Param, Tag, Rest>&)
+namespace detail
+{
+ template < typename DisplacementMap > struct fr_force_directed_layout
{
- fruchterman_reingold_force_directed_layout
- (g, position, topology, attractive_force, repulsive_force,
- force_pairs, cool, displacement);
- }
- };
-
- template<>
- struct fr_force_directed_layout<param_not_found>
- {
- 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,
- const Topology& topology,
- AttractiveForce attractive_force,
- RepulsiveForce repulsive_force,
- ForcePairs force_pairs,
- Cooling cool,
- param_not_found,
- const bgl_named_params<Param, Tag, Rest>& params)
+ 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,
+ const Topology& topology, AttractiveForce attractive_force,
+ RepulsiveForce repulsive_force, ForcePairs force_pairs,
+ Cooling cool, DisplacementMap displacement,
+ const bgl_named_params< Param, Tag, Rest >&)
+ {
+ fruchterman_reingold_force_directed_layout(g, position, topology,
+ attractive_force, repulsive_force, force_pairs, cool,
+ displacement);
+ }
+ };
+
+ template <> struct fr_force_directed_layout< param_not_found >
{
- typedef typename Topology::point_difference_type PointDiff;
- std::vector<PointDiff> displacements(num_vertices(g));
- fruchterman_reingold_force_directed_layout
- (g, position, topology, attractive_force, repulsive_force,
- force_pairs, cool,
- make_iterator_property_map
- (displacements.begin(),
- choose_const_pmap(get_param(params, vertex_index), g,
- vertex_index),
- PointDiff()));
- }
- };
+ 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,
+ const Topology& topology, AttractiveForce attractive_force,
+ RepulsiveForce repulsive_force, ForcePairs force_pairs,
+ Cooling cool, param_not_found,
+ const bgl_named_params< Param, Tag, Rest >& params)
+ {
+ typedef typename Topology::point_difference_type PointDiff;
+ std::vector< PointDiff > displacements(num_vertices(g));
+ fruchterman_reingold_force_directed_layout(g, position, topology,
+ attractive_force, repulsive_force, force_pairs, cool,
+ make_iterator_property_map(displacements.begin(),
+ choose_const_pmap(
+ get_param(params, vertex_index), g, vertex_index),
+ PointDiff()));
+ }
+ };
} // end namespace detail
-template<typename Topology, typename Graph, typename PositionMap, typename Param,
- typename Tag, typename Rest>
-void
-fruchterman_reingold_force_directed_layout
- (const Graph& g,
- PositionMap position,
- const Topology& topology,
- const bgl_named_params<Param, Tag, Rest>& params)
+template < typename Topology, typename Graph, typename PositionMap,
+ typename Param, typename Tag, typename Rest >
+void fruchterman_reingold_force_directed_layout(const Graph& g,
+ PositionMap position, const Topology& topology,
+ const bgl_named_params< Param, Tag, Rest >& params)
{
- typedef typename get_param_type<vertex_displacement_t, bgl_named_params<Param,Tag,Rest> >::type D;
-
- detail::fr_force_directed_layout<D>::run
- (g, position, topology,
- 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(topology, position, g)),
- choose_param(get_param(params, cooling_t()),
- linear_cooling<double>(100)),
- get_param(params, vertex_displacement_t()),
- params);
+ typedef typename get_param_type< vertex_displacement_t,
+ bgl_named_params< Param, Tag, Rest > >::type D;
+
+ detail::fr_force_directed_layout< D >::run(g, position, topology,
+ 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(topology, position, g)),
+ choose_param(
+ get_param(params, cooling_t()), linear_cooling< double >(100)),
+ get_param(params, vertex_displacement_t()), params);
}
-template<typename Topology, typename Graph, typename PositionMap>
-void
-fruchterman_reingold_force_directed_layout
- (const Graph& g,
- PositionMap position,
- const Topology& topology)
+template < typename Topology, typename Graph, typename PositionMap >
+void fruchterman_reingold_force_directed_layout(
+ const Graph& g, PositionMap position, const Topology& topology)
{
- fruchterman_reingold_force_directed_layout
- (g, position, topology,
- attractive_force(square_distance_attractive_force()));
+ fruchterman_reingold_force_directed_layout(g, position, topology,
+ attractive_force(square_distance_attractive_force()));
}
} // end namespace boost
-#include BOOST_GRAPH_MPI_INCLUDE(<boost/graph/distributed/fruchterman_reingold.hpp>)
+#include BOOST_GRAPH_MPI_INCLUDE(< boost / graph / distributed / fruchterman_reingold.hpp >)
#endif // BOOST_GRAPH_FRUCHTERMAN_REINGOLD_FORCE_DIRECTED_LAYOUT_HPP