324 lines
14 KiB
HTML
324 lines
14 KiB
HTML
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
|
|
<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>
|
|
<meta name="generator" content=
|
|
"HTML Tidy for Mac OS X (vers 12 April 2005), see www.w3.org">
|
|
<meta http-equiv="Content-Type" content=
|
|
"text/html; charset=us-ascii">
|
|
<title>Function kamada_kawai_spring_layout</title>
|
|
</head>
|
|
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084"
|
|
alink="#0000FF">
|
|
<table cellpadding="2" width="100%">
|
|
<tr>
|
|
<td valign="top"><img src="../../../boost.png" alt=
|
|
"boost.png (6897 bytes)" width="277" height="86"></td>
|
|
<td align="center"><a href="../../../index.htm">Home</a></td>
|
|
<td align="center"><a href="../../libraries.htm">Libraries</a></td>
|
|
<td align="center"><a href=
|
|
"http://www.boost.org/people/people.htm">People</a></td>
|
|
<td align="center"><a href="http://www.boost.org/more/faq.htm">FAQ</a></td>
|
|
<td align="center"><a href="../../../more/index.htm">More</a></td>
|
|
</tr>
|
|
</table>
|
|
<hr>
|
|
<div class="refentry" lang="en"><a name="id103831-bb" id=
|
|
"id103831-bb"></a>
|
|
<div class="titlepage"></div>
|
|
<div class="refnamediv">
|
|
<h2><img src="figs/python.gif" alt="(Python)"><span class=
|
|
"refentrytitle">Function kamada_kawai_spring_layout</span></h2>
|
|
<p>boost::kamada_kawai_spring_layout — Kamada-Kawai spring
|
|
layout for connected, undirected graphs.</p>
|
|
</div>
|
|
<h2 xmlns:rev=
|
|
"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class=
|
|
"refsynopsisdiv-title">Synopsis</h2>
|
|
<div xmlns:rev=
|
|
"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class=
|
|
"refsynopsisdiv">
|
|
<pre class="synopsis">
|
|
<span class="bold"><b>template</b></span><<span class=
|
|
"bold"><b>typename</b></span> Topology, <span class=
|
|
"bold"><b>typename</b></span> Graph, <span class=
|
|
"bold"><b>typename</b></span> PositionMap, <span class=
|
|
"bold"><b>typename</b></span> WeightMap, <span class=
|
|
"bold"><b>typename</b></span> T,
|
|
<span class=
|
|
"bold"><b>bool</b></span> EdgeOrSideLength, <span class=
|
|
"bold"><b>typename</b></span> Done, <span class=
|
|
"bold"><b>typename</b></span> VertexIndexMap,
|
|
<span class=
|
|
"bold"><b>typename</b></span> DistanceMatrix, <span class=
|
|
"bold"><b>typename</b></span> SpringStrengthMatrix,
|
|
<span class=
|
|
"bold"><b>typename</b></span> PartialDerivativeMap>
|
|
<span class="type"><span class=
|
|
"bold"><b>bool</b></span></span> kamada_kawai_spring_layout(<span class="bold"><b>const</b></span> Graph & g, PositionMap position,
|
|
WeightMap weight,
|
|
<b>const</b> Topology& space,
|
|
<span class=
|
|
"emphasis"><em>unspecified</em></span> edge_or_side_length, Done done,
|
|
<span class=
|
|
"bold"><b>typename</b></span> property_traits< WeightMap >::value_type spring_constant,
|
|
VertexIndexMap index,
|
|
DistanceMatrix distance,
|
|
SpringStrengthMatrix spring_strength,
|
|
PartialDerivativeMap partial_derivatives);
|
|
<span class="bold"><b>template</b></span><<span class=
|
|
"bold"><b>typename</b></span> Topology, <span class=
|
|
"bold"><b>typename</b></span> Graph, <span class=
|
|
"bold"><b>typename</b></span> PositionMap, <span class=
|
|
"bold"><b>typename</b></span> WeightMap, <span class=
|
|
"bold"><b>typename</b></span> T,
|
|
<span class=
|
|
"bold"><b>bool</b></span> EdgeOrSideLength, <span class=
|
|
"bold"><b>typename</b></span> Done, <span class=
|
|
"bold"><b>typename</b></span> VertexIndexMap>
|
|
<span class="type"><span class=
|
|
"bold"><b>bool</b></span></span> kamada_kawai_spring_layout(<span class="bold"><b>const</b></span> Graph & g, PositionMap position,
|
|
WeightMap weight,
|
|
<b>const</b> Topology& space,
|
|
<span class=
|
|
"emphasis"><em>unspecified</em></span> edge_or_side_length, Done done,
|
|
<span class=
|
|
"bold"><b>typename</b></span> property_traits< WeightMap >::value_type spring_constant,
|
|
VertexIndexMap index);
|
|
<span class="bold"><b>template</b></span><<span class=
|
|
"bold"><b>typename</b></span> Topology, <span class=
|
|
"bold"><b>typename</b></span> Graph, <span class=
|
|
"bold"><b>typename</b></span> PositionMap, <span class=
|
|
"bold"><b>typename</b></span> WeightMap, <span class=
|
|
"bold"><b>typename</b></span> T,
|
|
<span class=
|
|
"bold"><b>bool</b></span> EdgeOrSideLength, <span class=
|
|
"bold"><b>typename</b></span> Done>
|
|
<span class="type"><span class=
|
|
"bold"><b>bool</b></span></span> kamada_kawai_spring_layout(<span class="bold"><b>const</b></span> Graph & g, PositionMap position,
|
|
WeightMap weight,
|
|
<b>const</b> Topology& space,
|
|
<span class=
|
|
"emphasis"><em>unspecified</em></span> edge_or_side_length, Done done,
|
|
<span class=
|
|
"bold"><b>typename</b></span> property_traits< WeightMap >::value_type spring_constant = typename property_traits< WeightMap >::value_type(1));
|
|
<span class="bold"><b>template</b></span><<span class=
|
|
"bold"><b>typename</b></span> Topology, <span class=
|
|
"bold"><b>typename</b></span> Graph, <span class=
|
|
"bold"><b>typename</b></span> PositionMap, <span class=
|
|
"bold"><b>typename</b></span> WeightMap, <span class=
|
|
"bold"><b>typename</b></span> T,
|
|
<span class=
|
|
"bold"><b>bool</b></span> EdgeOrSideLength>
|
|
<span class="type"><span class=
|
|
"bold"><b>bool</b></span></span> kamada_kawai_spring_layout(<span class="bold"><b>const</b></span> Graph & g, PositionMap position,
|
|
WeightMap weight,
|
|
<b>const</b> Topology& space,
|
|
<span class=
|
|
"emphasis"><em>unspecified</em></span> edge_or_side_length);
|
|
</pre></div>
|
|
<div class="refsect1" lang="en"><a name="id822881" id=
|
|
"id822881"></a>
|
|
<h2>Where Defined</h2>
|
|
<a href=
|
|
"../../../boost/graph/kamada_kawai_spring_layout.hpp">boost/graph/kamada_kawai_spring_layout.hpp</a>
|
|
|
|
<h2>Description</h2>
|
|
<p>This algorithm [<a href=
|
|
"bibliography.html#kamada89">57</a>] performs graph layout (in two
|
|
dimensions) for connected, undirected graphs. It operates by
|
|
relating the layout of graphs to a dynamic spring system and
|
|
minimizing the energy within that system. The strength of a spring
|
|
between two vertices is inversely proportional to the square of the
|
|
shortest distance (in graph terms) between those two vertices.
|
|
Essentially, vertices that are closer in the graph-theoretic sense
|
|
(i.e., by following edges) will have stronger springs and will
|
|
therefore be placed closer together.</p>
|
|
<p>Prior to invoking this algorithm, it is recommended that the
|
|
vertices be placed along the vertices of a regular n-sided polygon
|
|
via <a href="circle_layout.html"><tt>circle_layout</tt></a>.</p>
|
|
<p><b xmlns:rev=
|
|
"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision"><span class="term">
|
|
Returns</span></b>: <tt class="computeroutput">true</tt> if layout
|
|
was successful or <tt class="computeroutput">false</tt> if a
|
|
negative weight cycle was detected or the graph is
|
|
disconnected.</p>
|
|
|
|
<h2>Parameters</h2>
|
|
IN: <tt>const Graph& g</tt>
|
|
<blockquote>
|
|
The graph, whose type <tt>Graph</tt> must model the
|
|
<a href="VertexListGraph.html">VertexListGraph</a>,
|
|
<a href="EdgeListGraph.html">EdgeListGraph</a>, and
|
|
<a href="IncidenceGraph.html">IncidenceGraph</a> concepts. The
|
|
graph must be undirected and connected. <br>
|
|
<b>Python</b>: This parameter is named <tt>graph</tt> in Python.
|
|
</blockquote>
|
|
|
|
OUT: <tt>PositionMap position</tt>
|
|
<blockquote>
|
|
This property map is used to store the position of each vertex. The
|
|
type <tt>PositionMap</tt> must be a model of <a
|
|
href="../../property_map/doc/WritablePropertyMap.html">Writable Property
|
|
Map</a>, with the graph's vertex descriptor type as its key type and
|
|
<tt>Topology::point_type</tt> as its value type.<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>weight_map(WeightMap w_map)</tt>
|
|
<blockquote>
|
|
The weight or ``length'' of each edge in the graph. The weights
|
|
must all be non-negative, and the algorithm will throw a
|
|
<a href="./exception.html#negative_edge"><tt>negative_edge</tt></a>
|
|
exception is one of the edges is negative.
|
|
The type <tt>WeightMap</tt> must be a model of
|
|
<a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The edge descriptor type of
|
|
the graph needs to be usable as the key type for the weight
|
|
map. The value type for this map must be
|
|
the same as the value type of the distance map.<br>
|
|
<b>Default:</b> <tt>get(edge_weight, g)</tt><br>
|
|
|
|
<b>Python</b>: Must be an <tt>edge_double_map</tt> for the graph.<br>
|
|
<b>Python default</b>: <tt>graph.get_edge_double_map("weight")</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, as well as its dimensionality; up to three
|
|
dimensions are supported by the current implementation. Topologies are
|
|
described in more detail
|
|
(with a list of BGL-provided topologies) <a href="topology.html">in separate
|
|
documentation</a>.
|
|
</blockquote>
|
|
|
|
IN: <tt>EdgeOrSideLength edge_or_side_length</tt>
|
|
<blockquote>
|
|
Provides either the unit length <tt class= "computeroutput">e</tt> of
|
|
an edge in the layout or the length of a side <tt
|
|
class="computeroutput">s</tt> of the display area, and must be
|
|
either <tt class= "computeroutput">boost::edge_length(e)</tt> or <tt
|
|
class= "computeroutput">boost::side_length(s)</tt> , respectively.
|
|
<b>Python</b>: In Python, this value always refers to the side length
|
|
and may only be a <tt>double</tt>.
|
|
</blockquote>
|
|
|
|
IN: <tt>Done done</tt>
|
|
<blockquote>
|
|
A 4-argument function object that is passed the current
|
|
value of delta_p (i.e., the energy of vertex <tt class=
|
|
"computeroutput">p</tt> ), the vertex <tt class=
|
|
"computeroutput">p</tt> , the graph <tt class=
|
|
"computeroutput">g</tt> , and a boolean flag indicating whether
|
|
<tt class="computeroutput">delta_p</tt> is the maximum energy in
|
|
the system (when <tt class="computeroutput">true</tt> ) or the
|
|
energy of the vertex being moved.
|
|
<b>Default</b>: <a href=
|
|
"layout_tolerance.html"><tt class=
|
|
"computeroutput">layout_tolerance</tt></a> instantiated over the
|
|
value type of the weight map.<br>
|
|
<b>Python</b>: Any callable Python object with an appropriate signature suffices.
|
|
</blockquote>
|
|
|
|
IN: <tt>typename property_traits<WeightMap>::value_type spring_constant</tt>
|
|
<blockquote>
|
|
The constant multiplied by each spring's strength.
|
|
Larger values create systems with more energy that can take longer
|
|
to stabilize; smaller values create systems with less energy that
|
|
stabilize quickly but do not necessarily result in pleasing
|
|
layouts.<br>
|
|
<b>Default</b>: 1.
|
|
</blockquote>
|
|
|
|
IN: <tt>VertexIndexMap index</tt>
|
|
<blockquote>
|
|
As a mapping from vertices to index values between 0 and
|
|
<tt class="computeroutput">num_vertices(g)</tt> .<br>
|
|
<b>Default</b>:<tt class="computeroutput">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>
|
|
|
|
UTIL/OUT: <tt>DistanceMap distance</tt>
|
|
<blockquote>
|
|
This parameter will be used to store the distance from every vertex to
|
|
every other vertex, which is computed in the first stages of the
|
|
algorithm. This value's type must be a model of <a
|
|
href="BasicMatrix.html"><tt>BasicMatrix</tt></a> with value type equal to
|
|
the value type of the weight map.<br>
|
|
<b>Default</b>: A vector of vectors.<br>
|
|
<b>Python</b>: Unsupported parameter.
|
|
</blockquote>
|
|
|
|
UTIL/OUT: <tt>SpringStrengthMatrix spring_strength</tt>
|
|
<blockquote>
|
|
|
|
This matrix will be used to store the strength of the spring between
|
|
every pair of vertices. This value's type must be a model of <a
|
|
href="BasicMatrix.html">BasicMatrix</a> with value type equal to the
|
|
value type of the weight map.<br>
|
|
<b>Default</b>: A vector of vectors of the value type of the weight map.<br>
|
|
<b>Python</b>: Unsupported parameter.
|
|
</blockquote>
|
|
|
|
UTIL: <tt>PartialDerivativeMap partial_derivatives</tt>
|
|
<blockquote>
|
|
A property map that will be used to store the partial derivatives of
|
|
each vertex with respect to the vertex's current coordinates.
|
|
coordinates. This must be a
|
|
<a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
|
|
Property Map</a> whose value type is <tt>Topology::point_difference_type</tt>.
|
|
The default is an iterator property map built using the graph's vertex index
|
|
map.<br>
|
|
<b>Default</b>: An <tt>iterator_property_map</tt> created from
|
|
an <tt>std::vector</tt> of <tt>Topology::point_difference_type</tt>.<br>
|
|
<b>Python</b>: Unsupported parameter.
|
|
</blockquote>
|
|
|
|
<b>Python</b> IN: <tt>bool progressive</tt>
|
|
<blockquote>
|
|
When <tt>false</tt>, performs layout of the graph on a circle before
|
|
running the Kamada-Kawai 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>
|
|
|
|
</div>
|
|
</div>
|
|
</div>
|
|
<table xmlns:rev=
|
|
"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width=
|
|
"100%">
|
|
<tr>
|
|
<td align="left"></td>
|
|
<td align="right"></td>
|
|
</tr>
|
|
</table>
|
|
<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">Douglas Gregor</a>,
|
|
Indiana University (dgregor -at cs.indiana.edu)<br>
|
|
<a href="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</a>, Indiana
|
|
University (<a href=
|
|
"mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>)</td>
|
|
</tr>
|
|
</table>
|
|
</body>
|
|
</html>
|