The spring-embedder layout algorithm by Kamada and Kawai. More...

#include <ogdf/energybased/SpringEmbedderKK.h>

Inheritance diagram for ogdf::SpringEmbedderKK:

Public Types
using	dpair = Tuple2< double, double >

Public Member Functions
	SpringEmbedderKK ()
	Constructor: Constructs instance of Kamada Kawai Layout.

virtual void	call (GraphAttributes &GA) override
	Calls the layout algorithm for graph attributes `GA`. Currently, GA.doubleWeight is NOT used to allow simple distinction of BFS/APSS. Precondition: Graph is connected.

void	call (GraphAttributes &GA, const EdgeArray< double > &eLength)
	Calls the layout algorithm for graph attributes `GA` using values in eLength for distance computation. Precondition: Graph is connected.

void	computeMaxIterations (bool b)
	If set to true, number of iterations is computed depending on G.

int	maxGlobalIterations () const

int	maxLocalIterations () const
	It is possible to limit the number of iterations to a fixed value Returns the current setting of iterations. These values are only used if m_computeMaxIt is set to true.

void	setDesLength (double d)
	Sets desirable edge length directly.

void	setGlobalIterationFactor (int i)

void	setMaxGlobalIterations (int i)
	Sets the number of global iterations to `i`.

void	setMaxLocalIterations (int i)
	Sets the number of local iterations to `i`.

void	setStopTolerance (double s)
	Sets the value for the stop tolerance, below which the system is regarded stable (balanced) and the optimization stopped.

void	setUseLayout (bool b)
	If set to true, the given layout is used for the initial positions.

void	setZeroLength (double d)
	If set != 0, value zerolength is used to determine the desirable edge length by L = zerolength / max distance_ij. Otherwise, zerolength is determined using the node number and sizes.

bool	useLayout ()

double	zeroLength ()

Public Member Functions inherited from ogdf::LayoutModule
	LayoutModule ()
	Initializes a layout module.

virtual	~LayoutModule ()

void	operator() (GraphAttributes &GA)
	Computes a layout of graph `GA`.

Protected Member Functions
void	adaptLengths (const Graph &G, const GraphAttributes &GA, const EdgeArray< double > &eLengths, EdgeArray< double > &adaptedLengths)
	Changes given edge lengths (interpreted as weight factors) according to additional parameters like node size etc.

dpair	computeParDer (node m, node u, GraphAttributes &GA, NodeArray< NodeArray< double > > &ss, NodeArray< NodeArray< double > > &dist)
	Computes contribution of node u to the first partial derivatives (dE/dx_m, dE/dy_m) (for node m) (eq. 7 and 8 in paper)

dpair	computeParDers (node v, GraphAttributes &GA, NodeArray< NodeArray< double > > &ss, NodeArray< NodeArray< double > > &dist)
	Compute partial derivative for v.

void	doCall (GraphAttributes &GA, const EdgeArray< double > &eLength, bool simpleBFS)
	Does the actual call.

bool	finished (double maxdelta)
	Checks if main loop is finished because local optimum reached.

bool	finishedNode (double deltav)
	Checks if inner loop (current node) is finished.

void	initialize (GraphAttributes &GA, NodeArray< dpair > &partialDer, const EdgeArray< double > &eLength, NodeArray< NodeArray< double > > &oLength, NodeArray< NodeArray< double > > &sstrength, bool simpleBFS)
	Does the necessary initialization work for the call functions.

void	mainStep (GraphAttributes &GA, NodeArray< dpair > &partialDer, NodeArray< NodeArray< double > > &oLength, NodeArray< NodeArray< double > > &sstrength)
	Main computation loop, nodes are moved here.

void	scale (GraphAttributes &GA)
	Does the scaling if no edge lengths are given but node sizes are respected.

void	shufflePositions (GraphAttributes &GA)
	Adapts positions to avoid degeneracy (all nodes on a single point)

Private Member Functions
double	allpairssp (const Graph &G, const EdgeArray< double > &eLengths, NodeArray< NodeArray< double > > &distance, const double threshold=std::numeric_limits< double >::max())

double	allpairsspBFS (const Graph &G, NodeArray< NodeArray< double > > &distance)

Private Attributes
bool	m_computeMaxIt
	If true, number of iterations is computed depending on number of nodes.

double	m_desLength
	Desirable edge length, used instead if > 0.

double	m_distFactor

int	m_gItBaseVal
	minimum number of global iterations

int	m_gItFactor
	factor for global iterations: m_gItBaseVal+m_gItFactor*\|V\|

double	m_K

double	m_ltolerance
	value for local stop criterion

