Note

This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.

rustworkx.kamada_kawai_layout

kamada_kawai_layout(graph, pos=None, fixed=None, weight_fn=None, default_weight=1.0, epsilon=0.0001, max_outer=500, max_inner=10, scale=1.0, center=None)[source]

Position nodes using the Kamada-Kawai path-length cost-function.

The layout minimises the energy

\[E = \frac{1}{2} \sum_{i<j} k_{ij} (|p_i - p_j| - l_{ij})^2\]

where \(d_{ij}\) is the graph-theoretic shortest path between nodes \(i\) and \(j\), \(l_{ij} \propto d_{ij}\) is the desired display distance, and \(k_{ij} = 1 / d_{ij}^2\) is the spring constant. Minimisation follows the original Kamada and Kawai (1989) scheme: at each outer step the node with the largest partial-gradient norm is selected and updated by a 2D Newton step against the local 2x2 Hessian.

Disconnected graphs are laid out by running Kamada-Kawai independently on each connected component and packing the components in a row, so components remain visibly separated rather than fighting for space inside a single global energy minimisation.

Parameters:

  • graph – Graph to be used. Can either be a PyGraph or PyDiGraph.

  • pos (dict) – Initial node positions as a dictionary with node ids as keys and values as a coordinate list. If None, a per-component circular layout is used as the starting point. (default=None)

  • fixed (set) – Nodes to keep fixed at initial position. Error raised if fixed is specified and pos is not. (default=None)

  • weight_fn – An optional weight function for an edge. It will accept a single argument, the edge’s weight object, and return a float used as the edge weight in the all-pairs shortest path computation.

  • default_weight (float) – Edge weight when weight_fn is not provided. (default=1.0)

  • epsilon (float) – Convergence threshold for the maximum partial-gradient norm. (default=1e-4)

  • max_outer (int) – Maximum number of outer iterations. (default=500)

  • max_inner (int) – Maximum number of inner Newton steps per outer iteration. (default=10)

  • scale (float) – Scale factor for positions. Not used unless fixed is None. (default=1.0)

  • center (list) – Coordinate pair around which to center the layout. Not used unless fixed is None. (default=None)

Returns:

A dictionary of positions keyed by node id.

Return type:

dict