Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/fruchterman_reingold.html @ 45

Last change on this file since 45 was 29, checked in by landauf, 17 years ago

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