int	m_maxGlobalIt
	Maximum number of global iterations.

int	m_maxLocalIt
	Maximum number of local iterations.

double	m_prevEnergy
	Big K constant for strength computation.

double	m_prevLEnergy
	local energy

double	m_tolerance
	The stop criterion when the forces of all strings are considered to be balanced.

bool	m_useLayout
	use positions or allow to shuffle nodes to avoid degeneration

double	m_zeroLength
	Length of a side of the display area, used for edge length computation if > 0.

Static Private Attributes
static const double	desMinLength
	Defines minimum desired edge length.

static const int	maxVal
	defines infinite upper bound for iteration number

static const double	minVal

static const double	startVal

Detailed Description

The spring-embedder layout algorithm by Kamada and Kawai.

The implementation used in SpringEmbedderKK is based on the following publication:

Tomihisa Kamada, Satoru Kawai: An Algorithm for Drawing General Undirected Graphs. Information Processing Letters 31, pp. 7-15, 1989.

Precondition: The input graph has to be connected.

Optional parameters

There are some parameters that can be tuned to optimize the algorithm's behavior regarding runtime and layout quality. First of all note that the algorithm uses all pairs shortest path to compute the graph theoretic distance. This can be done either with BFS (ignoring node sizes) in quadratic time or by using e.g. Floyd's algorithm in cubic time with given edge lengths that may reflect the node sizes. Also m_computeMaxIt decides if the computation is stopped after a fixed maximum number of iterations. The desirable edge length can either be set or computed from the graph and the given layout. Kamada-Kawai layout provides the following optional parameters.

Option	Type	Default	Description
tolerance	int	0.0001	Tolerance for the energy level (below which the main loop stops).

Definition at line 74 of file SpringEmbedderKK.h.

Member Typedef Documentation

◆ dpair

using ogdf::SpringEmbedderKK::dpair = Tuple2<double, double>

Definition at line 76 of file SpringEmbedderKK.h.

Constructor & Destructor Documentation

◆ SpringEmbedderKK()

ogdf::SpringEmbedderKK::SpringEmbedderKK ( )

inline

Constructor: Constructs instance of Kamada Kawai Layout.

Definition at line 79 of file SpringEmbedderKK.h.

Member Function Documentation

◆ adaptLengths()

void ogdf::SpringEmbedderKK::adaptLengths	(	const Graph &	G,
		const GraphAttributes &	GA,
		const EdgeArray< double > &	eLengths,
		EdgeArray< double > &	adaptedLengths
	)

protected

Changes given edge lengths (interpreted as weight factors) according to additional parameters like node size etc.

◆ allpairssp()

double ogdf::SpringEmbedderKK::allpairssp	(	const Graph &	G,
		const EdgeArray< double > &	eLengths,
		NodeArray< NodeArray< double > > &	distance,
		const double	threshold = `std::numeric_limits< double >::max()`
	)

private

◆ allpairsspBFS()

double ogdf::SpringEmbedderKK::allpairsspBFS	(	const Graph &	G,
		NodeArray< NodeArray< double > > &	distance
	)

private

◆ call() [1/2]

virtual void ogdf::SpringEmbedderKK::call ( GraphAttributes & GA )

overridevirtual

Calls the layout algorithm for graph attributes GA. Currently, GA.doubleWeight is NOT used to allow simple distinction of BFS/APSS. Precondition: Graph is connected.

Implements ogdf::LayoutModule.

◆ call() [2/2]

void ogdf::SpringEmbedderKK::call	(	GraphAttributes &	GA,
		const EdgeArray< double > &	eLength
	)

Calls the layout algorithm for graph attributes GA using values in eLength for distance computation. Precondition: Graph is connected.

◆ computeMaxIterations()

void ogdf::SpringEmbedderKK::computeMaxIterations ( bool b )

inline

If set to true, number of iterations is computed depending on G.

Definition at line 152 of file SpringEmbedderKK.h.

◆ computeParDer()

dpair ogdf::SpringEmbedderKK::computeParDer	(	node	m,
		node	u,
		GraphAttributes &	GA,
		NodeArray< NodeArray< double > > &	ss,
		NodeArray< NodeArray< double > > &	dist
	)

protected

Computes contribution of node u to the first partial derivatives (dE/dx_m, dE/dy_m) (for node m) (eq. 7 and 8 in paper)

◆ computeParDers()

dpair ogdf::SpringEmbedderKK::computeParDers	(	node	v,
		GraphAttributes &	GA,
		NodeArray< NodeArray< double > > &	ss,
		NodeArray< NodeArray< double > > &	dist
	)

protected

