1<HTML> 2<!-- 3 Copyright (c) 2004, 2010 Trustees of Indiana University 4 5 Distributed under the Boost Software License, Version 1.0. 6 (See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8 --> 9 10<Head> 11<Title>Boost Graph Library: Fruchterman-Reingold Force-Directed Layout</Title> 12<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 13 ALINK="#ff0000"> 14<IMG SRC="../../../boost.png" 15 ALT="C++ Boost" width="277" height="86"> 16 17<BR Clear> 18<img src="figs/python.gif" alt="(Python)"/> 19<TT>fruchterman_reingold_force_directed_layout</TT> 20</H1> 21 22 23<P> 24<PRE> 25<i>// named parameter version</i> 26template<typename Graph, typename PositionMap, typename Topology, typename Param, 27 typename Tag, typename Rest> 28void 29fruchterman_reingold_force_directed_layout 30 (const Graph& g, 31 PositionMap position, 32 const Topology& space, 33 const bgl_named_params<Param, Tag, Rest>& params); 34 35<i>// non-named parameter version</i> 36template<typename Graph, typename PositionMap, typename Topology, 37 typename AttractiveForce, typename RepulsiveForce, 38 typename ForcePairs, typename DisplacementMap, typename Cooling> 39void 40fruchterman_reingold_force_directed_layout 41 (const Graph& g, 42 PositionMap position, 43 const Topology& space, 44 AttractiveForce fa, 45 RepulsiveForce fr, 46 ForcePairs fp, 47 Cooling cool, 48 DisplacementMap displacement); 49 50template<typename Graph, typename PositionMap, typename Topology> 51void 52fruchterman_reingold_force_directed_layout(const Graph& g, 53 PositionMap position, 54 Topology& space, 55 Dim width, 56 Dim height); 57</PRE> 58 59<P> This algorithm [<A 60HREF="bibliography.html#fruchterman91">58</A>] performs layout of 61unweighted, undirected graphs. Unlike the <a 62href="kamada_kawai_spring_layout.html">Kamada-Kawai</a> layout 63algorithm, this algorithm directly supports the layout of disconnected 64graphs (but see the <tt>force_pairs</tt> named parameter). It is a 65<em>force-directed</em> algorithm, meaning that vertex layout is 66determined by the forces pulling vertices together and pushing them 67apart. Attractive forces occur between adjacent vertices only, whereas 68repulsive forces occur between every pair of vertices. Each iteration 69computes the sum of the forces on each vertex, then moves the vertices 70to their new positions. The movement of vertices is mitigated by the 71<i>temperature</i> of the system for that iteration: as the algorithm 72progresses through successive iterations, the temperature should 73decrease so that vertices settle in place. The cooling schedule, 74attractive forces, and repulsive forces can be provided by the user. 75 76<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>. 77 78<h3>Where Defined</h3> 79 80<a href="../../../boost/graph/fruchterman_reingold.hpp"><tt>boost/graph/fruchterman_reingold.hpp</tt></a> 81 82<h3>Parameters</h3> 83 84IN: <tt>const Graph& g</tt> 85<blockquote> 86 The graph object on which the algorithm will be applied. 87 The type <tt>Graph</tt> must be a model of 88 <a href="./VertexAndEdgeListGraph.html">Vertex And Edge List Graph</a>.<br> 89 <b>Python</b>: This parameter is named <tt>graph</tt> in Python. 90</blockquote> 91 92IN/OUT: <tt>PositionMap position</tt> 93<blockquote> 94 The property map that stores the position of each vertex. It should 95 typically be initialized with the vertices at random locations (use 96 <a href="random_layout.html"><tt>random_graph_layout</tt></a>). The 97 type <tt>PositionMap</tt> must be a model of <a 98 href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property 99 Map</a> such that the vertex descriptor type of <tt>Graph</tt> is 100 convertible to its key type. Its value type must be 101 <tt>Topology::point_type</tt>, representing the coordinates 102 of the vertex.<br> 103 <b>Python</b>: The position map must be a <tt>vertex_point2d_map</tt> for 104 the graph.<br> 105 <b>Python default</b>: <tt>graph.get_vertex_point2d_map("position")</tt> 106</blockquote> 107 108IN: <tt>const Topology& space</tt> 109<blockquote> 110 The topology used to lay out the vertices. This parameter describes both the 111 size and shape of the layout area. Topologies are described in more detail 112 (with a list of BGL-provided topologies) <a href="topology.html">in separate 113 documentation</a>. 114</blockquote> 115 116<h3>Named Parameters</h3> 117 118IN: <tt>attractive_force(AttractiveForce fa)</tt> 119<blockquote> 120Computes the magnitude of the attractive force between two adjacent 121vertices. The function object <tt>fa</tt> must accept four 122parameters: the edge descriptor, <tt>k</tt>, the distance between the 123vertices, and the graph. <tt>k</tt> is the square root of the ratio 124of the display area to the number of vertices. <br> 125<b>Default:</b> <tt>square_distance_attractive_force()</tt>, which 126computes the attractive force as <code>dist<sup>2</sup>/k</code>.<br> 127<b>Python</b>: Any callable Python object that matches the signature will suffice. 128</blockquote> 129 130IN: <tt>repulsive_force(RepulsiveForce fr)</tt> 131<blockquote> 132Computes the magnitude of the repulsive force between any two 133vertices. The function object <tt>fr</tt> must accept five 134parameters: the two vertex descriptors, <tt>k</tt>, the distance between the 135vertices, and the graph. <tt>k</tt> is the square root of the ratio 136of the display area to the number of vertices. <br> 137<b>Default:</b> <tt>square_distance_repsulsive_force()</tt>, which 138computes the repulsive force as <code>k<sup>2</sup>/dist</code>.<br> 139<b>Python</b>: Any callable Python object that matches the signature will suffice. 140</blockquote> 141 142IN: <tt>force_pairs(ForcePairs fp)</tt> 143<blockquote> 144Enumerates the pairs of vertices on which the repulsive force should 145be applied. <tt>fp</tt> is a function object taking two parameters: 146the graph <tt>g</tt> and a binary function object that should be 147passed each pair of vertices to be considered. The basic formulation 148of the Fruchterman-Reingold algorithm computes repulsive forces 149between all pairs of vertices (pass <tt>all_force_pairs()</tt> for 150this parameter), which is functional for disconnected graphs but 151tends to push the connected components toward the edges of the 152display area. The grid variant of the algorithm places a grid over 153the display area and only computes repulsive forces among vertices 154within each rectangle in the grid. The grid variant can be more 155efficient than the basic formulation and tends to produce better 156layouts for disconnected graphs, but is not better overall: pass 157<tt>make_grid_force_pairs(width, height, position, g)</tt> as this 158parameter to use the grid variant. Other enumeration strategies may 159yield better results for particular graphs. <br> 160<b>Default:</b> <tt>make_grid_force_pairs(width, height, position, g)</tt><br> 161<b>Python</b>: Unsupported parameter. 162</blockquote> 163 164IN: <tt>cooling(Cooling cool)</tt> 165<blockquote> 166Determines the cooling schedule for the algorithm, which affects the 167rate of movement of vertices and termination of the algorithm. The 168<tt>cool</tt> parameter is a nullary function object (i.e., one that 169takes no arguments) and returns the temperature for the current 170iteration. When the returned temperature is zero, the algorithm 171terminates. Cooling schedules should begin with some initial 172temperature and gradually reduce the temperature to zero.<br> 173<b>Default:</b> <tt>linear_cooling<double>(100)</tt><br> 174<b>Python</b>: Any callable Python object that matches the signature will suffice. 175</blockquote> 176 177UTIL: <tt>displacement_map(DisplacementMap displacement)</tt> 178<blockquote> 179The displacement map is used to compute the amount by which each 180vertex will move in each step. The <tt>DisplacementMap</tt> type must be a 181property map whose key type is the graph's vertex type and whose value type is 182<tt>Topology::point_difference_type</tt>.<br> 183<b>Default:</b> An <tt>iterator_property_map</tt> with the specified value type 184and using the given vertex index map.<br> 185<b>Python:</b> Unsupported parameter. 186</blockquote> 187 188IN: <tt>vertex_index_map(VertexIndexMap i_map)</tt> 189<blockquote> 190 This maps each vertex to an integer in the range <tt>[0, 191 num_vertices(g))</tt>. This is only necessary when no 192 displacement map is provided. 193 The type <tt>VertexIndexMap</tt> must be a model of <a 194 href="../../property_map/doc/ReadablePropertyMap.html">Readable Property 195 Map</a>. The value type of the map must be an integer type. The 196 vertex descriptor type of the graph needs to be usable as the key 197 type of the map.<br> 198<b>Default:</b> <tt>get(vertex_index, g)</tt> 199 Note: if you use this default, make sure your graph has 200 an internal <tt>vertex_index</tt> property. For example, 201 <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does 202 not have an internal <tt>vertex_index</tt> property. 203 <br> 204<b>Python:</b> Unsupported parameter. 205</blockquote> 206 207<b>Python</b> IN: <tt>bool progressive</tt> 208<blockquote> 209 When <tt>false</tt>, performs a random layout of the graph before 210 running the Fruchterman-Reingold algorithm. If <tt>true</tt>, the 211 algorithm is executing starting with the vertex configuration in 212 the <tt>position</tt> map.<br> 213 <b>Default</b>: <tt>False</tt>. 214</blockquote> 215 216<H3>Complexity</H3> 217 218<P> The time complexity is <i>O(|V|<sup>2</sup> + |E|)</i> for each 219iteration of the algorithm in the worst case. The average case for the 220grid variant is <i>O(|V| + |E|)</i>. The number of iterations is 221determined by the cooling schedule. 222 223<H3>Example</H3> 224<a href="../example/fr_layout.cpp">libs/graph/example/fr_layout.cpp</a> 225 226<br> 227<HR> 228<TABLE> 229<TR valign=top> 230<TD nowrap>Copyright © 2004, 2010 Trustees of Indiana University</TD><TD> 231<A HREF="http://www.boost.org/people/doug_gregor.html">Doug Gregor</A>, Indiana University 232</TD></TR></TABLE> 233 234</BODY> 235</HTML> 236
