]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |