source: NonGTP/Boost/boost/graph/fruchterman_reingold.hpp @ 857

Revision 857, 14.5 KB checked in by igarcia, 19 years ago (diff)
Line 
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
20namespace boost {
21
22struct 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
34struct 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
47template<typename T>
48struct 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
70struct 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
87template<typename Dim, typename PositionMap>
88struct 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
160template<typename Dim, typename PositionMap, typename Graph>
161inline grid_force_pairs<Dim, PositionMap>
162make_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
166template<typename Graph, typename PositionMap, typename Dim>
167void
168scale_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
202namespace 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
241template<typename Graph, typename PositionMap, typename Dim,
242         typename AttractiveForce, typename RepulsiveForce,
243         typename ForcePairs, typename Cooling, typename DisplacementMap>
244void
245fruchterman_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
320namespace 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
379template<typename Graph, typename PositionMap, typename Dim, typename Param,
380         typename Tag, typename Rest>
381void
382fruchterman_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
406template<typename Graph, typename PositionMap, typename Dim>
407void
408fruchterman_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
Note: See TracBrowser for help on using the repository browser.