Compute partial derivative for v.

◆ doCall()

void ogdf::SpringEmbedderKK::doCall	(	GraphAttributes &	GA,
		const EdgeArray< double > &	eLength,
		bool	simpleBFS
	)

protected

Does the actual call.

◆ finished()

bool ogdf::SpringEmbedderKK::finished ( double maxdelta )

inlineprotected

Checks if main loop is finished because local optimum reached.

Definition at line 172 of file SpringEmbedderKK.h.

◆ finishedNode()

bool ogdf::SpringEmbedderKK::finishedNode ( double deltav )

inlineprotected

Checks if inner loop (current node) is finished.

Definition at line 196 of file SpringEmbedderKK.h.

◆ initialize()

void ogdf::SpringEmbedderKK::initialize	(	GraphAttributes &	GA,
		NodeArray< dpair > &	partialDer,
		const EdgeArray< double > &	eLength,
		NodeArray< NodeArray< double > > &	oLength,
		NodeArray< NodeArray< double > > &	sstrength,
		bool	simpleBFS
	)

protected

Does the necessary initialization work for the call functions.

◆ mainStep()

void ogdf::SpringEmbedderKK::mainStep	(	GraphAttributes &	GA,
		NodeArray< dpair > &	partialDer,
		NodeArray< NodeArray< double > > &	oLength,
		NodeArray< NodeArray< double > > &	sstrength
	)

protected

Main computation loop, nodes are moved here.

◆ maxGlobalIterations()

int ogdf::SpringEmbedderKK::maxGlobalIterations ( ) const

inline

Definition at line 135 of file SpringEmbedderKK.h.

◆ maxLocalIterations()

int ogdf::SpringEmbedderKK::maxLocalIterations ( ) const

inline

It is possible to limit the number of iterations to a fixed value Returns the current setting of iterations. These values are only used if m_computeMaxIt is set to true.

Definition at line 127 of file SpringEmbedderKK.h.

◆ scale()

void ogdf::SpringEmbedderKK::scale ( GraphAttributes & GA )

protected

Does the scaling if no edge lengths are given but node sizes are respected.

◆ setDesLength()

void ogdf::SpringEmbedderKK::setDesLength ( double d )

inline

Sets desirable edge length directly.

Definition at line 122 of file SpringEmbedderKK.h.

◆ setGlobalIterationFactor()

void ogdf::SpringEmbedderKK::setGlobalIterationFactor ( int i )

inline

Definition at line 129 of file SpringEmbedderKK.h.

◆ setMaxGlobalIterations()

void ogdf::SpringEmbedderKK::setMaxGlobalIterations ( int i )

inline

Sets the number of global iterations to i.

Definition at line 138 of file SpringEmbedderKK.h.

◆ setMaxLocalIterations()

void ogdf::SpringEmbedderKK::setMaxLocalIterations ( int i )

inline

Sets the number of local iterations to i.

Definition at line 145 of file SpringEmbedderKK.h.

◆ setStopTolerance()

void ogdf::SpringEmbedderKK::setStopTolerance ( double s )

inline

Sets the value for the stop tolerance, below which the system is regarded stable (balanced) and the optimization stopped.

Definition at line 107 of file SpringEmbedderKK.h.

◆ setUseLayout()

void ogdf::SpringEmbedderKK::setUseLayout ( bool b )

inline

If set to true, the given layout is used for the initial positions.

Definition at line 110 of file SpringEmbedderKK.h.

◆ setZeroLength()

void ogdf::SpringEmbedderKK::setZeroLength ( double d )

inline

If set != 0, value zerolength is used to determine the desirable edge length by L = zerolength / max distance_ij. Otherwise, zerolength is determined using the node number and sizes.

Definition at line 117 of file SpringEmbedderKK.h.

◆ shufflePositions()

void ogdf::SpringEmbedderKK::shufflePositions ( GraphAttributes & GA )

protected

Adapts positions to avoid degeneracy (all nodes on a single point)

◆ useLayout()

bool ogdf::SpringEmbedderKK::useLayout ( )

inline

Definition at line 112 of file SpringEmbedderKK.h.

◆ zeroLength()

double ogdf::SpringEmbedderKK::zeroLength ( )

inline

Definition at line 119 of file SpringEmbedderKK.h.

Member Data Documentation

◆ desMinLength

const double ogdf::SpringEmbedderKK::desMinLength

staticprivate

Defines minimum desired edge length.

Smaller values are treated as zero

Definition at line 265 of file SpringEmbedderKK.h.

◆ m_computeMaxIt

bool ogdf::SpringEmbedderKK::m_computeMaxIt

private

