1 // Copyright 2004 The Trustees of Indiana University.

     2 

     3 // Distributed under the Boost Software License, Version 1.0.

     4 // (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<Dim> > 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<Dim>()));

   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<Dim>(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