Ugly, not-to-be-pushed sucking in of all of Boost to get windows to work.
[dyninst.git] / external / boost / graph / fruchterman_reingold.hpp
1 // Copyright 2004 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_FRUCHTERMAN_REINGOLD_FORCE_DIRECTED_LAYOUT_HPP
10 #define BOOST_GRAPH_FRUCHTERMAN_REINGOLD_FORCE_DIRECTED_LAYOUT_HPP
11
12 #include <cmath>
13 #include <boost/graph/graph_traits.hpp>
14 #include <boost/graph/named_function_params.hpp>
15 #include <boost/graph/simple_point.hpp>
16 #include <vector>
17 #include <list>
18 #include <algorithm> // for std::min and std::max
19
20 namespace boost {
21
22 struct square_distance_attractive_force {
23   template<typename Graph, typename T>
24   T
25   operator()(typename graph_traits<Graph>::edge_descriptor,
26              T k,
27              T d,
28              const Graph&) const
29   {
30     return d * d / k;
31   }
32 };
33
34 struct square_distance_repulsive_force {
35   template<typename Graph, typename T>
36   T
37   operator()(typename graph_traits<Graph>::vertex_descriptor,
38              typename graph_traits<Graph>::vertex_descriptor,
39              T k,
40              T d,
41              const Graph&) const
42   {
43     return k * k / d;
44   }
45 };
46
47 template<typename T>
48 struct linear_cooling {
49   typedef T result_type;
50
51   linear_cooling(std::size_t iterations)
52     : temp(T(iterations) / T(10)), step(0.1) { }
53
54   linear_cooling(std::size_t iterations, T temp)
55     : temp(temp), step(temp / T(iterations)) { }
56
57   T operator()()
58   {
59     T old_temp = temp;
60     temp -= step;
61     if (temp < T(0)) temp = T(0);
62     return old_temp;
63   }
64
65  private:
66   T temp;
67   T step;
68 };
69
70 struct all_force_pairs
71 {
72   template<typename Graph, typename ApplyForce >
73   void operator()(const Graph& g, ApplyForce apply_force)
74   {
75     typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
76     vertex_iterator v, end;
77     for (tie(v, end) = vertices(g); v != end; ++v) {
78       vertex_iterator u = v;
79       for (++u; u != end; ++u) {
80         apply_force(*u, *v);
81         apply_force(*v, *u);
82       }
83     }
84   }
85 };
86
87 template<typename Dim, typename PositionMap>
88 struct grid_force_pairs
89 {
90   template<typename Graph>
91   explicit
92   grid_force_pairs(Dim width, Dim height, PositionMap position, const Graph& g)
93     : width(width), height(height), position(position)
94   {
95 #ifndef BOOST_NO_STDC_NAMESPACE
96     using std::sqrt;
97 #endif // BOOST_NO_STDC_NAMESPACE
98     two_k = Dim(2) * sqrt(width*height / num_vertices(g));
99   }
100
101   template<typename Graph, typename ApplyForce >
102   void operator()(const Graph& g, ApplyForce apply_force)
103   {
104     typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
105     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
106     typedef std::list<vertex_descriptor> bucket_t;
107     typedef std::vector<bucket_t> buckets_t;
108
109     std::size_t columns = std::size_t(width / two_k + Dim(1));
110     std::size_t rows = std::size_t(height / two_k + Dim(1));
111     buckets_t buckets(rows * columns);
112     vertex_iterator v, v_end;
113     for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
114       std::size_t column = std::size_t((position[*v].x + width  / 2) / two_k);
115       std::size_t row    = std::size_t((position[*v].y + height / 2) / two_k);
116
117       if (column >= columns) column = columns - 1;
118       if (row >= rows) row = rows - 1;
119       buckets[row * columns + column].push_back(*v);
120     }
121
122     for (std::size_t row = 0; row < rows; ++row)
123       for (std::size_t column = 0; column < columns; ++column) {
124         bucket_t& bucket = buckets[row * columns + column];
125         typedef typename bucket_t::iterator bucket_iterator;
126         for (bucket_iterator u = bucket.begin(); u != bucket.end(); ++u) {
127           // Repulse vertices in this bucket
128           bucket_iterator v = u;
129           for (++v; v != bucket.end(); ++v) {
130             apply_force(*u, *v);
131             apply_force(*v, *u);
132           }
133
134           std::size_t adj_start_row = row == 0? 0 : row - 1;
135           std::size_t adj_end_row = row == rows - 1? row : row + 1;
136           std::size_t adj_start_column = column == 0? 0 : column - 1;
137           std::size_t adj_end_column = column == columns - 1? column : column + 1;
138           for (std::size_t other_row = adj_start_row; other_row <= adj_end_row;
139                ++other_row)
140             for (std::size_t other_column = adj_start_column; 
141                  other_column <= adj_end_column; ++other_column)
142               if (other_row != row || other_column != column) {
143                 // Repulse vertices in this bucket
144                 bucket_t& other_bucket 
145                   = buckets[other_row * columns + other_column];
146                 for (v = other_bucket.begin(); v != other_bucket.end(); ++v)
147                   apply_force(*u, *v);
148               }
149         }
150       }
151   }
152
153  private:
154   Dim width;
155   Dim height;
156   PositionMap position;
157   Dim two_k;
158 };
159
160 template<typename Dim, typename PositionMap, typename Graph>
161 inline grid_force_pairs<Dim, PositionMap>
162 make_grid_force_pairs(Dim width, Dim height, const PositionMap& position,
163                       const Graph& g)
164 { return grid_force_pairs<Dim, PositionMap>(width, height, position, g); }
165
166 template<typename Graph, typename PositionMap, typename Dim>
167 void
168 scale_graph(const Graph& g, PositionMap position,
169             Dim left, Dim top, Dim right, Dim bottom)
170 {
171   if (num_vertices(g) == 0) return;
172
173   if (bottom > top) {
174     using std::swap;
175     swap(bottom, top);
176   }
177
178   typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
179
180   // Find min/max ranges
181   Dim minX = position[*vertices(g).first].x, maxX = minX;
182   Dim minY = position[*vertices(g).first].y, maxY = minY;
183   vertex_iterator vi, vi_end;
184   for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
185     BOOST_USING_STD_MIN();
186     BOOST_USING_STD_MAX();
187     minX = min BOOST_PREVENT_MACRO_SUBSTITUTION (minX, position[*vi].x);
188     maxX = max BOOST_PREVENT_MACRO_SUBSTITUTION (maxX, position[*vi].x);
189     minY = min BOOST_PREVENT_MACRO_SUBSTITUTION (minY, position[*vi].y);
190     maxY = max BOOST_PREVENT_MACRO_SUBSTITUTION (maxY, position[*vi].y);
191   }
192
193   // Scale to bounding box provided
194   for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
195     position[*vi].x = ((position[*vi].x - minX) / (maxX - minX))
196                     * (right - left) + left;
197     position[*vi].y = ((position[*vi].y - minY) / (maxY - minY))
198                     * (top - bottom) + bottom;
199   }
200 }
201
202 namespace detail {
203   template<typename PositionMap, typename DisplacementMap,
204            typename RepulsiveForce, typename Dim, typename Graph>
205   struct fr_apply_force
206   {
207     typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
208
209     fr_apply_force(const PositionMap& position,
210                    const DisplacementMap& displacement,
211                    RepulsiveForce repulsive_force, Dim k, const Graph& g)
212       : position(position), displacement(displacement),
213         repulsive_force(repulsive_force), k(k), g(g)
214     { }
215
216     void operator()(vertex_descriptor u, vertex_descriptor v)
217     {
218 #ifndef BOOST_NO_STDC_NAMESPACE
219       using std::sqrt;
220 #endif // BOOST_NO_STDC_NAMESPACE
221       if (u != v) {
222         Dim delta_x = position[v].x - position[u].x;
223         Dim delta_y = position[v].y - position[u].y;
224         Dim dist = sqrt(delta_x * delta_x + delta_y * delta_y);
225         Dim fr = repulsive_force(u, v, k, dist, g);
226         displacement[v].x += delta_x / dist * fr;
227         displacement[v].y += delta_y / dist * fr;
228       }
229     }
230
231   private:
232     PositionMap position;
233     DisplacementMap displacement;
234     RepulsiveForce repulsive_force;
235     Dim k;
236     const Graph& g;
237   };
238
239 } // end namespace detail
240
241 template<typename Graph, typename PositionMap, typename Dim,
242          typename AttractiveForce, typename RepulsiveForce,
243          typename ForcePairs, typename Cooling, typename DisplacementMap>
244 void
245 fruchterman_reingold_force_directed_layout
246  (const Graph&    g,
247   PositionMap     position,
248   Dim             width,
249   Dim             height,
250   AttractiveForce attractive_force,
251   RepulsiveForce  repulsive_force,
252   ForcePairs      force_pairs,
253   Cooling         cool,
254   DisplacementMap displacement)
255 {
256   typedef typename graph_traits<Graph>::vertex_iterator   vertex_iterator;
257   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
258   typedef typename graph_traits<Graph>::edge_iterator     edge_iterator;
259
260 #ifndef BOOST_NO_STDC_NAMESPACE
261   using std::sqrt;
262 #endif // BOOST_NO_STDC_NAMESPACE
263
264   Dim area = width * height;
265   // assume positions are initialized randomly
266   Dim k = sqrt(area / num_vertices(g));
267
268   detail::fr_apply_force<PositionMap, DisplacementMap,
269                          RepulsiveForce, Dim, Graph>
270     apply_force(position, displacement, repulsive_force, k, g);
271
272   Dim temp = cool();
273   if (temp) do {
274     // Calculate repulsive forces
275     vertex_iterator v, v_end;
276     for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
277       displacement[*v].x = 0;
278       displacement[*v].y = 0;
279     }
280     force_pairs(g, apply_force);
281
282     // Calculate attractive forces
283     edge_iterator e, e_end;
284     for (tie(e, e_end) = edges(g); e != e_end; ++e) {
285       vertex_descriptor v = source(*e, g);
286       vertex_descriptor u = target(*e, g);
287       Dim delta_x = position[v].x - position[u].x;
288       Dim delta_y = position[v].y - position[u].y;
289       Dim dist = sqrt(delta_x * delta_x + delta_y * delta_y);
290       Dim fa = attractive_force(*e, k, dist, g);
291
292       displacement[v].x -= delta_x / dist * fa;
293       displacement[v].y -= delta_y / dist * fa;
294       displacement[u].x += delta_x / dist * fa;
295       displacement[u].y += delta_y / dist * fa;
296     }
297
298     // Update positions
299     for (tie(v, v_end) = vertices(g); v != v_end; ++v) {
300       BOOST_USING_STD_MIN();
301       BOOST_USING_STD_MAX();
302       Dim disp_size = sqrt(displacement[*v].x * displacement[*v].x
303                            + displacement[*v].y * displacement[*v].y);
304       position[*v].x += displacement[*v].x / disp_size 
305                      * min BOOST_PREVENT_MACRO_SUBSTITUTION (disp_size, temp);
306       position[*v].y += displacement[*v].y / disp_size 
307                      * min BOOST_PREVENT_MACRO_SUBSTITUTION (disp_size, temp);
308       position[*v].x = min BOOST_PREVENT_MACRO_SUBSTITUTION 
309                          (width / 2, 
310                           max BOOST_PREVENT_MACRO_SUBSTITUTION(-width / 2, 
311                                                                position[*v].x));
312       position[*v].y = min BOOST_PREVENT_MACRO_SUBSTITUTION
313                          (height / 2, 
314                           max BOOST_PREVENT_MACRO_SUBSTITUTION(-height / 2, 
315                                                                position[*v].y));
316     }
317   } while (temp = cool());
318 }
319
320 namespace detail {
321   template<typename DisplacementMap>
322   struct fr_force_directed_layout
323   {
324     template<typename Graph, typename PositionMap, typename Dim,
325              typename AttractiveForce, typename RepulsiveForce,
326              typename ForcePairs, typename Cooling,
327              typename Param, typename Tag, typename Rest>
328     static void
329     run(const Graph&    g,
330         PositionMap     position,
331         Dim             width,
332         Dim             height,
333         AttractiveForce attractive_force,
334         RepulsiveForce  repulsive_force,
335         ForcePairs      force_pairs,
336         Cooling         cool,
337         DisplacementMap displacement,
338         const bgl_named_params<Param, Tag, Rest>&)
339     {
340       fruchterman_reingold_force_directed_layout
341         (g, position, width, height, attractive_force, repulsive_force,
342          force_pairs, cool, displacement);
343     }
344   };
345
346   template<>
347   struct fr_force_directed_layout<error_property_not_found>
348   {
349     template<typename Graph, typename PositionMap, typename Dim,
350              typename AttractiveForce, typename RepulsiveForce,
351              typename ForcePairs, typename Cooling,
352              typename Param, typename Tag, typename Rest>
353     static void
354     run(const Graph&    g,
355         PositionMap     position,
356         Dim             width,
357         Dim             height,
358         AttractiveForce attractive_force,
359         RepulsiveForce  repulsive_force,
360         ForcePairs      force_pairs,
361         Cooling         cool,
362         error_property_not_found,
363         const bgl_named_params<Param, Tag, Rest>& params)
364     {
365       std::vector<simple_point<double> > displacements(num_vertices(g));
366       fruchterman_reingold_force_directed_layout
367         (g, position, width, height, attractive_force, repulsive_force,
368          force_pairs, cool,
369          make_iterator_property_map
370          (displacements.begin(),
371           choose_const_pmap(get_param(params, vertex_index), g,
372                             vertex_index),
373           simple_point<double>()));
374     }
375   };
376
377 } // end namespace detail
378
379 template<typename Graph, typename PositionMap, typename Dim, typename Param,
380          typename Tag, typename Rest>
381 void
382 fruchterman_reingold_force_directed_layout
383   (const Graph&    g,
384    PositionMap     position,
385    Dim             width,
386    Dim             height,
387    const bgl_named_params<Param, Tag, Rest>& params)
388 {
389   typedef typename property_value<bgl_named_params<Param,Tag,Rest>,
390                                   vertex_displacement_t>::type D;
391
392   detail::fr_force_directed_layout<D>::run
393     (g, position, width, height,
394      choose_param(get_param(params, attractive_force_t()),
395                   square_distance_attractive_force()),
396      choose_param(get_param(params, repulsive_force_t()),
397                   square_distance_repulsive_force()),
398      choose_param(get_param(params, force_pairs_t()),
399                   make_grid_force_pairs(width, height, position, g)),
400      choose_param(get_param(params, cooling_t()),
401                   linear_cooling<double>(100)),
402      get_param(params, vertex_displacement_t()),
403      params);
404 }
405
406 template<typename Graph, typename PositionMap, typename Dim>
407 void
408 fruchterman_reingold_force_directed_layout(const Graph&    g,
409                                            PositionMap     position,
410                                            Dim             width,
411                                            Dim             height)
412 {
413   fruchterman_reingold_force_directed_layout
414     (g, position, width, height,
415      attractive_force(square_distance_attractive_force()));
416 }
417
418 } // end namespace boost
419
420 #endif // BOOST_GRAPH_FRUCHTERMAN_REINGOLD_FORCE_DIRECTED_LAYOUT_HPP