]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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> | |
26 | template<typename Graph, typename PositionMap, typename Topology, typename Param, | |
27 | typename Tag, typename Rest> | |
28 | void | |
29 | fruchterman_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> | |
36 | template<typename Graph, typename PositionMap, typename Topology, | |
37 | typename AttractiveForce, typename RepulsiveForce, | |
38 | typename ForcePairs, typename DisplacementMap, typename Cooling> | |
39 | void | |
40 | fruchterman_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 | ||
50 | template<typename Graph, typename PositionMap, typename Topology> | |
51 | void | |
52 | fruchterman_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 | |
60 | HREF="bibliography.html#fruchterman91">58</A>] performs layout of | |
61 | unweighted, undirected graphs. Unlike the <a | |
62 | href="kamada_kawai_spring_layout.html">Kamada-Kawai</a> layout | |
63 | algorithm, this algorithm directly supports the layout of disconnected | |
64 | graphs (but see the <tt>force_pairs</tt> named parameter). It is a | |
65 | <em>force-directed</em> algorithm, meaning that vertex layout is | |
66 | determined by the forces pulling vertices together and pushing them | |
67 | apart. Attractive forces occur between adjacent vertices only, whereas | |
68 | repulsive forces occur between every pair of vertices. Each iteration | |
69 | computes the sum of the forces on each vertex, then moves the vertices | |
70 | to their new positions. The movement of vertices is mitigated by the | |
71 | <i>temperature</i> of the system for that iteration: as the algorithm | |
72 | progresses through successive iterations, the temperature should | |
73 | decrease so that vertices settle in place. The cooling schedule, | |
74 | attractive 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 | ||
84 | IN: <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 | ||
92 | IN/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 | ||
108 | IN: <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 | ||
118 | IN: <tt>attractive_force(AttractiveForce fa)</tt> | |
119 | <blockquote> | |
120 | Computes the magnitude of the attractive force between two adjacent | |
121 | vertices. The function object <tt>fa</tt> must accept four | |
122 | parameters: the edge descriptor, <tt>k</tt>, the distance between the | |
123 | vertices, and the graph. <tt>k</tt> is the square root of the ratio | |
124 | of the display area to the number of vertices. <br> | |
125 | <b>Default:</b> <tt>square_distance_attractive_force()</tt>, which | |
126 | computes 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 | ||
130 | IN: <tt>repulsive_force(RepulsiveForce fr)</tt> | |
131 | <blockquote> | |
132 | Computes the magnitude of the repulsive force between any two | |
133 | vertices. The function object <tt>fa</tt> must accept five | |
134 | parameters: the two vertex descriptors, <tt>k</tt>, the distance between the | |
135 | vertices, and the graph. <tt>k</tt> is the square root of the ratio | |
136 | of the display area to the number of vertices. <br> | |
137 | <b>Default:</b> <tt>square_distance_repsulsive_force()</tt>, which | |
138 | computes 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 | ||
142 | IN: <tt>force_pairs(ForcePairs fp)</tt> | |
143 | <blockquote> | |
144 | Enumerates the pairs of vertices on which the repulsive force should | |
145 | be applied. <tt>fp</tt> is a function object taking two parameters: | |
146 | the graph <tt>g</tt> and a binary function object that should be | |
147 | passed each pair of vertices to be considered. The basic formulation | |
148 | of the Fruchterman-Reingold algorithm computes repulsive forces | |
149 | between all pairs of vertices (pass <tt>all_force_pairs()</tt> for | |
150 | this parameter), which is functional for disconnected graphs but | |
151 | tends to push the connected components toward the edges of the | |
152 | display area. The grid variant of the algorithm places a grid over | |
153 | the display area and only computes repulsive forces among vertices | |
154 | within each rectangle in the grid. The grid variant can be more | |
155 | efficient than the basic formulation and tends to produce better | |
156 | layouts for disconnected graphs, but is not better overall: pass | |
157 | <tt>make_grid_force_pairs(width, height, position, g)</tt> as this | |
158 | parameter to use the grid variant. Other enumeration strategies may | |
159 | yield 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 | ||
164 | IN: <tt>cooling(Cooling cool)</tt> | |
165 | <blockquote> | |
166 | Determines the cooling schedule for the algorithm, which affects the | |
167 | rate of movement of vertices and termination of the algorithm. The | |
168 | <tt>cool</tt> parameter is a nullary function object (i.e., one that | |
169 | takes no arguments) and returns the temperature for the current | |
170 | iteration. When the returned temperature is zero, the algorithm | |
171 | terminates. Cooling schedules should begin with some initial | |
172 | temperature 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 | ||
177 | UTIL: <tt>displacement_map(DisplacementMap displacement)</tt> | |
178 | <blockquote> | |
179 | The displacement map is used to compute the amount by which each | |
180 | vertex will move in each step. The <tt>DisplacementMap</tt> type must be a | |
181 | property 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 | |
184 | and using the given vertex index map.<br> | |
185 | <b>Python:</b> Unsupported parameter. | |
186 | </blockquote> | |
187 | ||
188 | IN: <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 | |
219 | iteration of the algorithm in the worst case. The average case for the | |
220 | grid variant is <i>O(|V| + |E|)</i>. The number of iterations is | |
221 | determined 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> |