| <HTML> |
| <!-- |
| Copyright (c) 2004, 2010 Trustees of Indiana University |
| |
| Distributed under the Boost Software License, Version 1.0. |
| (See accompanying file LICENSE_1_0.txt or copy at |
| http://www.boost.org/LICENSE_1_0.txt) |
| --> |
| |
| <Head> |
| <Title>Boost Graph Library: Fruchterman-Reingold Force-Directed Layout</Title> |
| <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" |
| ALINK="#ff0000"> |
| <IMG SRC="../../../boost.png" |
| ALT="C++ Boost" width="277" height="86"> |
| |
| <BR Clear> |
| <img src="figs/python.gif" alt="(Python)"/> |
| <TT>fruchterman_reingold_force_directed_layout</TT> |
| </H1> |
| |
| |
| <P> |
| <PRE> |
| <i>// named parameter version</i> |
| template<typename Graph, typename PositionMap, typename Topology, typename Param, |
| typename Tag, typename Rest> |
| void |
| fruchterman_reingold_force_directed_layout |
| (const Graph& g, |
| PositionMap position, |
| const Topology& space, |
| const bgl_named_params<Param, Tag, Rest>& params); |
| |
| <i>// non-named parameter version</i> |
| template<typename Graph, typename PositionMap, typename Topology, |
| typename AttractiveForce, typename RepulsiveForce, |
| typename ForcePairs, typename DisplacementMap, typename Cooling> |
| void |
| fruchterman_reingold_force_directed_layout |
| (const Graph& g, |
| PositionMap position, |
| const Topology& space, |
| AttractiveForce fa, |
| RepulsiveForce fr, |
| ForcePairs fp, |
| Cooling cool, |
| DisplacementMap displacement); |
| |
| template<typename Graph, typename PositionMap, typename Topology> |
| void |
| fruchterman_reingold_force_directed_layout(const Graph& g, |
| PositionMap position, |
| Topology& space, |
| Dim width, |
| Dim height); |
| </PRE> |
| |
| <P> This algorithm [<A |
| HREF="bibliography.html#fruchterman91">58</A>] performs layout of |
| unweighted, undirected graphs. Unlike the <a |
| href="kamada_kawai_spring_layout.html">Kamada-Kawai</a> layout |
| algorithm, this algorithm directly supports the layout of disconnected |
| graphs (but see the <tt>force_pairs</tt> named parameter). It is a |
| <em>force-directed</em> algorithm, meaning that vertex layout is |
| determined by the forces pulling vertices together and pushing them |
| apart. Attractive forces occur between adjacent vertices only, whereas |
| repulsive forces occur between every pair of vertices. Each iteration |
| computes the sum of the forces on each vertex, then moves the vertices |
| to their new positions. The movement of vertices is mitigated by the |
| <i>temperature</i> of the system for that iteration: as the algorithm |
| progresses through successive iterations, the temperature should |
| decrease so that vertices settle in place. The cooling schedule, |
| attractive forces, and repulsive forces can be provided by the user. |
| |
| <p> The vertices are often placed randomly prior to execution of this algorithm via <a href="random_layout.html"><tt>random_graph_layout</tt></a>. |
| |
| <h3>Where Defined</h3> |
| |
| <a href="../../../boost/graph/fruchterman_reingold.hpp"><tt>boost/graph/fruchterman_reingold.hpp</tt></a> |
| |
| <h3>Parameters</h3> |
| |
| IN: <tt>const Graph& g</tt> |
| <blockquote> |
| The graph object on which the algorithm will be applied. |
| The type <tt>Graph</tt> must be a model of |
| <a href="./VertexAndEdgeListGraph.html">Vertex And Edge List Graph</a>.<br> |
| <b>Python</b>: This parameter is named <tt>graph</tt> in Python. |
| </blockquote> |
| |
| IN/OUT: <tt>PositionMap position</tt> |
| <blockquote> |
| The property map that stores the position of each vertex. It should |
| typically be initialized with the vertices at random locations (use |
| <a href="random_layout.html"><tt>random_graph_layout</tt></a>). The |
| type <tt>PositionMap</tt> must be a model of <a |
| href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property |
| Map</a> such that the vertex descriptor type of <tt>Graph</tt> is |
| convertible to its key type. Its value type must be |
| <tt>Topology::point_type</tt>, representing the coordinates |
| of the vertex.<br> |
| <b>Python</b>: The position map must be a <tt>vertex_point2d_map</tt> for |
| the graph.<br> |
| <b>Python default</b>: <tt>graph.get_vertex_point2d_map("position")</tt> |
| </blockquote> |
| |
| IN: <tt>const Topology& space</tt> |
| <blockquote> |
| The topology used to lay out the vertices. This parameter describes both the |
| size and shape of the layout area. Topologies are described in more detail |
| (with a list of BGL-provided topologies) <a href="topology.html">in separate |
| documentation</a>. |
| </blockquote> |
| |
| <h3>Named Parameters</h3> |
| |
| IN: <tt>attractive_force(AttractiveForce fa)</tt> |
| <blockquote> |
| Computes the magnitude of the attractive force between two adjacent |
| vertices. The function object <tt>fa</tt> must accept four |
| parameters: the edge descriptor, <tt>k</tt>, the distance between the |
| vertices, and the graph. <tt>k</tt> is the square root of the ratio |
| of the display area to the number of vertices. <br> |
| <b>Default:</b> <tt>square_distance_attractive_force()</tt>, which |
| computes the attractive force as <code>dist<sup>2</sup>/k</code>.<br> |
| <b>Python</b>: Any callable Python object that matches the signature will suffice. |
| </blockquote> |
| |
| IN: <tt>repulsive_force(RepulsiveForce fr)</tt> |
| <blockquote> |
| Computes the magnitude of the repulsive force between any two |
| vertices. The function object <tt>fa</tt> must accept five |
| parameters: the two vertex descriptors, <tt>k</tt>, the distance between the |
| vertices, and the graph. <tt>k</tt> is the square root of the ratio |
| of the display area to the number of vertices. <br> |
| <b>Default:</b> <tt>square_distance_repsulsive_force()</tt>, which |
| computes the repulsive force as <code>k<sup>2</sup>/dist</code>.<br> |
| <b>Python</b>: Any callable Python object that matches the signature will suffice. |
| </blockquote> |
| |
| IN: <tt>force_pairs(ForcePairs fp)</tt> |
| <blockquote> |
| Enumerates the pairs of vertices on which the repulsive force should |
| be applied. <tt>fp</tt> is a function object taking two parameters: |
| the graph <tt>g</tt> and a binary function object that should be |
| passed each pair of vertices to be considered. The basic formulation |
| of the Fruchterman-Reingold algorithm computes repulsive forces |
| between all pairs of vertices (pass <tt>all_force_pairs()</tt> for |
| this parameter), which is functional for disconnected graphs but |
| tends to push the connected components toward the edges of the |
| display area. The grid variant of the algorithm places a grid over |
| the display area and only computes repulsive forces among vertices |
| within each rectangle in the grid. The grid variant can be more |
| efficient than the basic formulation and tends to produce better |
| layouts for disconnected graphs, but is not better overall: pass |
| <tt>make_grid_force_pairs(width, height, position, g)</tt> as this |
| parameter to use the grid variant. Other enumeration strategies may |
| yield better results for particular graphs. <br> |
| <b>Default:</b> <tt>make_grid_force_pairs(width, height, position, g)</tt><br> |
| <b>Python</b>: Unsupported parameter. |
| </blockquote> |
| |
| IN: <tt>cooling(Cooling cool)</tt> |
| <blockquote> |
| Determines the cooling schedule for the algorithm, which affects the |
| rate of movement of vertices and termination of the algorithm. The |
| <tt>cool</tt> parameter is a nullary function object (i.e., one that |
| takes no arguments) and returns the temperature for the current |
| iteration. When the returned temperature is zero, the algorithm |
| terminates. Cooling schedules should begin with some initial |
| temperature and gradually reduce the temperature to zero.<br> |
| <b>Default:</b> <tt>linear_cooling<double>(100)</tt><br> |
| <b>Python</b>: Any callable Python object that matches the signature will suffice. |
| </blockquote> |
| |
| UTIL: <tt>displacement_map(DisplacementMap displacement)</tt> |
| <blockquote> |
| The displacement map is used to compute the amount by which each |
| vertex will move in each step. The <tt>DisplacementMap</tt> type must be a |
| property map whose key type is the graph's vertex type and whose value type is |
| <tt>Topology::point_difference_type</tt>.<br> |
| <b>Default:</b> An <tt>iterator_property_map</tt> with the specified value type |
| and using the given vertex index map.<br> |
| <b>Python:</b> Unsupported parameter. |
| </blockquote> |
| |
| IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt> |
| <blockquote> |
| This maps each vertex to an integer in the range <tt>[0, |
| num_vertices(g))</tt>. This is only necessary when no |
| displacement map is provided. |
| The type <tt>VertexIndexMap</tt> must be a model of <a |
| href="../../property_map/doc/ReadablePropertyMap.html">Readable Property |
| Map</a>. The value type of the map must be an integer type. The |
| vertex descriptor type of the graph needs to be usable as the key |
| type of the map.<br> |
| <b>Default:</b> <tt>get(vertex_index, g)</tt> |
| Note: if you use this default, make sure your graph has |
| an internal <tt>vertex_index</tt> property. For example, |
| <tt>adjacenty_list</tt> with <tt>VertexList=listS</tt> does |
| not have an internal <tt>vertex_index</tt> property. |
| <br> |
| <b>Python:</b> Unsupported parameter. |
| </blockquote> |
| |
| <b>Python</b> IN: <tt>bool progressive</tt> |
| <blockquote> |
| When <tt>false</tt>, performs a random layout of the graph before |
| running the Fruchterman-Reingold algorithm. If <tt>true</tt>, the |
| algorithm is executing starting with the vertex configuration in |
| the <tt>position</tt> map.<br> |
| <b>Default</b>: <tt>False</tt>. |
| </blockquote> |
| |
| <H3>Complexity</H3> |
| |
| <P> The time complexity is <i>O(|V|<sup>2</sup> + |E|)</i> for each |
| iteration of the algorithm in the worse case. The average case for the |
| grid variant is <i>O(|V| + |E|)</i>. The number of iterations is |
| determined by the cooling schedule. |
| |
| <H3>Example</H3> |
| <a href="../example/fr_layout.cpp">libs/graph/example/fr_layout.cpp</a> |
| |
| <br> |
| <HR> |
| <TABLE> |
| <TR valign=top> |
| <TD nowrap>Copyright © 2004, 2010 Trustees of Indiana University</TD><TD> |
| <A HREF="http://www.boost.org/people/doug_gregor.html">Doug Gregor</A>, Indiana University |
| </TD></TR></TABLE> |
| |
| </BODY> |
| </HTML> |
