...one of the most highly
regarded and expertly designed C++ library projects in the
world.

— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards

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

template<typenameGraph,typenamePositionMap,typenameWeightMap,typenameT,boolEdgeOrSideLength,typenameDone,typenameVertexIndexMap,typenameDistanceMatrix,typenameSpringStrengthMatrix,typenamePartialDerivativeMap>boolkamada_kawai_spring_layout(constGraph & g, PositionMap position, WeightMap weight,unspecifiededge_or_side_length, Done done,typenameproperty_traits< WeightMap >::value_type spring_constant, VertexIndexMap index, DistanceMatrix distance, SpringStrengthMatrix spring_strength, PartialDerivativeMap partial_derivatives);template<typenameGraph,typenamePositionMap,typenameWeightMap,typenameT,boolEdgeOrSideLength,typenameDone,typenameVertexIndexMap>boolkamada_kawai_spring_layout(constGraph & g, PositionMap position, WeightMap weight,unspecifiededge_or_side_length, Done done,typenameproperty_traits< WeightMap >::value_type spring_constant, VertexIndexMap index);template<typenameGraph,typenamePositionMap,typenameWeightMap,typenameT,boolEdgeOrSideLength,typenameDone>boolkamada_kawai_spring_layout(constGraph & g, PositionMap position, WeightMap weight,unspecifiededge_or_side_length, Done done,typenameproperty_traits< WeightMap >::value_type spring_constant = typename property_traits< WeightMap >::value_type(1));template<typenameGraph,typenamePositionMap,typenameWeightMap,typenameT,boolEdgeOrSideLength>boolkamada_kawai_spring_layout(constGraph & g, PositionMap position, WeightMap weight,unspecifiededge_or_side_length);

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.

The graph, whose typeOUT:Graphmust model the VertexListGraph, EdgeListGraph, and IncidenceGraph concepts. The graph must be undirected and connected.

Python: This parameter is namedgraphin Python.

This property map is used to store the position of each vertex. The typeIN:PositionMapmust be a model of Writable Property Map, with the graph's edge descriptor type as its key type.

Python: The position map must be avertex_point2d_mapfor the graph.

Python default:graph.get_vertex_point2d_map("position")

The weight or ``length'' of each edge in the graph. The weights must all be non-negative, and the algorithm will throw aIN:negative_edgeexception is one of the edges is negative. The typeWeightMapmust be a model of Readable Property Map. 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.

Default:get(edge_weight, g)

Python: Must be anedge_double_mapfor the graph.

Python default:graph.get_edge_double_map("weight")

Provides either the unit lengthIN:eof an edge in the layout or the length of a sidesof the display area, and must be eitherboost::edge_length(e)orboost::side_length(s), respectively.Python: In Python, this value always refers to the side length and may only be adouble.

A 4-argument function object that is passed the current value of delta_p (i.e., the energy of vertexIN:p), the vertexp, the graphg, and a boolean flag indicating whetherdelta_pis the maximum energy in the system (whentrue) or the energy of the vertex being moved.Default:layout_toleranceinstantiated over the value type of the weight map.

Python: Any callable Python object with an appropriate signature suffices.

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.IN:

Default: 1.

As a mapping from vertices to index values between 0 andUTIL/OUT:num_vertices(g).

Default:get(vertex_index,g).

Python: Unsupported parameter.

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 ofUTIL/OUT:BasicMatrixwith value type equal to the value type of the weight map.

Default: A vector of vectors.

Python: Unsupported parameter.

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 BasicMatrix with value type equal to the value type of the weight map.UTIL:

Default: A vector of vectors of the value type of the weight map.

Python: Unsupported parameter.

A property map that will be used to store the partial derivates of each vertex with respect to thexandycoordinates. 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.

Default: Aniterator_property_mapcreated from anstd::vectorofstd::pair<weight_type, weight_type>, whereweight_typeis the value type of theWeightMap.

Python: Unsupported parameter.

Whenfalse, performs layout of the graph on a circle before running the Kamada-Kawai algorithm. Iftrue, the algorithm is executing starting with the vertex configuration in thepositionmap.

Default:False.

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