<!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>adjacenty_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="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</a>, Indiana University (<a href= "mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>)</td> </tr> </table> </body> </html>