graph/distributed/fruchterman_reingold.hpp

0001 // Copyright (C) 2005-2006 The Trustees of Indiana University.
0002
0003 // Use, modification and distribution is subject to the Boost Software
0004 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
0005 // http://www.boost.org/LICENSE_1_0.txt)
0006
0007 //  Authors: Douglas Gregor
0008 //           Andrew Lumsdaine
0009 #ifndef BOOST_GRAPH_DISTRIBUTED_FRUCHTERMAN_REINGOLD_HPP
0010 #define BOOST_GRAPH_DISTRIBUTED_FRUCHTERMAN_REINGOLD_HPP
0011
0012 #ifndef BOOST_GRAPH_USE_MPI
0013 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
0014 #endif
0015
0016 #include <boost/graph/fruchterman_reingold.hpp>
0017
0018 namespace boost { namespace graph { namespace distributed {
0019
0020 class simple_tiling
0021 {
0022  public:
0023   simple_tiling(int columns, int rows, bool flip = true)
0024     : columns(columns), rows(rows), flip(flip)
0025   {
0026   }
0027
0028   // Convert from a position (x, y) in the tiled display into a
0029   // processor ID number
0030   int operator()(int x, int y) const
0031   {
0032     return flip? (rows - y - 1) * columns + x : y * columns + x;
0033   }
0034
0035   // Convert from a process ID to a position (x, y) in the tiled
0036   // display
0037   std::pair<int, int> operator()(int id)
0038   {
0039     int my_col = id % columns;
0040     int my_row = flip? rows - (id / columns) - 1 : id / columns;
0041     return std::make_pair(my_col, my_row);
0042   }
0043
0044   int columns, rows;
0045
0046  private:
0047   bool flip;
0048 };
0049
0050 // Force pairs function object that does nothing
0051 struct no_force_pairs
0052 {
0053   template<typename Graph, typename ApplyForce>
0054   void operator()(const Graph&, const ApplyForce&)
0055   {
0056   }
0057 };
0058
0059 // Computes force pairs in the distributed case.
0060 template<typename PositionMap, typename DisplacementMap, typename LocalForces,
0061          typename NonLocalForces = no_force_pairs>
0062 class distributed_force_pairs_proxy
0063 {
0064  public:
0065   distributed_force_pairs_proxy(const PositionMap& position,
0066                                 const DisplacementMap& displacement,
0067                                 const LocalForces& local_forces,
0068                                 const NonLocalForces& nonlocal_forces = NonLocalForces())
0069     : position(position), displacement(displacement),
0070       local_forces(local_forces), nonlocal_forces(nonlocal_forces)
0071   {
0072   }
0073
0074   template<typename Graph, typename ApplyForce>
0075   void operator()(const Graph& g, ApplyForce apply_force)
0076   {
0077     // Flush remote displacements
0078     displacement.flush();
0079
0080     // Receive updated positions for all of our neighbors
0081     synchronize(position);
0082
0083     // Reset remote displacements
0084     displacement.reset();
0085
0086     // Compute local repulsive forces
0087     local_forces(g, apply_force);
0088
0089     // Compute neighbor repulsive forces
0090     nonlocal_forces(g, apply_force);
0091   }
0092
0093  protected:
0094   PositionMap position;
0095   DisplacementMap displacement;
0096   LocalForces local_forces;
0097   NonLocalForces nonlocal_forces;
0098 };
0099
0100 template<typename PositionMap, typename DisplacementMap, typename LocalForces>
0101 inline
0102 distributed_force_pairs_proxy<PositionMap, DisplacementMap, LocalForces>
0103 make_distributed_force_pairs(const PositionMap& position,
0104                              const DisplacementMap& displacement,
0105                              const LocalForces& local_forces)
0106 {
0107   typedef
0108     distributed_force_pairs_proxy<PositionMap, DisplacementMap, LocalForces>
0109     result_type;
0110   return result_type(position, displacement, local_forces);
0111 }
0112
0113 template<typename PositionMap, typename DisplacementMap, typename LocalForces,
0114          typename NonLocalForces>
0115 inline
0116 distributed_force_pairs_proxy<PositionMap, DisplacementMap, LocalForces,
0117                               NonLocalForces>
0118 make_distributed_force_pairs(const PositionMap& position,
0119                              const DisplacementMap& displacement,
0120                              const LocalForces& local_forces,
0121                              const NonLocalForces& nonlocal_forces)
0122 {
0123   typedef
0124     distributed_force_pairs_proxy<PositionMap, DisplacementMap, LocalForces,
0125                                   NonLocalForces>
0126       result_type;
0127   return result_type(position, displacement, local_forces, nonlocal_forces);
0128 }
0129
0130 // Compute nonlocal force pairs based on the shared borders with
0131 // adjacent tiles.
0132 template<typename PositionMap>
0133 class neighboring_tiles_force_pairs
0134 {
0135  public:
0136   typedef typename property_traits<PositionMap>::value_type Point;
0137   typedef typename point_traits<Point>::component_type Dim;
0138
0139   enum bucket_position { left, top, right, bottom, end_position };
0140
0141   neighboring_tiles_force_pairs(PositionMap position, Point origin,
0142                                 Point extent, simple_tiling tiling)
0143     : position(position), origin(origin), extent(extent), tiling(tiling)
0144   {
0145   }
0146
0147   template<typename Graph, typename ApplyForce>
0148   void operator()(const Graph& g, ApplyForce apply_force)
0149   {
0150     // TBD: Do this some smarter way
0151     if (tiling.columns == 1 && tiling.rows == 1)
0152       return;
0153
0154     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
0155 #ifndef BOOST_NO_STDC_NAMESPACE
0156     using std::sqrt;
0157 #endif // BOOST_NO_STDC_NAMESPACE
0158
0159     // TBD: num_vertices(g) should be the global number of vertices?
0160     Dim two_k = Dim(2) * sqrt(extent[0] * extent[1] / num_vertices(g));
0161
0162     std::vector<vertex_descriptor> my_vertices[4];
0163     std::vector<vertex_descriptor> neighbor_vertices[4];
0164
0165     // Compute cutoff positions
0166     Dim cutoffs[4];
0167     cutoffs[left] = origin[0] + two_k;
0168     cutoffs[top] = origin[1] + two_k;
0169     cutoffs[right] = origin[0] + extent[0] - two_k;
0170     cutoffs[bottom] = origin[1] + extent[1] - two_k;
0171
0172     // Compute neighbors
0173     typename PositionMap::process_group_type pg = position.process_group();
0174     std::pair<int, int> my_tile = tiling(process_id(pg));
0175     int neighbors[4] = { -1, -1, -1, -1 } ;
0176     if (my_tile.first > 0)
0177       neighbors[left] = tiling(my_tile.first - 1, my_tile.second);
0178     if (my_tile.second > 0)
0179       neighbors[top] = tiling(my_tile.first, my_tile.second - 1);
0180     if (my_tile.first < tiling.columns - 1)
0181       neighbors[right] = tiling(my_tile.first + 1, my_tile.second);
0182     if (my_tile.second < tiling.rows - 1)
0183       neighbors[bottom] = tiling(my_tile.first, my_tile.second + 1);
0184
0185     // Sort vertices along the edges into buckets
0186     BGL_FORALL_VERTICES_T(v, g, Graph) {
0187       if (position[v][0] <= cutoffs[left]) my_vertices[left].push_back(v);
0188       if (position[v][1] <= cutoffs[top]) my_vertices[top].push_back(v);
0189       if (position[v][0] >= cutoffs[right]) my_vertices[right].push_back(v);
0190       if (position[v][1] >= cutoffs[bottom]) my_vertices[bottom].push_back(v);
0191     }
0192
0193     // Send vertices to neighbors, and gather our neighbors' vertices
0194     bucket_position pos;
0195     for (pos = left; pos < end_position; pos = bucket_position(pos + 1)) {
0196       if (neighbors[pos] != -1) {
0197         send(pg, neighbors[pos], 0, my_vertices[pos].size());
0198         if (!my_vertices[pos].empty())
0199           send(pg, neighbors[pos], 1,
0200                &my_vertices[pos].front(), my_vertices[pos].size());
0201       }
0202     }
0203
0204     // Pass messages around
0205     synchronize(pg);
0206
0207     // Receive neighboring vertices
0208     for (pos = left; pos < end_position; pos = bucket_position(pos + 1)) {
0209       if (neighbors[pos] != -1) {
0210         std::size_t incoming_vertices;
0211         receive(pg, neighbors[pos], 0, incoming_vertices);
0212
0213         if (incoming_vertices) {
0214           neighbor_vertices[pos].resize(incoming_vertices);
0215           receive(pg, neighbors[pos], 1, &neighbor_vertices[pos].front(),
0216                   incoming_vertices);
0217         }
0218       }
0219     }
0220
0221     // For each neighboring vertex, we need to get its current position
0222     for (pos = left; pos < end_position; pos = bucket_position(pos + 1))
0223       for (typename std::vector<vertex_descriptor>::iterator i =
0224              neighbor_vertices[pos].begin();
0225            i != neighbor_vertices[pos].end();
0226            ++i)
0227         request(position, *i);
0228     synchronize(position);
0229
0230     // Apply forces in adjacent bins. This is O(n^2) in the worst
0231     // case. Oh well.
0232     for (pos = left; pos < end_position; pos = bucket_position(pos + 1)) {
0233       for (typename std::vector<vertex_descriptor>::iterator i =
0234              my_vertices[pos].begin();
0235            i != my_vertices[pos].end();
0236            ++i)
0237         for (typename std::vector<vertex_descriptor>::iterator j =
0238                neighbor_vertices[pos].begin();
0239              j != neighbor_vertices[pos].end();
0240              ++j)
0241           apply_force(*i, *j);
0242     }
0243   }
0244
0245  protected:
0246   PositionMap position;
0247   Point origin;
0248   Point extent;
0249   simple_tiling tiling;
0250 };
0251
0252 template<typename PositionMap>
0253 inline neighboring_tiles_force_pairs<PositionMap>
0254 make_neighboring_tiles_force_pairs
0255  (PositionMap position,
0256   typename property_traits<PositionMap>::value_type origin,
0257   typename property_traits<PositionMap>::value_type extent,
0258   simple_tiling tiling)
0259 {
0260   return neighboring_tiles_force_pairs<PositionMap>(position, origin, extent,
0261                                                     tiling);
0262 }
0263
0264 template<typename DisplacementMap, typename Cooling>
0265 class distributed_cooling_proxy
0266 {
0267  public:
0268   typedef typename Cooling::result_type result_type;
0269
0270   distributed_cooling_proxy(const DisplacementMap& displacement,
0271                             const Cooling& cooling)
0272     : displacement(displacement), cooling(cooling)
0273   {
0274   }
0275
0276   result_type operator()()
0277   {
0278     // Accumulate displacements computed on each processor
0279     synchronize(displacement.data->process_group);
0280
0281     // Allow the underlying cooling to occur
0282     return cooling();
0283   }
0284
0285  protected:
0286   DisplacementMap displacement;
0287   Cooling cooling;
0288 };
0289
0290 template<typename DisplacementMap, typename Cooling>
0291 inline distributed_cooling_proxy<DisplacementMap, Cooling>
0292 make_distributed_cooling(const DisplacementMap& displacement,
0293                          const Cooling& cooling)
0294 {
0295   typedef distributed_cooling_proxy<DisplacementMap, Cooling> result_type;
0296   return result_type(displacement, cooling);
0297 }
0298
0299 template<typename Point>
0300 struct point_accumulating_reducer {
0301   BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);
0302
0303   template<typename K>
0304   Point operator()(const K&) const { return Point(); }
0305
0306   template<typename K>
0307   Point operator()(const K&, const Point& p1, const Point& p2) const
0308   { return Point(p1[0] + p2[0], p1[1] + p2[1]); }
0309 };
0310
0311 template<typename Graph, typename PositionMap,
0312          typename AttractiveForce, typename RepulsiveForce,
0313          typename ForcePairs, typename Cooling, typename DisplacementMap>
0314 void
0315 fruchterman_reingold_force_directed_layout
0316  (const Graph&    g,
0317   PositionMap     position,
0318   typename property_traits<PositionMap>::value_type const& origin,
0319   typename property_traits<PositionMap>::value_type const& extent,
0320   AttractiveForce attractive_force,
0321   RepulsiveForce  repulsive_force,
0322   ForcePairs      force_pairs,
0323   Cooling         cool,
0324   DisplacementMap displacement)
0325 {
0326   typedef typename property_traits<PositionMap>::value_type Point;
0327
0328   // Reduction in the displacement map involves summing the forces
0329   displacement.set_reduce(point_accumulating_reducer<Point>());
0330
0331   // We need to track the positions of all of our neighbors
0332   BGL_FORALL_VERTICES_T(u, g, Graph)
0333     BGL_FORALL_ADJ_T(u, v, g, Graph)
0334       request(position, v);
0335
0336   // Invoke the "sequential" Fruchterman-Reingold implementation
0337   boost::fruchterman_reingold_force_directed_layout
0338     (g, position, origin, extent,
0339      attractive_force, repulsive_force,
0340      make_distributed_force_pairs(position, displacement, force_pairs),
0341      make_distributed_cooling(displacement, cool),
0342      displacement);
0343 }
0344
0345 template<typename Graph, typename PositionMap,
0346          typename AttractiveForce, typename RepulsiveForce,
0347          typename ForcePairs, typename Cooling, typename DisplacementMap>
0348 void
0349 fruchterman_reingold_force_directed_layout
0350  (const Graph&    g,
0351   PositionMap     position,
0352   typename property_traits<PositionMap>::value_type const& origin,
0353   typename property_traits<PositionMap>::value_type const& extent,
0354   AttractiveForce attractive_force,
0355   RepulsiveForce  repulsive_force,
0356   ForcePairs      force_pairs,
0357   Cooling         cool,
0358   DisplacementMap displacement,
0359   simple_tiling   tiling)
0360 {
0361   typedef typename property_traits<PositionMap>::value_type Point;
0362
0363   // Reduction in the displacement map involves summing the forces
0364   displacement.set_reduce(point_accumulating_reducer<Point>());
0365
0366   // We need to track the positions of all of our neighbors
0367   BGL_FORALL_VERTICES_T(u, g, Graph)
0368     BGL_FORALL_ADJ_T(u, v, g, Graph)
0369       request(position, v);
0370
0371   // Invoke the "sequential" Fruchterman-Reingold implementation
0372   boost::fruchterman_reingold_force_directed_layout
0373     (g, position, origin, extent,
0374      attractive_force, repulsive_force,
0375      make_distributed_force_pairs
0376       (position, displacement, force_pairs,
0377        make_neighboring_tiles_force_pairs(position, origin, extent, tiling)),
0378      make_distributed_cooling(displacement, cool),
0379      displacement);
0380 }
0381
0382 } } } // end namespace boost::graph::distributed
0383
0384 #endif // BOOST_GRAPH_DISTRIBUTED_FRUCHTERMAN_REINGOLD_HPP