If true, number of iterations is computed depending on number of nodes.

Definition at line 252 of file SpringEmbedderKK.h.

◆ m_desLength

double ogdf::SpringEmbedderKK::m_desLength

private

Desirable edge length, used instead if > 0.

Definition at line 257 of file SpringEmbedderKK.h.

◆ m_distFactor

double ogdf::SpringEmbedderKK::m_distFactor

private

Definition at line 258 of file SpringEmbedderKK.h.

◆ m_gItBaseVal

int ogdf::SpringEmbedderKK::m_gItBaseVal

private

minimum number of global iterations

Definition at line 260 of file SpringEmbedderKK.h.

◆ m_gItFactor

int ogdf::SpringEmbedderKK::m_gItFactor

private

factor for global iterations: m_gItBaseVal+m_gItFactor*|V|

Definition at line 261 of file SpringEmbedderKK.h.

◆ m_K

double ogdf::SpringEmbedderKK::m_K

private

Definition at line 253 of file SpringEmbedderKK.h.

◆ m_ltolerance

double ogdf::SpringEmbedderKK::m_ltolerance

private

value for local stop criterion

Definition at line 249 of file SpringEmbedderKK.h.

◆ m_maxGlobalIt

int ogdf::SpringEmbedderKK::m_maxGlobalIt

private

Maximum number of global iterations.

Definition at line 250 of file SpringEmbedderKK.h.

◆ m_maxLocalIt

int ogdf::SpringEmbedderKK::m_maxLocalIt

private

Maximum number of local iterations.

Definition at line 251 of file SpringEmbedderKK.h.

◆ m_prevEnergy

double ogdf::SpringEmbedderKK::m_prevEnergy

private

Big K constant for strength computation.

max energy value

Definition at line 254 of file SpringEmbedderKK.h.

◆ m_prevLEnergy

double ogdf::SpringEmbedderKK::m_prevLEnergy

private

local energy

Definition at line 255 of file SpringEmbedderKK.h.

◆ m_tolerance

double ogdf::SpringEmbedderKK::m_tolerance

private

The stop criterion when the forces of all strings are considered to be balanced.

value for stop criterion

Definition at line 248 of file SpringEmbedderKK.h.

◆ m_useLayout

bool ogdf::SpringEmbedderKK::m_useLayout

private

use positions or allow to shuffle nodes to avoid degeneration

Definition at line 259 of file SpringEmbedderKK.h.

◆ m_zeroLength

double ogdf::SpringEmbedderKK::m_zeroLength

private

Length of a side of the display area, used for edge length computation if > 0.

Definition at line 256 of file SpringEmbedderKK.h.

◆ maxVal

const int ogdf::SpringEmbedderKK::maxVal

staticprivate

defines infinite upper bound for iteration number

Definition at line 266 of file SpringEmbedderKK.h.

◆ minVal

const double ogdf::SpringEmbedderKK::minVal

staticprivate

Definition at line 264 of file SpringEmbedderKK.h.

◆ startVal

const double ogdf::SpringEmbedderKK::startVal

staticprivate

Definition at line 263 of file SpringEmbedderKK.h.

The documentation for this class was generated from the following file:

include/ogdf/energybased/SpringEmbedderKK.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Optional parameters

Member Typedef Documentation

◆ dpair

Constructor & Destructor Documentation

◆ SpringEmbedderKK()

Member Function Documentation

◆ adaptLengths()

◆ allpairssp()

◆ allpairsspBFS()

◆ call() [1/2]

◆ call() [2/2]

◆ computeMaxIterations()

◆ computeParDer()

◆ computeParDers()

◆ doCall()

◆ finished()

◆ finishedNode()

◆ initialize()

◆ mainStep()

◆ maxGlobalIterations()

◆ maxLocalIterations()

◆ scale()

◆ setDesLength()

◆ setGlobalIterationFactor()

◆ setMaxGlobalIterations()

◆ setMaxLocalIterations()

◆ setStopTolerance()

◆ setUseLayout()

◆ setZeroLength()

◆ shufflePositions()

◆ useLayout()

◆ zeroLength()

Member Data Documentation

◆ desMinLength

◆ m_computeMaxIt

◆ m_desLength

◆ m_distFactor

◆ m_gItBaseVal

◆ m_gItFactor

◆ m_K

◆ m_ltolerance

◆ m_maxGlobalIt

◆ m_maxLocalIt

◆ m_prevEnergy

◆ m_prevLEnergy

◆ m_tolerance

◆ m_useLayout

◆ m_zeroLength

◆ maxVal

◆ minVal

◆ startVal

Open
Graph Drawing
Framework