fruchterman_reingold.hpp 13 KB

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