ceph/src/boost/libs/graph/doc/kamada_kawai_spring_layout.html

   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"
  18 alink="#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 &mdash; Kamada-Kawai spring
  39 layout 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>&lt;<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&gt;
  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 &amp; g, PositionMap position,
  65                                   WeightMap weight,
  66                                   <b>const</b> Topology&amp; 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&lt; WeightMap &gt;::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>&lt;<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&gt;
  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 &amp; g, PositionMap position,
  87                                   WeightMap weight,
  88                                   <b>const</b> Topology&amp; 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&lt; WeightMap &gt;::value_type spring_constant,
  93                                   VertexIndexMap index);
  94 <span class="bold"><b>template</b></span>&lt;<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&gt;
 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 &amp; g, PositionMap position,
 105                                   WeightMap weight,
 106                                   <b>const</b> Topology&amp; 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&lt; WeightMap &gt;::value_type spring_constant = typename property_traits&lt; WeightMap &gt;::value_type(1));
 111 <span class="bold"><b>template</b></span>&lt;<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&gt;
 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 &amp; g, PositionMap position,
 121                                   WeightMap weight,
 122                                   <b>const</b> Topology&amp; 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&nbsp;[<a href=
 134 "bibliography.html#kamada89">57</a>] performs graph layout (in two
 135 dimensions) for connected, undirected graphs. It operates by
 136 relating the layout of graphs to a dynamic spring system and
 137 minimizing the energy within that system. The strength of a spring
 138 between two vertices is inversely proportional to the square of the
 139 shortest distance (in graph terms) between those two vertices.
 140 Essentially, vertices that are closer in the graph-theoretic sense
 141 (i.e., by following edges) will have stronger springs and will
 142 therefore be placed closer together.</p>
 143 <p>Prior to invoking this algorithm, it is recommended that the
 144 vertices be placed along the vertices of a regular n-sided polygon
 145 via <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">
 148 Returns</span></b>: <tt class="computeroutput">true</tt> if layout
 149 was successful or <tt class="computeroutput">false</tt> if a
 150 negative weight cycle was detected or the graph is
 151 disconnected.</p>
 152
 153 <h2>Parameters</h2>
 154 IN: <tt>const Graph&amp; 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
 164 OUT: <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
 177 IN: <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
 194 IN: <tt>const Topology&amp; space</tt>
 195 <blockquote>
 196 The topology used to lay out the vertices.  This parameter describes both the
 197 size and shape of the layout area, as well as its dimensionality; up to three
 198 dimensions are supported by the current implementation.  Topologies are
 199 described in more detail
 200 (with a list of BGL-provided topologies) <a href="topology.html">in separate
 201 documentation</a>.
 202 </blockquote>
 203
 204 IN: <tt>EdgeOrSideLength edge_or_side_length</tt>
 205 <blockquote>
 206 Provides either the unit length <tt class= "computeroutput">e</tt> of
 207 an edge in the layout or the length of a side <tt
 208 class="computeroutput">s</tt> of the display area, and must be
 209 either <tt class= "computeroutput">boost::edge_length(e)</tt> or <tt
 210 class= "computeroutput">boost::side_length(s)</tt> , respectively.
 211 <b>Python</b>: In Python, this value always refers to the side length
 212 and may only be a <tt>double</tt>.
 213 </blockquote>
 214
 215 IN: <tt>Done done</tt>
 216 <blockquote>
 217 A 4-argument function object that is passed the current
 218 value 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
 223 the system (when <tt class="computeroutput">true</tt> ) or the
 224 energy 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
 228 value type of the weight map.<br>
 229 <b>Python</b>: Any callable Python object with an appropriate signature suffices.
 230 </blockquote>
 231
 232 IN: <tt>typename property_traits&lt;WeightMap&gt;::value_type spring_constant</tt>
 233 <blockquote>
 234 The constant multiplied by each spring's strength.
 235 Larger values create systems with more energy that can take longer
 236 to stabilize; smaller values create systems with less energy that
 237 stabilize quickly but do not necessarily result in pleasing
 238 layouts.<br>
 239 <b>Default</b>: 1.
 240 </blockquote>
 241
 242 IN: <tt>VertexIndexMap index</tt>
 243 <blockquote>
 244 As 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
 255 UTIL/OUT: <tt>DistanceMap distance</tt>
 256 <blockquote>
 257 This parameter will be used to store the distance from every vertex to
 258 every other vertex, which is computed in the first stages of the
 259 algorithm. This value's type must be a model of <a
 260 href="BasicMatrix.html"><tt>BasicMatrix</tt></a> with value type equal to
 261 the 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
 266 UTIL/OUT: <tt>SpringStrengthMatrix spring_strength</tt>
 267 <blockquote>
 268
 269 This matrix will be used to store the strength of the spring between
 270 every pair of vertices. This value's type must be a model of <a
 271 href="BasicMatrix.html">BasicMatrix</a> with value type equal to the
 272 value 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
 277 UTIL: <tt>PartialDerivativeMap partial_derivatives</tt>
 278 <blockquote>
 279 A property map that will be used to store the partial derivatives of
 280 each vertex with respect to the vertex's current coordinates.
 281 coordinates. This must be a
 282 <a href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write
 283 Property Map</a> whose value type is <tt>Topology::point_difference_type</tt>.
 284 The default is an iterator property map built using the graph's vertex index
 285 map.<br>
 286 <b>Default</b>: An <tt>iterator_property_map</tt> created from
 287 an <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 &copy; 2004, 2010 Trustees of Indiana University</td>
 315 <td><a href="http://www.boost.org/people/doug_gregor.html">Douglas Gregor</a>,
 316 Indiana University (dgregor -at cs.indiana.edu)<br>
 317 <a href="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</a>, Indiana
 318 University (<a href=
 319 "mailto:lums@osl.iu.edu">lums@osl.iu.edu</a>)</td>
 320 </tr>
 321 </table>
 322 </body>
 323 </html>