1 // Copyright (C) 2005-2006 The Trustees of Indiana University.
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)
7 // Authors: Douglas Gregor
9 #ifndef BOOST_GRAPH_DISTRIBUTED_FRUCHTERMAN_REINGOLD_HPP
10 #define BOOST_GRAPH_DISTRIBUTED_FRUCHTERMAN_REINGOLD_HPP
12 #ifndef BOOST_GRAPH_USE_MPI
13 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
16 #include <boost/graph/fruchterman_reingold.hpp>
18 namespace boost { namespace graph { namespace distributed {
23 simple_tiling(int columns, int rows, bool flip = true)
24 : columns(columns), rows(rows), flip(flip)
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
32 return flip? (rows - y - 1) * columns + x : y * columns + x;
35 // Convert from a process ID to a position (x, y) in the tiled
37 std::pair<int, int> operator()(int id)
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);
50 // Force pairs function object that does nothing
53 template<typename Graph, typename ApplyForce>
54 void operator()(const Graph&, const ApplyForce&)
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
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)
74 template<typename Graph, typename ApplyForce>
75 void operator()(const Graph& g, ApplyForce apply_force)
77 // Flush remote displacements
80 // Receive updated positions for all of our neighbors
81 synchronize(position);
83 // Reset remote displacements
86 // Compute local repulsive forces
87 local_forces(g, apply_force);
89 // Compute neighbor repulsive forces
90 nonlocal_forces(g, apply_force);
95 DisplacementMap displacement;
96 LocalForces local_forces;
97 NonLocalForces nonlocal_forces;
100 template<typename PositionMap, typename DisplacementMap, typename LocalForces>
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)
108 distributed_force_pairs_proxy<PositionMap, DisplacementMap, LocalForces>
110 return result_type(position, displacement, local_forces);
113 template<typename PositionMap, typename DisplacementMap, typename LocalForces,
114 typename NonLocalForces>
116 distributed_force_pairs_proxy<PositionMap, DisplacementMap, LocalForces,
118 make_distributed_force_pairs(const PositionMap& position,
119 const DisplacementMap& displacement,
120 const LocalForces& local_forces,
121 const NonLocalForces& nonlocal_forces)
124 distributed_force_pairs_proxy<PositionMap, DisplacementMap, LocalForces,
127 return result_type(position, displacement, local_forces, nonlocal_forces);
130 // Compute nonlocal force pairs based on the shared borders with
132 template<typename PositionMap>
133 class neighboring_tiles_force_pairs
136 typedef typename property_traits<PositionMap>::value_type Point;
137 typedef typename point_traits<Point>::component_type Dim;
139 enum bucket_position { left, top, right, bottom, end_position };
141 neighboring_tiles_force_pairs(PositionMap position, Point origin,
142 Point extent, simple_tiling tiling)
143 : position(position), origin(origin), extent(extent), tiling(tiling)
147 template<typename Graph, typename ApplyForce>
148 void operator()(const Graph& g, ApplyForce apply_force)
150 // TBD: Do this some smarter way
151 if (tiling.columns == 1 && tiling.rows == 1)
154 typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
155 #ifndef BOOST_NO_STDC_NAMESPACE
157 #endif // BOOST_NO_STDC_NAMESPACE
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));
162 std::vector<vertex_descriptor> my_vertices[4];
163 std::vector<vertex_descriptor> neighbor_vertices[4];
165 // Compute cutoff positions
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;
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);
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);
193 // Send vertices to neighbors, and gather our neighbors' vertices
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());
204 // Pass messages around
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);
213 if (incoming_vertices) {
214 neighbor_vertices[pos].resize(incoming_vertices);
215 receive(pg, neighbors[pos], 1, &neighbor_vertices[pos].front(),
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();
227 request(position, *i);
228 synchronize(position);
230 // Apply forces in adjacent bins. This is O(n^2) in the worst
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();
237 for (typename std::vector<vertex_descriptor>::iterator j =
238 neighbor_vertices[pos].begin();
239 j != neighbor_vertices[pos].end();
246 PositionMap position;
249 simple_tiling tiling;
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)
260 return neighboring_tiles_force_pairs<PositionMap>(position, origin, extent,
264 template<typename DisplacementMap, typename Cooling>
265 class distributed_cooling_proxy
268 typedef typename Cooling::result_type result_type;
270 distributed_cooling_proxy(const DisplacementMap& displacement,
271 const Cooling& cooling)
272 : displacement(displacement), cooling(cooling)
276 result_type operator()()
278 // Accumulate displacements computed on each processor
279 synchronize(displacement.data->process_group);
281 // Allow the underlying cooling to occur
286 DisplacementMap displacement;
290 template<typename DisplacementMap, typename Cooling>
291 inline distributed_cooling_proxy<DisplacementMap, Cooling>
292 make_distributed_cooling(const DisplacementMap& displacement,
293 const Cooling& cooling)
295 typedef distributed_cooling_proxy<DisplacementMap, Cooling> result_type;
296 return result_type(displacement, cooling);
299 template<typename Point>
300 struct point_accumulating_reducer {
301 BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);
304 Point operator()(const K&) const { return Point(); }
307 Point operator()(const K&, const Point& p1, const Point& p2) const
308 { return Point(p1[0] + p2[0], p1[1] + p2[1]); }
311 template<typename Graph, typename PositionMap,
312 typename AttractiveForce, typename RepulsiveForce,
313 typename ForcePairs, typename Cooling, typename DisplacementMap>
315 fruchterman_reingold_force_directed_layout
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,
324 DisplacementMap displacement)
326 typedef typename property_traits<PositionMap>::value_type Point;
328 // Reduction in the displacement map involves summing the forces
329 displacement.set_reduce(point_accumulating_reducer<Point>());
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);
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),
345 template<typename Graph, typename PositionMap,
346 typename AttractiveForce, typename RepulsiveForce,
347 typename ForcePairs, typename Cooling, typename DisplacementMap>
349 fruchterman_reingold_force_directed_layout
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,
358 DisplacementMap displacement,
359 simple_tiling tiling)
361 typedef typename property_traits<PositionMap>::value_type Point;
363 // Reduction in the displacement map involves summing the forces
364 displacement.set_reduce(point_accumulating_reducer<Point>());
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);
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),
382 } } } // end namespace boost::graph::distributed
384 #endif // BOOST_GRAPH_DISTRIBUTED_FRUCHTERMAN_REINGOLD_HPP