236 lines
9.7 KiB
HTML
236 lines
9.7 KiB
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<typename Graph, typename PositionMap, typename Topology, typename Param,
|
|
typename Tag, typename Rest>
|
|
void
|
|
fruchterman_reingold_force_directed_layout
|
|
(const Graph& g,
|
|
PositionMap position,
|
|
const Topology& space,
|
|
const bgl_named_params<Param, Tag, Rest>& params);
|
|
|
|
<i>// non-named parameter version</i>
|
|
template<typename Graph, typename PositionMap, typename Topology,
|
|
typename AttractiveForce, typename RepulsiveForce,
|
|
typename ForcePairs, typename DisplacementMap, typename Cooling>
|
|
void
|
|
fruchterman_reingold_force_directed_layout
|
|
(const Graph& g,
|
|
PositionMap position,
|
|
const Topology& space,
|
|
AttractiveForce fa,
|
|
RepulsiveForce fr,
|
|
ForcePairs fp,
|
|
Cooling cool,
|
|
DisplacementMap displacement);
|
|
|
|
template<typename Graph, typename PositionMap, typename Topology>
|
|
void
|
|
fruchterman_reingold_force_directed_layout(const Graph& g,
|
|
PositionMap position,
|
|
Topology& space,
|
|
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/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& 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>fr</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 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 © 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>
|