Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::SpringEmbedderKK Class Reference

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. More...
 
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. More...
 
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. More...
 
void computeMaxIterations (bool b)
 If set to true, number of iterations is computed depending on G. More...
 
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. More...
 
void setDesLength (double d)
 Sets desirable edge length directly. More...
 
void setGlobalIterationFactor (int i)
 
void setMaxGlobalIterations (int i)
 Sets the number of global iterations to i. More...
 
void setMaxLocalIterations (int i)
 Sets the number of local iterations to i. More...
 
void setStopTolerance (double s)
 Sets the value for the stop tolerance, below which the system is regarded stable (balanced) and the optimization stopped. More...
 
void setUseLayout (bool b)
 If set to true, the given layout is used for the initial positions. More...
 
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. More...
 
bool useLayout ()
 
double zeroLength ()
 
- Public Member Functions inherited from ogdf::LayoutModule
 LayoutModule ()
 Initializes a layout module. More...
 
virtual ~LayoutModule ()
 
void operator() (GraphAttributes &GA)
 Computes a layout of graph GA. More...
 

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. More...
 
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) More...
 
dpair computeParDers (node v, GraphAttributes &GA, NodeArray< NodeArray< double > > &ss, NodeArray< NodeArray< double > > &dist)
 Compute partial derivative for v. More...
 
void doCall (GraphAttributes &GA, const EdgeArray< double > &eLength, bool simpleBFS)
 Does the actual call. More...
 
bool finished (double maxdelta)
 Checks if main loop is finished because local optimum reached. More...
 
bool finishedNode (double deltav)
 Checks if inner loop (current node) is finished. More...
 
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. More...
 
void mainStep (GraphAttributes &GA, NodeArray< dpair > &partialDer, NodeArray< NodeArray< double > > &oLength, NodeArray< NodeArray< double > > &sstrength)
 Main computation loop, nodes are moved here. More...
 
void scale (GraphAttributes &GA)
 Does the scaling if no edge lengths are given but node sizes are respected. More...
 
void shufflePositions (GraphAttributes &GA)
 Adapts positions to avoid degeneracy (all nodes on a single point) More...
 

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. More...
 
double m_desLength
 Desirable edge length, used instead if > 0. More...
 
double m_distFactor
 
int m_gItBaseVal
 minimum number of global iterations More...
 
int m_gItFactor
 factor for global iterations: m_gItBaseVal+m_gItFactor*|V| More...
 
double m_K
 
double m_ltolerance
 value for local stop criterion More...
 
int m_maxGlobalIt
 Maximum number of global iterations. More...
 
int m_maxLocalIt
 Maximum number of local iterations. More...
 
double m_prevEnergy
 Big K constant for strength computation. More...
 
double m_prevLEnergy
 local energy More...
 
double m_tolerance
 The stop criterion when the forces of all strings are considered to be balanced. More...
 
bool m_useLayout
 use positions or allow to shuffle nodes to avoid degeneration More...
 
double m_zeroLength
 Length of a side of the display area, used for edge length computation if > 0. More...
 

Static Private Attributes

static const double desMinLength
 Defines minimum desired edge length. More...
 
static const int maxVal
 defines infinite upper bound for iteration number More...
 
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.

OptionTypeDefaultDescription
toleranceint0.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 77 of file SpringEmbedderKK.h.

Constructor & Destructor Documentation

◆ SpringEmbedderKK()

ogdf::SpringEmbedderKK::SpringEmbedderKK ( )
inline

Constructor: Constructs instance of Kamada Kawai Layout.

Definition at line 80 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 150 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 173 of file SpringEmbedderKK.h.

◆ finishedNode()

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

Checks if inner loop (current node) is finished.

Definition at line 198 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 134 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 128 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 132 of file SpringEmbedderKK.h.

◆ setMaxGlobalIterations()

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

Sets the number of global iterations to i.

Definition at line 139 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 109 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 112 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 118 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 113 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 281 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 268 of file SpringEmbedderKK.h.

◆ m_desLength

double ogdf::SpringEmbedderKK::m_desLength
private

Desirable edge length, used instead if > 0.

Definition at line 273 of file SpringEmbedderKK.h.

◆ m_distFactor

double ogdf::SpringEmbedderKK::m_distFactor
private

Definition at line 274 of file SpringEmbedderKK.h.

◆ m_gItBaseVal

int ogdf::SpringEmbedderKK::m_gItBaseVal
private

minimum number of global iterations

Definition at line 276 of file SpringEmbedderKK.h.

◆ m_gItFactor

int ogdf::SpringEmbedderKK::m_gItFactor
private

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

Definition at line 277 of file SpringEmbedderKK.h.

◆ m_K

double ogdf::SpringEmbedderKK::m_K
private

Definition at line 269 of file SpringEmbedderKK.h.

◆ m_ltolerance

double ogdf::SpringEmbedderKK::m_ltolerance
private

value for local stop criterion

Definition at line 265 of file SpringEmbedderKK.h.

◆ m_maxGlobalIt

int ogdf::SpringEmbedderKK::m_maxGlobalIt
private

Maximum number of global iterations.

Definition at line 266 of file SpringEmbedderKK.h.

◆ m_maxLocalIt

int ogdf::SpringEmbedderKK::m_maxLocalIt
private

Maximum number of local iterations.

Definition at line 267 of file SpringEmbedderKK.h.

◆ m_prevEnergy

double ogdf::SpringEmbedderKK::m_prevEnergy
private

Big K constant for strength computation.

max energy value

Definition at line 270 of file SpringEmbedderKK.h.

◆ m_prevLEnergy

double ogdf::SpringEmbedderKK::m_prevLEnergy
private

local energy

Definition at line 271 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 264 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 275 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 272 of file SpringEmbedderKK.h.

◆ maxVal

const int ogdf::SpringEmbedderKK::maxVal
staticprivate

defines infinite upper bound for iteration number

Definition at line 282 of file SpringEmbedderKK.h.

◆ minVal

const double ogdf::SpringEmbedderKK::minVal
staticprivate

Definition at line 280 of file SpringEmbedderKK.h.

◆ startVal

const double ogdf::SpringEmbedderKK::startVal
staticprivate

Definition at line 279 of file SpringEmbedderKK.h.


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