// Copyright (C) 2005-2006 The Trustees of Indiana University. | |
// Use, modification and distribution is subject to 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: Douglas Gregor | |
// Andrew Lumsdaine | |
#ifndef BOOST_GRAPH_DISTRIBUTED_FRUCHTERMAN_REINGOLD_HPP | |
#define BOOST_GRAPH_DISTRIBUTED_FRUCHTERMAN_REINGOLD_HPP | |
#ifndef BOOST_GRAPH_USE_MPI | |
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included" | |
#endif | |
#include <boost/graph/fruchterman_reingold.hpp> | |
namespace boost { namespace graph { namespace distributed { | |
class simple_tiling | |
{ | |
public: | |
simple_tiling(int columns, int rows, bool flip = true) | |
: columns(columns), rows(rows), flip(flip) | |
{ | |
} | |
// Convert from a position (x, y) in the tiled display into a | |
// processor ID number | |
int operator()(int x, int y) const | |
{ | |
return flip? (rows - y - 1) * columns + x : y * columns + x; | |
} | |
// Convert from a process ID to a position (x, y) in the tiled | |
// display | |
std::pair<int, int> operator()(int id) | |
{ | |
int my_col = id % columns; | |
int my_row = flip? rows - (id / columns) - 1 : id / columns; | |
return std::make_pair(my_col, my_row); | |
} | |
int columns, rows; | |
private: | |
bool flip; | |
}; | |
// Force pairs function object that does nothing | |
struct no_force_pairs | |
{ | |
template<typename Graph, typename ApplyForce> | |
void operator()(const Graph&, const ApplyForce&) | |
{ | |
} | |
}; | |
// Computes force pairs in the distributed case. | |
template<typename PositionMap, typename DisplacementMap, typename LocalForces, | |
typename NonLocalForces = no_force_pairs> | |
class distributed_force_pairs_proxy | |
{ | |
public: | |
distributed_force_pairs_proxy(const PositionMap& position, | |
const DisplacementMap& displacement, | |
const LocalForces& local_forces, | |
const NonLocalForces& nonlocal_forces = NonLocalForces()) | |
: position(position), displacement(displacement), | |
local_forces(local_forces), nonlocal_forces(nonlocal_forces) | |
{ | |
} | |
template<typename Graph, typename ApplyForce> | |
void operator()(const Graph& g, ApplyForce apply_force) | |
{ | |
// Flush remote displacements | |
displacement.flush(); | |
// Receive updated positions for all of our neighbors | |
synchronize(position); | |
// Reset remote displacements | |
displacement.reset(); | |
// Compute local repulsive forces | |
local_forces(g, apply_force); | |
// Compute neighbor repulsive forces | |
nonlocal_forces(g, apply_force); | |
} | |
protected: | |
PositionMap position; | |
DisplacementMap displacement; | |
LocalForces local_forces; | |
NonLocalForces nonlocal_forces; | |
}; | |
template<typename PositionMap, typename DisplacementMap, typename LocalForces> | |
inline | |
distributed_force_pairs_proxy<PositionMap, DisplacementMap, LocalForces> | |
make_distributed_force_pairs(const PositionMap& position, | |
const DisplacementMap& displacement, | |
const LocalForces& local_forces) | |
{ | |
typedef | |
distributed_force_pairs_proxy<PositionMap, DisplacementMap, LocalForces> | |
result_type; | |
return result_type(position, displacement, local_forces); | |
} | |
template<typename PositionMap, typename DisplacementMap, typename LocalForces, | |
typename NonLocalForces> | |
inline | |
distributed_force_pairs_proxy<PositionMap, DisplacementMap, LocalForces, | |
NonLocalForces> | |
make_distributed_force_pairs(const PositionMap& position, | |
const DisplacementMap& displacement, | |
const LocalForces& local_forces, | |
const NonLocalForces& nonlocal_forces) | |
{ | |
typedef | |
distributed_force_pairs_proxy<PositionMap, DisplacementMap, LocalForces, | |
NonLocalForces> | |
result_type; | |
return result_type(position, displacement, local_forces, nonlocal_forces); | |
} | |
// Compute nonlocal force pairs based on the shared borders with | |
// adjacent tiles. | |
template<typename PositionMap> | |
class neighboring_tiles_force_pairs | |
{ | |
public: | |
typedef typename property_traits<PositionMap>::value_type Point; | |
typedef typename point_traits<Point>::component_type Dim; | |
enum bucket_position { left, top, right, bottom, end_position }; | |
neighboring_tiles_force_pairs(PositionMap position, Point origin, | |
Point extent, simple_tiling tiling) | |
: position(position), origin(origin), extent(extent), tiling(tiling) | |
{ | |
} | |
template<typename Graph, typename ApplyForce> | |
void operator()(const Graph& g, ApplyForce apply_force) | |
{ | |
// TBD: Do this some smarter way | |
if (tiling.columns == 1 && tiling.rows == 1) | |
return; | |
typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; | |
#ifndef BOOST_NO_STDC_NAMESPACE | |
using std::sqrt; | |
#endif // BOOST_NO_STDC_NAMESPACE | |
// TBD: num_vertices(g) should be the global number of vertices? | |
Dim two_k = Dim(2) * sqrt(extent[0] * extent[1] / num_vertices(g)); | |
std::vector<vertex_descriptor> my_vertices[4]; | |
std::vector<vertex_descriptor> neighbor_vertices[4]; | |
// Compute cutoff positions | |
Dim cutoffs[4]; | |
cutoffs[left] = origin[0] + two_k; | |
cutoffs[top] = origin[1] + two_k; | |
cutoffs[right] = origin[0] + extent[0] - two_k; | |
cutoffs[bottom] = origin[1] + extent[1] - two_k; | |
// Compute neighbors | |
typename PositionMap::process_group_type pg = position.process_group(); | |
std::pair<int, int> my_tile = tiling(process_id(pg)); | |
int neighbors[4] = { -1, -1, -1, -1 } ; | |
if (my_tile.first > 0) | |
neighbors[left] = tiling(my_tile.first - 1, my_tile.second); | |
if (my_tile.second > 0) | |
neighbors[top] = tiling(my_tile.first, my_tile.second - 1); | |
if (my_tile.first < tiling.columns - 1) | |
neighbors[right] = tiling(my_tile.first + 1, my_tile.second); | |
if (my_tile.second < tiling.rows - 1) | |
neighbors[bottom] = tiling(my_tile.first, my_tile.second + 1); | |
// Sort vertices along the edges into buckets | |
BGL_FORALL_VERTICES_T(v, g, Graph) { | |
if (position[v][0] <= cutoffs[left]) my_vertices[left].push_back(v); | |
if (position[v][1] <= cutoffs[top]) my_vertices[top].push_back(v); | |
if (position[v][0] >= cutoffs[right]) my_vertices[right].push_back(v); | |
if (position[v][1] >= cutoffs[bottom]) my_vertices[bottom].push_back(v); | |
} | |
// Send vertices to neighbors, and gather our neighbors' vertices | |
bucket_position pos; | |
for (pos = left; pos < end_position; pos = bucket_position(pos + 1)) { | |
if (neighbors[pos] != -1) { | |
send(pg, neighbors[pos], 0, my_vertices[pos].size()); | |
if (!my_vertices[pos].empty()) | |
send(pg, neighbors[pos], 1, | |
&my_vertices[pos].front(), my_vertices[pos].size()); | |
} | |
} | |
// Pass messages around | |
synchronize(pg); | |
// Receive neighboring vertices | |
for (pos = left; pos < end_position; pos = bucket_position(pos + 1)) { | |
if (neighbors[pos] != -1) { | |
std::size_t incoming_vertices; | |
receive(pg, neighbors[pos], 0, incoming_vertices); | |
if (incoming_vertices) { | |
neighbor_vertices[pos].resize(incoming_vertices); | |
receive(pg, neighbors[pos], 1, &neighbor_vertices[pos].front(), | |
incoming_vertices); | |
} | |
} | |
} | |
// For each neighboring vertex, we need to get its current position | |
for (pos = left; pos < end_position; pos = bucket_position(pos + 1)) | |
for (typename std::vector<vertex_descriptor>::iterator i = | |
neighbor_vertices[pos].begin(); | |
i != neighbor_vertices[pos].end(); | |
++i) | |
request(position, *i); | |
synchronize(position); | |
// Apply forces in adjacent bins. This is O(n^2) in the worst | |
// case. Oh well. | |
for (pos = left; pos < end_position; pos = bucket_position(pos + 1)) { | |
for (typename std::vector<vertex_descriptor>::iterator i = | |
my_vertices[pos].begin(); | |
i != my_vertices[pos].end(); | |
++i) | |
for (typename std::vector<vertex_descriptor>::iterator j = | |
neighbor_vertices[pos].begin(); | |
j != neighbor_vertices[pos].end(); | |
++j) | |
apply_force(*i, *j); | |
} | |
} | |
protected: | |
PositionMap position; | |
Point origin; | |
Point extent; | |
simple_tiling tiling; | |
}; | |
template<typename PositionMap> | |
inline neighboring_tiles_force_pairs<PositionMap> | |
make_neighboring_tiles_force_pairs | |
(PositionMap position, | |
typename property_traits<PositionMap>::value_type origin, | |
typename property_traits<PositionMap>::value_type extent, | |
simple_tiling tiling) | |
{ | |
return neighboring_tiles_force_pairs<PositionMap>(position, origin, extent, | |
tiling); | |
} | |
template<typename DisplacementMap, typename Cooling> | |
class distributed_cooling_proxy | |
{ | |
public: | |
typedef typename Cooling::result_type result_type; | |
distributed_cooling_proxy(const DisplacementMap& displacement, | |
const Cooling& cooling) | |
: displacement(displacement), cooling(cooling) | |
{ | |
} | |
result_type operator()() | |
{ | |
// Accumulate displacements computed on each processor | |
synchronize(displacement.data->process_group); | |
// Allow the underlying cooling to occur | |
return cooling(); | |
} | |
protected: | |
DisplacementMap displacement; | |
Cooling cooling; | |
}; | |
template<typename DisplacementMap, typename Cooling> | |
inline distributed_cooling_proxy<DisplacementMap, Cooling> | |
make_distributed_cooling(const DisplacementMap& displacement, | |
const Cooling& cooling) | |
{ | |
typedef distributed_cooling_proxy<DisplacementMap, Cooling> result_type; | |
return result_type(displacement, cooling); | |
} | |
template<typename Point> | |
struct point_accumulating_reducer { | |
BOOST_STATIC_CONSTANT(bool, non_default_resolver = true); | |
template<typename K> | |
Point operator()(const K&) const { return Point(); } | |
template<typename K> | |
Point operator()(const K&, const Point& p1, const Point& p2) const | |
{ return Point(p1[0] + p2[0], p1[1] + p2[1]); } | |
}; | |
template<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, | |
AttractiveForce attractive_force, | |
RepulsiveForce repulsive_force, | |
ForcePairs force_pairs, | |
Cooling cool, | |
DisplacementMap displacement) | |
{ | |
typedef typename property_traits<PositionMap>::value_type Point; | |
// Reduction in the displacement map involves summing the forces | |
displacement.set_reduce(point_accumulating_reducer<Point>()); | |
// We need to track the positions of all of our neighbors | |
BGL_FORALL_VERTICES_T(u, g, Graph) | |
BGL_FORALL_ADJ_T(u, v, g, Graph) | |
request(position, v); | |
// Invoke the "sequential" Fruchterman-Reingold implementation | |
boost::fruchterman_reingold_force_directed_layout | |
(g, position, origin, extent, | |
attractive_force, repulsive_force, | |
make_distributed_force_pairs(position, displacement, force_pairs), | |
make_distributed_cooling(displacement, cool), | |
displacement); | |
} | |
template<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, | |
AttractiveForce attractive_force, | |
RepulsiveForce repulsive_force, | |
ForcePairs force_pairs, | |
Cooling cool, | |
DisplacementMap displacement, | |
simple_tiling tiling) | |
{ | |
typedef typename property_traits<PositionMap>::value_type Point; | |
// Reduction in the displacement map involves summing the forces | |
displacement.set_reduce(point_accumulating_reducer<Point>()); | |
// We need to track the positions of all of our neighbors | |
BGL_FORALL_VERTICES_T(u, g, Graph) | |
BGL_FORALL_ADJ_T(u, v, g, Graph) | |
request(position, v); | |
// Invoke the "sequential" Fruchterman-Reingold implementation | |
boost::fruchterman_reingold_force_directed_layout | |
(g, position, origin, extent, | |
attractive_force, repulsive_force, | |
make_distributed_force_pairs | |
(position, displacement, force_pairs, | |
make_neighboring_tiles_force_pairs(position, origin, extent, tiling)), | |
make_distributed_cooling(displacement, cool), | |
displacement); | |
} | |
} } } // end namespace boost::graph::distributed | |
#endif // BOOST_GRAPH_DISTRIBUTED_FRUCHTERMAN_REINGOLD_HPP |