ceph/src/boost/libs/graph_parallel/include/boost/graph/distributed/fruchterman_reingold.hpp

   1 // Copyright (C) 2005-2006 The Trustees of Indiana University.
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Douglas Gregor
   8 //           Andrew Lumsdaine
   9 #ifndef BOOST_GRAPH_DISTRIBUTED_FRUCHTERMAN_REINGOLD_HPP
  10 #define BOOST_GRAPH_DISTRIBUTED_FRUCHTERMAN_REINGOLD_HPP
  11
  12 #ifndef BOOST_GRAPH_USE_MPI
  13 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
  14 #endif
  15
  16 #include <boost/graph/fruchterman_reingold.hpp>
  17
  18 namespace boost { namespace graph { namespace distributed {
  19
  20 class simple_tiling
  21 {
  22  public:
  23   simple_tiling(int columns, int rows, bool flip = true)
  24     : columns(columns), rows(rows), flip(flip)
  25   {
  26   }
  27
  28   // Convert from a position (x, y) in the tiled display into a
  29   // processor ID number
  30   int operator()(int x, int y) const
  31   {
  32     return flip? (rows - y - 1) * columns + x : y * columns + x;
  33   }
  34
  35   // Convert from a process ID to a position (x, y) in the tiled
  36   // display
  37   std::pair<int, int> operator()(int id)
  38   {
  39     int my_col = id % columns;
  40     int my_row = flip? rows - (id / columns) - 1 : id / columns;
  41     return std::make_pair(my_col, my_row);
  42   }
  43
  44   int columns, rows;
  45
  46  private:
  47   bool flip;
  48 };
  49
  50 // Force pairs function object that does nothing
  51 struct no_force_pairs
  52 {
  53   template<typename Graph, typename ApplyForce>
  54   void operator()(const Graph&, const ApplyForce&)
  55   {
  56   }
  57 };
  58
  59 // Computes force pairs in the distributed case.
  60 template<typename PositionMap, typename DisplacementMap, typename LocalForces,
  61          typename NonLocalForces = no_force_pairs>
  62 class distributed_force_pairs_proxy
  63 {
  64  public:
  65   distributed_force_pairs_proxy(const PositionMap& position,
  66                                 const DisplacementMap& displacement,
  67                                 const LocalForces& local_forces,
  68                                 const NonLocalForces& nonlocal_forces = NonLocalForces())
  69     : position(position), displacement(displacement),
  70       local_forces(local_forces), nonlocal_forces(nonlocal_forces)
  71   {
  72   }
  73
  74   template<typename Graph, typename ApplyForce>
  75   void operator()(const Graph& g, ApplyForce apply_force)
  76   {
  77     // Flush remote displacements
  78     displacement.flush();
  79
  80     // Receive updated positions for all of our neighbors
  81     synchronize(position);
  82
  83     // Reset remote displacements
  84     displacement.reset();
  85
  86     // Compute local repulsive forces
  87     local_forces(g, apply_force);
  88
  89     // Compute neighbor repulsive forces
  90     nonlocal_forces(g, apply_force);
  91   }
  92
  93  protected:
  94   PositionMap position;
  95   DisplacementMap displacement;
  96   LocalForces local_forces;
  97   NonLocalForces nonlocal_forces;
  98 };
  99
 100 template<typename PositionMap, typename DisplacementMap, typename LocalForces>
 101 inline
 102 distributed_force_pairs_proxy<PositionMap, DisplacementMap, LocalForces>
 103 make_distributed_force_pairs(const PositionMap& position,
 104                              const DisplacementMap& displacement,
 105                              const LocalForces& local_forces)
 106 {
 107   typedef
 108     distributed_force_pairs_proxy<PositionMap, DisplacementMap, LocalForces>
 109     result_type;
 110   return result_type(position, displacement, local_forces);
 111 }
 112
 113 template<typename PositionMap, typename DisplacementMap, typename LocalForces,
 114          typename NonLocalForces>
 115 inline
 116 distributed_force_pairs_proxy<PositionMap, DisplacementMap, LocalForces,
 117                               NonLocalForces>
 118 make_distributed_force_pairs(const PositionMap& position,
 119                              const DisplacementMap& displacement,
 120                              const LocalForces& local_forces,
 121                              const NonLocalForces& nonlocal_forces)
 122 {
 123   typedef
 124     distributed_force_pairs_proxy<PositionMap, DisplacementMap, LocalForces,
 125                                   NonLocalForces>
 126       result_type;
 127   return result_type(position, displacement, local_forces, nonlocal_forces);
 128 }
 129
 130 // Compute nonlocal force pairs based on the shared borders with
 131 // adjacent tiles.
 132 template<typename PositionMap>
 133 class neighboring_tiles_force_pairs
 134 {
 135  public:
 136   typedef typename property_traits<PositionMap>::value_type Point;
 137   typedef typename point_traits<Point>::component_type Dim;
 138
 139   enum bucket_position { left, top, right, bottom, end_position };
 140
 141   neighboring_tiles_force_pairs(PositionMap position, Point origin,
 142                                 Point extent, simple_tiling tiling)
 143     : position(position), origin(origin), extent(extent), tiling(tiling)
 144   {
 145   }
 146
 147   template<typename Graph, typename ApplyForce>
 148   void operator()(const Graph& g, ApplyForce apply_force)
 149   {
 150     // TBD: Do this some smarter way
 151     if (tiling.columns == 1 && tiling.rows == 1)
 152       return;
 153
 154     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
 155 #ifndef BOOST_NO_STDC_NAMESPACE
 156     using std::sqrt;
 157 #endif // BOOST_NO_STDC_NAMESPACE
 158
 159     // TBD: num_vertices(g) should be the global number of vertices?
 160     Dim two_k = Dim(2) * sqrt(extent[0] * extent[1] / num_vertices(g));
 161
 162     std::vector<vertex_descriptor> my_vertices[4];
 163     std::vector<vertex_descriptor> neighbor_vertices[4];
 164
 165     // Compute cutoff positions
 166     Dim cutoffs[4];
 167     cutoffs[left] = origin[0] + two_k;
 168     cutoffs[top] = origin[1] + two_k;
 169     cutoffs[right] = origin[0] + extent[0] - two_k;
 170     cutoffs[bottom] = origin[1] + extent[1] - two_k;
 171
 172     // Compute neighbors
 173     typename PositionMap::process_group_type pg = position.process_group();
 174     std::pair<int, int> my_tile = tiling(process_id(pg));
 175     int neighbors[4] = { -1, -1, -1, -1 } ;
 176     if (my_tile.first > 0)
 177       neighbors[left] = tiling(my_tile.first - 1, my_tile.second);
 178     if (my_tile.second > 0)
 179       neighbors[top] = tiling(my_tile.first, my_tile.second - 1);
 180     if (my_tile.first < tiling.columns - 1)
 181       neighbors[right] = tiling(my_tile.first + 1, my_tile.second);
 182     if (my_tile.second < tiling.rows - 1)
 183       neighbors[bottom] = tiling(my_tile.first, my_tile.second + 1);
 184
 185     // Sort vertices along the edges into buckets
 186     BGL_FORALL_VERTICES_T(v, g, Graph) {
 187       if (position[v][0] <= cutoffs[left]) my_vertices[left].push_back(v);
 188       if (position[v][1] <= cutoffs[top]) my_vertices[top].push_back(v);
 189       if (position[v][0] >= cutoffs[right]) my_vertices[right].push_back(v);
 190       if (position[v][1] >= cutoffs[bottom]) my_vertices[bottom].push_back(v);
 191     }
 192
 193     // Send vertices to neighbors, and gather our neighbors' vertices
 194     bucket_position pos;
 195     for (pos = left; pos < end_position; pos = bucket_position(pos + 1)) {
 196       if (neighbors[pos] != -1) {
 197         send(pg, neighbors[pos], 0, my_vertices[pos].size());
 198         if (!my_vertices[pos].empty())
 199           send(pg, neighbors[pos], 1,
 200                &my_vertices[pos].front(), my_vertices[pos].size());
 201       }
 202     }
 203
 204     // Pass messages around
 205     synchronize(pg);
 206
 207     // Receive neighboring vertices
 208     for (pos = left; pos < end_position; pos = bucket_position(pos + 1)) {
 209       if (neighbors[pos] != -1) {
 210         std::size_t incoming_vertices;
 211         receive(pg, neighbors[pos], 0, incoming_vertices);
 212
 213         if (incoming_vertices) {
 214           neighbor_vertices[pos].resize(incoming_vertices);
 215           receive(pg, neighbors[pos], 1, &neighbor_vertices[pos].front(),
 216                   incoming_vertices);
 217         }
 218       }
 219     }
 220
 221     // For each neighboring vertex, we need to get its current position
 222     for (pos = left; pos < end_position; pos = bucket_position(pos + 1))
 223       for (typename std::vector<vertex_descriptor>::iterator i =
 224              neighbor_vertices[pos].begin();
 225            i != neighbor_vertices[pos].end();
 226            ++i)
 227         request(position, *i);
 228     synchronize(position);
 229
 230     // Apply forces in adjacent bins. This is O(n^2) in the worst
 231     // case. Oh well.
 232     for (pos = left; pos < end_position; pos = bucket_position(pos + 1)) {
 233       for (typename std::vector<vertex_descriptor>::iterator i =
 234              my_vertices[pos].begin();
 235            i != my_vertices[pos].end();
 236            ++i)
 237         for (typename std::vector<vertex_descriptor>::iterator j =
 238                neighbor_vertices[pos].begin();
 239              j != neighbor_vertices[pos].end();
 240              ++j)
 241           apply_force(*i, *j);
 242     }
 243   }
 244
 245  protected:
 246   PositionMap position;
 247   Point origin;
 248   Point extent;
 249   simple_tiling tiling;
 250 };
 251
 252 template<typename PositionMap>
 253 inline neighboring_tiles_force_pairs<PositionMap>
 254 make_neighboring_tiles_force_pairs
 255  (PositionMap position,
 256   typename property_traits<PositionMap>::value_type origin,
 257   typename property_traits<PositionMap>::value_type extent,
 258   simple_tiling tiling)
 259 {
 260   return neighboring_tiles_force_pairs<PositionMap>(position, origin, extent,
 261                                                     tiling);
 262 }
 263
 264 template<typename DisplacementMap, typename Cooling>
 265 class distributed_cooling_proxy
 266 {
 267  public:
 268   typedef typename Cooling::result_type result_type;
 269
 270   distributed_cooling_proxy(const DisplacementMap& displacement,
 271                             const Cooling& cooling)
 272     : displacement(displacement), cooling(cooling)
 273   {
 274   }
 275
 276   result_type operator()()
 277   {
 278     // Accumulate displacements computed on each processor
 279     synchronize(displacement.data->process_group);
 280
 281     // Allow the underlying cooling to occur
 282     return cooling();
 283   }
 284
 285  protected:
 286   DisplacementMap displacement;
 287   Cooling cooling;
 288 };
 289
 290 template<typename DisplacementMap, typename Cooling>
 291 inline distributed_cooling_proxy<DisplacementMap, Cooling>
 292 make_distributed_cooling(const DisplacementMap& displacement,
 293                          const Cooling& cooling)
 294 {
 295   typedef distributed_cooling_proxy<DisplacementMap, Cooling> result_type;
 296   return result_type(displacement, cooling);
 297 }
 298
 299 template<typename Point>
 300 struct point_accumulating_reducer {
 301   BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);
 302
 303   template<typename K>
 304   Point operator()(const K&) const { return Point(); }
 305
 306   template<typename K>
 307   Point operator()(const K&, const Point& p1, const Point& p2) const
 308   { return Point(p1[0] + p2[0], p1[1] + p2[1]); }
 309 };
 310
 311 template<typename Graph, typename PositionMap,
 312          typename AttractiveForce, typename RepulsiveForce,
 313          typename ForcePairs, typename Cooling, typename DisplacementMap>
 314 void
 315 fruchterman_reingold_force_directed_layout
 316  (const Graph&    g,
 317   PositionMap     position,
 318   typename property_traits<PositionMap>::value_type const& origin,
 319   typename property_traits<PositionMap>::value_type const& extent,
 320   AttractiveForce attractive_force,
 321   RepulsiveForce  repulsive_force,
 322   ForcePairs      force_pairs,
 323   Cooling         cool,
 324   DisplacementMap displacement)
 325 {
 326   typedef typename property_traits<PositionMap>::value_type Point;
 327
 328   // Reduction in the displacement map involves summing the forces
 329   displacement.set_reduce(point_accumulating_reducer<Point>());
 330
 331   // We need to track the positions of all of our neighbors
 332   BGL_FORALL_VERTICES_T(u, g, Graph)
 333     BGL_FORALL_ADJ_T(u, v, g, Graph)
 334       request(position, v);
 335
 336   // Invoke the "sequential" Fruchterman-Reingold implementation
 337   boost::fruchterman_reingold_force_directed_layout
 338     (g, position, origin, extent,
 339      attractive_force, repulsive_force,
 340      make_distributed_force_pairs(position, displacement, force_pairs),
 341      make_distributed_cooling(displacement, cool),
 342      displacement);
 343 }
 344
 345 template<typename Graph, typename PositionMap,
 346          typename AttractiveForce, typename RepulsiveForce,
 347          typename ForcePairs, typename Cooling, typename DisplacementMap>
 348 void
 349 fruchterman_reingold_force_directed_layout
 350  (const Graph&    g,
 351   PositionMap     position,
 352   typename property_traits<PositionMap>::value_type const& origin,
 353   typename property_traits<PositionMap>::value_type const& extent,
 354   AttractiveForce attractive_force,
 355   RepulsiveForce  repulsive_force,
 356   ForcePairs      force_pairs,
 357   Cooling         cool,
 358   DisplacementMap displacement,
 359   simple_tiling   tiling)
 360 {
 361   typedef typename property_traits<PositionMap>::value_type Point;
 362
 363   // Reduction in the displacement map involves summing the forces
 364   displacement.set_reduce(point_accumulating_reducer<Point>());
 365
 366   // We need to track the positions of all of our neighbors
 367   BGL_FORALL_VERTICES_T(u, g, Graph)
 368     BGL_FORALL_ADJ_T(u, v, g, Graph)
 369       request(position, v);
 370
 371   // Invoke the "sequential" Fruchterman-Reingold implementation
 372   boost::fruchterman_reingold_force_directed_layout
 373     (g, position, origin, extent,
 374      attractive_force, repulsive_force,
 375      make_distributed_force_pairs
 376       (position, displacement, force_pairs,
 377        make_neighboring_tiles_force_pairs(position, origin, extent, tiling)),
 378      make_distributed_cooling(displacement, cool),
 379      displacement);
 380 }
 381
 382 } } } // end namespace boost::graph::distributed
 383
 384 #endif // BOOST_GRAPH_DISTRIBUTED_FRUCHTERMAN_REINGOLD_HPP