epoc32/include/stdapis/boost/graph/fruchterman_reingold.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
     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