[ceph.git] / ceph / src / boost / libs / graph / doc / fruchterman_reingold.html

<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&lt;typename Graph, typename PositionMap, typename Topology, typename Param,
	 typename Tag, typename Rest&gt;
void
fruchterman_reingold_force_directed_layout
  (const Graph&amp;    g,
   PositionMap     position,
   const Topology&amp;     space,
   const bgl_named_params&lt;Param, Tag, Rest&gt;&amp; params);

<i>// non-named parameter version</i>
template&lt;typename Graph, typename PositionMap, typename Topology,
         typename AttractiveForce, typename RepulsiveForce,
         typename ForcePairs, typename DisplacementMap, typename Cooling&gt;
void
fruchterman_reingold_force_directed_layout
 (const Graph&amp;    g,
  PositionMap     position,
  const Topology&amp; space,
  AttractiveForce fa,
  RepulsiveForce  fr,
  ForcePairs      fp,
  Cooling         cool,
  DisplacementMap displacement);

template&lt;typename Graph, typename PositionMap, typename Topology&gt;
void
fruchterman_reingold_force_directed_layout(const Graph&amp;    g,
			     		   PositionMap     position,
			     		   Topology&amp;     space,
			     		   Dim             width,
			     		   Dim             height);
</PRE>

<P> This algorithm&nbsp;[<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&amp; 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&amp; 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&lt;double&gt;(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>adjacency_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 worst 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 &copy; 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>
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>