123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323 |
- <!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>
|