1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
|
<HTML>
<!--
-- Copyright (c) 2004 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 Dim, typename Param,
typename Tag, typename Rest>
void
fruchterman_reingold_force_directed_layout
(const Graph& g,
PositionMap position,
Dim width,
Dim height,
const bgl_named_params<Param, Tag, Rest>& params);
<i>// non-named parameter version</i>
template<typename Graph, typename PositionMap, typename Dim,
typename AttractiveForce, typename RepulsiveForce,
typename ForcePairs, typename DisplacementMap, typename Cooling>
void
fruchterman_reingold_force_directed_layout
(const Graph& g,
PositionMap position,
Dim width,
Dim height,
AttractiveForce fa,
RepulsiveForce fr,
ForcePairs fp,
Cooling cool,
DisplacementMap displacement);
template<typename Graph, typename PositionMap, typename Dim>
void
fruchterman_reingold_force_directed_layout(const Graph& g,
PositionMap position,
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/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 a structure
with fields <tt>x</tt> and <tt>y</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>Dim width</tt>
<blockquote>
The width of the display area in which layout should occur. On
termination of the algorithm, the <tt>x</tt> coordinates of all
vertices will fall in <tt>[-width/2, width/2]</tt>.
</blockquote>
IN: <tt>Dim height</tt>
<blockquote>
The height of the display area in which layout should occur. On
termination of the algorithm, the <tt>y</tt> coordinates of all
vertices will fall in <tt>[-height/2, height/2]</tt>.
</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
carries the same requirements as the <tt>PositionMap</tt> type.<br>
<b>Default:</b> An <tt>iterator_property_map</tt> with a value type
of <tt>simple_point<double></tt> 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/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</TD><TD>
<A HREF="http://www.boost.org/people/doug_gregor.html">Doug Gregor</A>, Indiana University
</TD></TR></TABLE>
</BODY>
</HTML>
|
