Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

This is the documentation for an old version of Boost. Click here to view this page for the latest version.

Function kamada_kawai_spring_layout

boost::kamada_kawai_spring_layout — Kamada-Kawai spring layout for connected, undirected graphs.

Synopsis

template<typename Graph, typename PositionMap, typename WeightMap, typename T, 
         bool EdgeOrSideLength, typename Done, typename VertexIndexMap, 
         typename DistanceMatrix, typename SpringStrengthMatrix, 
         typename PartialDerivativeMap> 
  bool kamada_kawai_spring_layout(const Graph & g, PositionMap position, 
                                  WeightMap weight, 
                                  unspecified edge_or_side_length, Done done, 
                                  typename property_traits< WeightMap >::value_type spring_constant, 
                                  VertexIndexMap index, 
                                  DistanceMatrix distance, 
                                  SpringStrengthMatrix spring_strength, 
                                  PartialDerivativeMap partial_derivatives);
template<typename Graph, typename PositionMap, typename WeightMap, typename T, 
         bool EdgeOrSideLength, typename Done, typename VertexIndexMap> 
  bool kamada_kawai_spring_layout(const Graph & g, PositionMap position, 
                                  WeightMap weight, 
                                  unspecified edge_or_side_length, Done done, 
                                  typename property_traits< WeightMap >::value_type spring_constant, 
                                  VertexIndexMap index);
template<typename Graph, typename PositionMap, typename WeightMap, typename T, 
         bool EdgeOrSideLength, typename Done> 
  bool kamada_kawai_spring_layout(const Graph & g, PositionMap position, 
                                  WeightMap weight, 
                                  unspecified edge_or_side_length, Done done, 
                                  typename property_traits< WeightMap >::value_type spring_constant = typename property_traits< WeightMap >::value_type(1));
template<typename Graph, typename PositionMap, typename WeightMap, typename T, 
         bool EdgeOrSideLength> 
  bool kamada_kawai_spring_layout(const Graph & g, PositionMap position, 
                                  WeightMap weight, 
                                  unspecified edge_or_side_length);

Where Defined

boost/graph/kamada_kawai_spring_layout.hpp

Description

Parameters

distance

(UTIL/OUT) 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 BasicMatrix with value type equal to the value type of the weight map. The default is a a vector of vectors.

done

(IN) is a 4-argument function object that is passed the current value of delta_p (i.e., the energy of vertex p ), the vertex p , the graph g , and a boolean flag indicating whether delta_p is the maximum energy in the system (when true ) or the energy of the vertex being moved. Defaults to layout_tolerance instantiated over the value type of the weight map.

edge_or_side_length

(IN) provides either the unit length e of an edge in the layout or the length of a side s of the display area, and must be either boost::edge_length(e) or boost::side_length(s) , respectively.

g

(IN) must be a model of Vertex List Graph, Edge List Graph, and Incidence Graph and must be connected and undirected.

index

(IN) is a mapping from vertices to index values between 0 and num_vertices(g) . The default is get(vertex_index,g) .

partial_derivatives

(UTIL) will be used to store the partial derivates of each vertex with respect to the x and y coordinates. This must be a Read/Write Property Map whose value type is a pair with both types equivalent to the value type of the weight map. The default is an iterator property map.

position

(OUT) must be a model of Lvalue Property Map, where the value type is a class containing fields x and y that will be set to the x and y coordinates of each vertex.

spring_constant

(IN) is 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. The default value is 1.

spring_strength

(UTIL/OUT) will be used to store the strength of the spring between every pair of vertices. This value's type must be a model of BasicMatrix with value type equal to the value type of the weight map. The default is a a vector of vectors.

weight

(IN) must be a model of Readable Property Map, which provides the weight of each edge in the graph g .

This algorithm [57] 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.

Prior to invoking this algorithm, it is recommended that the vertices be placed along the vertices of a regular n-sided polygon via circle_layout.

Returns: true if layout was successful or false if a negative weight cycle was detected or the graph is disconnected.


Copyright © 2004 Douglas Gregor, Indiana University (dgregor -at cs.indiana.edu)
Andrew Lumsdaine, Indiana University (lums@osl.iu.edu)