1<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> 2<html> 3<!-- 4 Copyright (c) 2004, 2010 Trustees of Indiana University 5 6 Distributed under the Boost Software License, Version 1.0. 7 (See accompanying file LICENSE_1_0.txt or copy at 8 http://www.boost.org/LICENSE_1_0.txt) 9 --> 10<head> 11<meta name="generator" content= 12"HTML Tidy for Mac OS X (vers 12 April 2005), see www.w3.org"> 13<meta http-equiv="Content-Type" content= 14"text/html; charset=us-ascii"> 15<title>Function kamada_kawai_spring_layout</title> 16</head> 17<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" 18alink="#0000FF"> 19<table cellpadding="2" width="100%"> 20<tr> 21<td valign="top"><img src="../../../boost.png" alt= 22"boost.png (6897 bytes)" width="277" height="86"></td> 23<td align="center"><a href="../../../index.htm">Home</a></td> 24<td align="center"><a href="../../libraries.htm">Libraries</a></td> 25<td align="center"><a href= 26"http://www.boost.org/people/people.htm">People</a></td> 27<td align="center"><a href="http://www.boost.org/more/faq.htm">FAQ</a></td> 28<td align="center"><a href="../../../more/index.htm">More</a></td> 29</tr> 30</table> 31<hr> 32<div class="refentry" lang="en"><a name="id103831-bb" id= 33"id103831-bb"></a> 34<div class="titlepage"></div> 35<div class="refnamediv"> 36<h2><img src="figs/python.gif" alt="(Python)"><span class= 37"refentrytitle">Function kamada_kawai_spring_layout</span></h2> 38<p>boost::kamada_kawai_spring_layout — Kamada-Kawai spring 39layout for connected, undirected graphs.</p> 40</div> 41<h2 xmlns:rev= 42"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class= 43"refsynopsisdiv-title">Synopsis</h2> 44<div xmlns:rev= 45"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" class= 46"refsynopsisdiv"> 47<pre class="synopsis"> 48<span class="bold"><b>template</b></span><<span class= 49"bold"><b>typename</b></span> Topology, <span class= 50"bold"><b>typename</b></span> Graph, <span class= 51"bold"><b>typename</b></span> PositionMap, <span class= 52"bold"><b>typename</b></span> WeightMap, <span class= 53"bold"><b>typename</b></span> T, 54 <span class= 55"bold"><b>bool</b></span> EdgeOrSideLength, <span class= 56"bold"><b>typename</b></span> Done, <span class= 57"bold"><b>typename</b></span> VertexIndexMap, 58 <span class= 59"bold"><b>typename</b></span> DistanceMatrix, <span class= 60"bold"><b>typename</b></span> SpringStrengthMatrix, 61 <span class= 62"bold"><b>typename</b></span> PartialDerivativeMap> 63 <span class="type"><span class= 64"bold"><b>bool</b></span></span> kamada_kawai_spring_layout(<span class="bold"><b>const</b></span> Graph & g, PositionMap position, 65 WeightMap weight, 66 <b>const</b> Topology& space, 67 <span class= 68"emphasis"><em>unspecified</em></span> edge_or_side_length, Done done, 69 <span class= 70"bold"><b>typename</b></span> property_traits< WeightMap >::value_type spring_constant, 71 VertexIndexMap index, 72 DistanceMatrix distance, 73 SpringStrengthMatrix spring_strength, 74 PartialDerivativeMap partial_derivatives); 75<span class="bold"><b>template</b></span><<span class= 76"bold"><b>typename</b></span> Topology, <span class= 77"bold"><b>typename</b></span> Graph, <span class= 78"bold"><b>typename</b></span> PositionMap, <span class= 79"bold"><b>typename</b></span> WeightMap, <span class= 80"bold"><b>typename</b></span> T, 81 <span class= 82"bold"><b>bool</b></span> EdgeOrSideLength, <span class= 83"bold"><b>typename</b></span> Done, <span class= 84"bold"><b>typename</b></span> VertexIndexMap> 85 <span class="type"><span class= 86"bold"><b>bool</b></span></span> kamada_kawai_spring_layout(<span class="bold"><b>const</b></span> Graph & g, PositionMap position, 87 WeightMap weight, 88 <b>const</b> Topology& space, 89 <span class= 90"emphasis"><em>unspecified</em></span> edge_or_side_length, Done done, 91 <span class= 92"bold"><b>typename</b></span> property_traits< WeightMap >::value_type spring_constant, 93 VertexIndexMap index); 94<span class="bold"><b>template</b></span><<span class= 95"bold"><b>typename</b></span> Topology, <span class= 96"bold"><b>typename</b></span> Graph, <span class= 97"bold"><b>typename</b></span> PositionMap, <span class= 98"bold"><b>typename</b></span> WeightMap, <span class= 99"bold"><b>typename</b></span> T, 100 <span class= 101"bold"><b>bool</b></span> EdgeOrSideLength, <span class= 102"bold"><b>typename</b></span> Done> 103 <span class="type"><span class= 104"bold"><b>bool</b></span></span> kamada_kawai_spring_layout(<span class="bold"><b>const</b></span> Graph & g, PositionMap position, 105 WeightMap weight, 106 <b>const</b> Topology& space, 107 <span class= 108"emphasis"><em>unspecified</em></span> edge_or_side_length, Done done, 109 <span class= 110"bold"><b>typename</b></span> property_traits< WeightMap >::value_type spring_constant = typename property_traits< WeightMap >::value_type(1)); 111<span class="bold"><b>template</b></span><<span class= 112"bold"><b>typename</b></span> Topology, <span class= 113"bold"><b>typename</b></span> Graph, <span class= 114"bold"><b>typename</b></span> PositionMap, <span class= 115"bold"><b>typename</b></span> WeightMap, <span class= 116"bold"><b>typename</b></span> T, 117 <span class= 118"bold"><b>bool</b></span> EdgeOrSideLength> 119 <span class="type"><span class= 120"bold"><b>bool</b></span></span> kamada_kawai_spring_layout(<span class="bold"><b>const</b></span> Graph & g, PositionMap position, 121 WeightMap weight, 122 <b>const</b> Topology& space, 123 <span class= 124"emphasis"><em>unspecified</em></span> edge_or_side_length); 125</pre></div> 126<div class="refsect1" lang="en"><a name="id822881" id= 127"id822881"></a> 128<h2>Where Defined</h2> 129<a href= 130"../../../boost/graph/kamada_kawai_spring_layout.hpp">boost/graph/kamada_kawai_spring_layout.hpp</a> 131 132<h2>Description</h2> 133<p>This algorithm [<a href= 134"bibliography.html#kamada89">57</a>] performs graph layout (in two 135dimensions) for connected, undirected graphs. It operates by 136relating the layout of graphs to a dynamic spring system and 137minimizing the energy within that system. The strength of a spring 138between two vertices is inversely proportional to the square of the 139shortest distance (in graph terms) between those two vertices. 140Essentially, vertices that are closer in the graph-theoretic sense 141(i.e., by following edges) will have stronger springs and will 142therefore be placed closer together.</p> 143<p>Prior to invoking this algorithm, it is recommended that the 144vertices be placed along the vertices of a regular n-sided polygon 145via <a href="circle_layout.html"><tt>circle_layout</tt></a>.</p> 146<p><b xmlns:rev= 147"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision"><span class="term"> 148Returns</span></b>: <tt class="computeroutput">true</tt> if layout 149was successful or <tt class="computeroutput">false</tt> if a 150negative weight cycle was detected or the graph is 151disconnected.</p> 152 153<h2>Parameters</h2> 154IN: <tt>const Graph& g</tt> 155<blockquote> 156 The graph, whose type <tt>Graph</tt> must model the 157 <a href="VertexListGraph.html">VertexListGraph</a>, 158 <a href="EdgeListGraph.html">EdgeListGraph</a>, and 159 <a href="IncidenceGraph.html">IncidenceGraph</a> concepts. The 160 graph must be undirected and connected. <br> 161 <b>Python</b>: This parameter is named <tt>graph</tt> in Python. 162</blockquote> 163 164OUT: <tt>PositionMap position</tt> 165<blockquote> 166 This property map is used to store the position of each vertex. The 167 type <tt>PositionMap</tt> must be a model of <a 168 href="../../property_map/doc/WritablePropertyMap.html">Writable Property 169 Map</a>, with the graph's vertex descriptor type as its key type and 170 <tt>Topology::point_type</tt> as its value type.<br> 171 172 <b>Python</b>: The position map must be a <tt>vertex_point2d_map</tt> for 173 the graph.<br> 174 <b>Python default</b>: <tt>graph.get_vertex_point2d_map("position")</tt> 175</blockquote> 176 177IN: <tt>weight_map(WeightMap w_map)</tt> 178<blockquote> 179 The weight or ``length'' of each edge in the graph. The weights 180 must all be non-negative, and the algorithm will throw a 181 <a href="./exception.html#negative_edge"><tt>negative_edge</tt></a> 182 exception is one of the edges is negative. 183 The type <tt>WeightMap</tt> must be a model of 184 <a href="../../property_map/doc/ReadablePropertyMap.html">Readable Property Map</a>. The edge descriptor type of 185 the graph needs to be usable as the key type for the weight 186 map. The value type for this map must be 187 the same as the value type of the distance map.<br> 188 <b>Default:</b> <tt>get(edge_weight, g)</tt><br> 189 190 <b>Python</b>: Must be an <tt>edge_double_map</tt> for the graph.<br> 191 <b>Python default</b>: <tt>graph.get_edge_double_map("weight")</tt> 192</blockquote> 193 194IN: <tt>const Topology& space</tt> 195<blockquote> 196The topology used to lay out the vertices. This parameter describes both the 197size and shape of the layout area, as well as its dimensionality; up to three 198dimensions are supported by the current implementation. Topologies are 199described in more detail 200(with a list of BGL-provided topologies) <a href="topology.html">in separate 201documentation</a>. 202</blockquote> 203 204IN: <tt>EdgeOrSideLength edge_or_side_length</tt> 205<blockquote> 206Provides either the unit length <tt class= "computeroutput">e</tt> of 207an edge in the layout or the length of a side <tt 208class="computeroutput">s</tt> of the display area, and must be 209either <tt class= "computeroutput">boost::edge_length(e)</tt> or <tt 210class= "computeroutput">boost::side_length(s)</tt> , respectively. 211<b>Python</b>: In Python, this value always refers to the side length 212and may only be a <tt>double</tt>. 213</blockquote> 214 215IN: <tt>Done done</tt> 216<blockquote> 217A 4-argument function object that is passed the current 218value of delta_p (i.e., the energy of vertex <tt class= 219"computeroutput">p</tt> ), the vertex <tt class= 220"computeroutput">p</tt> , the graph <tt class= 221"computeroutput">g</tt> , and a boolean flag indicating whether 222<tt class="computeroutput">delta_p</tt> is the maximum energy in 223the system (when <tt class="computeroutput">true</tt> ) or the 224energy of the vertex being moved. 225<b>Default</b>: <a href= 226"layout_tolerance.html"><tt class= 227"computeroutput">layout_tolerance</tt></a> instantiated over the 228value type of the weight map.<br> 229<b>Python</b>: Any callable Python object with an appropriate signature suffices. 230</blockquote> 231 232IN: <tt>typename property_traits<WeightMap>::value_type spring_constant</tt> 233<blockquote> 234The constant multiplied by each spring's strength. 235Larger values create systems with more energy that can take longer 236to stabilize; smaller values create systems with less energy that 237stabilize quickly but do not necessarily result in pleasing 238layouts.<br> 239<b>Default</b>: 1. 240</blockquote> 241 242IN: <tt>VertexIndexMap index</tt> 243<blockquote> 244As a mapping from vertices to index values between 0 and 245<tt class="computeroutput">num_vertices(g)</tt> .<br> 246<b>Default</b>:<tt class="computeroutput">get(vertex_index,g)</tt>. 247 Note: if you use this default, make sure your graph has 248 an internal <tt>vertex_index</tt> property. For example, 249 <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does 250 not have an internal <tt>vertex_index</tt> property. 251 <br> 252<b>Python</b>: Unsupported parameter. 253</blockquote> 254 255UTIL/OUT: <tt>DistanceMap distance</tt> 256<blockquote> 257This parameter will be used to store the distance from every vertex to 258every other vertex, which is computed in the first stages of the 259algorithm. This value's type must be a model of <a 260href="BasicMatrix.html"><tt>BasicMatrix</tt></a> with value type equal to 261the value type of the weight map.<br> 262<b>Default</b>: A vector of vectors.<br> 263<b>Python</b>: Unsupported parameter. 264</blockquote> 265 266UTIL/OUT: <tt>SpringStrengthMatrix spring_strength</tt> 267<blockquote> 268 269This matrix will be used to store the strength of the spring between 270every pair of vertices. This value's type must be a model of <a 271href="BasicMatrix.html">BasicMatrix</a> with value type equal to the 272value type of the weight map.<br> 273<b>Default</b>: A vector of vectors of the value type of the weight map.<br> 274<b>Python</b>: Unsupported parameter. 275</blockquote> 276 277UTIL: <tt>PartialDerivativeMap partial_derivatives</tt> 278<blockquote> 279A property map that will be used to store the partial derivatives of 280each vertex with respect to the vertex's current coordinates. 281coordinates. This must be a 282<a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write 283Property Map</a> whose value type is <tt>Topology::point_difference_type</tt>. 284The default is an iterator property map built using the graph's vertex index 285map.<br> 286<b>Default</b>: An <tt>iterator_property_map</tt> created from 287an <tt>std::vector</tt> of <tt>Topology::point_difference_type</tt>.<br> 288<b>Python</b>: Unsupported parameter. 289</blockquote> 290 291<b>Python</b> IN: <tt>bool progressive</tt> 292<blockquote> 293 When <tt>false</tt>, performs layout of the graph on a circle before 294 running the Kamada-Kawai algorithm. If <tt>true</tt>, the algorithm 295 is executing starting with the vertex configuration in 296 the <tt>position</tt> map.<br> 297 <b>Default</b>: <tt>False</tt>. 298</blockquote> 299 300</div> 301</div> 302</div> 303<table xmlns:rev= 304"http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width= 305"100%"> 306<tr> 307<td align="left"></td> 308<td align="right"></td> 309</tr> 310</table> 311<hr> 312<table> 313<tr valign="top"> 314<td nowrap>Copyright © 2004, 2010 Trustees of Indiana University</td> 315<td><a href="http://www.boost.org/people/doug_gregor.html">Douglas Gregor</a>, 316Indiana University (dgregor -at cs.indiana.edu)<br> 317<a href="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</a>, Indiana 318University (<a href= 319"mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>)</td> 320</tr> 321</table> 322</body> 323</html> 324
