Energy-based layout using stress minimization. More...

#include <ogdf/energybased/StressMinimization.h>

Inheritance diagram for ogdf::StressMinimization:

Public Types
enum class	TerminationCriterion { None , PositionDifference , Stress }

Public Member Functions
	StressMinimization ()
	Constructor: Constructs instance of stress majorization.

	~StressMinimization ()
	Destructor.

virtual void	call (GraphAttributes &GA) override
	Calls the layout algorithm with uniform edge costs.

void	convergenceCriterion (TerminationCriterion criterion)
	Tells which TerminationCriterion should be used.

void	fixXCoordinates (bool fix)
	Tells whether the x coordinates are allowed to be modified or not.

void	fixYCoordinates (bool fix)
	Tells whether the y coordinates are allowed to be modified or not.

void	fixZCoordinates (bool fix)
	Tells whether the z coordinates are allowed to be modified or not.

void	hasInitialLayout (bool hasInitialLayout)
	Tells whether the current layout should be used or the initial layout needs to be computed.

void	layoutComponentsSeparately (bool separate)
	Sets whether the graph's components should be layouted separately or a dummy distance should be used for nodes within different components.

void	setEdgeCosts (double edgeCosts)
	Sets the desired distance between adjacent nodes. If the new value is smaller or equal 0 the default value (100) is used.

void	setForcing2DLayout (bool forcing2DLayout)
	Sets whether a 2D-layout should be calculated even when GraphAttributes::threeD is set.

void	setIterations (int numberOfIterations)
	Sets a fixed number of iterations for stress majorization. If the new value is smaller or equal 0 the default value (200) is used.

void	useEdgeCostsAttribute (bool useEdgeCostsAttribute)
	Tells whether the edge costs are uniform or defined by some edge costs attribute.

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

virtual	~LayoutModule ()

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

Private Member Functions
double	calcStress (const GraphAttributes &GA, NodeArray< NodeArray< double > > &shortestPathMatrix, NodeArray< NodeArray< double > > &weightMatrix)
	Calculates the stress for the given layout.

void	calcWeights (const Graph &G, NodeArray< NodeArray< double > > &shortestPathMatrix, NodeArray< NodeArray< double > > &weightMatrix)
	Calculates the weight matrix of the shortest path matrix. This is done by w_ij = s_ij^{-2}.

void	call (GraphAttributes &GA, NodeArray< NodeArray< double > > &shortestPathMatrix, NodeArray< NodeArray< double > > &weightMatrix)
	Runs the stress for a given Graph, shortest path and weight matrix.

void	computeInitialLayout (GraphAttributes &GA)
	Calculates the intial layout of the graph if necessary.

void	copyLayout (const GraphAttributes &GA, NodeArray< double > &newX, NodeArray< double > &newY)
	Convenience method copying the layout of the graph in case of epsilon convergence.

void	copyLayout (const GraphAttributes &GA, NodeArray< double > &newX, NodeArray< double > &newY, NodeArray< double > &newZ)
	Convenience method copying the layout of the graph in case of epsilon convergence for 3D.

bool	finished (GraphAttributes &GA, int numberOfPerformedIterations, NodeArray< double > &prevXCoords, NodeArray< double > &prevYCoords, const double prevStress, const double curStress)
	Checks for epsilon convergence and whether the performed number of iterations exceed the predefined maximum number of iterations.

void	initMatrices (const Graph &G, NodeArray< NodeArray< double > > &shortestPathMatrix, NodeArray< NodeArray< double > > &weightMatrix)
	Convenience method to initialize the matrices.

void	minimizeStress (GraphAttributes &GA, NodeArray< NodeArray< double > > &shortestPathMatrix, NodeArray< NodeArray< double > > &weightMatrix)
	Minimizes the stress for each component separately given the shortest path matrix and the weight matrix.

void	nextIteration (GraphAttributes &GA, NodeArray< NodeArray< double > > &shortestPathMatrix, NodeArray< NodeArray< double > > &weightMatrix)
	Runs the next iteration of the stress minimization process. Note that serial update is used.

void	replaceInfinityDistances (NodeArray< NodeArray< double > > &shortestPathMatrix, double newVal)
	Replaces infinite distances to the given value.

Private Attributes
double	m_avgEdgeCosts
	The average edge costs. Needed to define distances of nodes belonging to different graph components.

bool	m_componentLayout
	Indicates whether the components should be treated separately.

double	m_edgeCosts
	The weight of an edge.

bool	m_fixXCoords
	Indicates whether the x coordinates will be modified or not.

bool	m_fixYCoords
	Indicates whether the y coordinates will be modified or not.

bool	m_fixZCoords
	Indicates whether the z coordinates will be modified or not.

bool	m_forcing2DLayout
	Indicates whether a 2D-layout is calculated even when GraphAttributes::threeD is set.

bool	m_hasEdgeCostsAttribute
	Tells whether the stress minimization is based on uniform edge costs or a edge costs attribute.

bool	m_hasInitialLayout
	Tells whether an initial layout has to be computed or not.

int	m_numberOfIterations
	Number of iterations performed by the stress minimization.

TerminationCriterion	m_terminationCriterion
	Indicates whether epsilon convergence is used or not.

bool	m_use3D
	Indicates whether a 3D-layout is computed.

Static Private Attributes
static const int	DEFAULT_NUMBER_OF_PIVOTS
	Default number of pivots used for the initial Pivot-MDS layout.

static const double	EPSILON
	Convergence constant.

Detailed Description

Energy-based layout using stress minimization.

Definition at line 49 of file StressMinimization.h.

Member Enumeration Documentation

◆ TerminationCriterion

enum class ogdf::StressMinimization::TerminationCriterion

strong

Enumerator
None
PositionDifference
Stress

Definition at line 51 of file StressMinimization.h.

Constructor & Destructor Documentation

◆ StressMinimization()

ogdf::StressMinimization::StressMinimization ( )

inline

Constructor: Constructs instance of stress majorization.

Definition at line 54 of file StressMinimization.h.

◆ ~StressMinimization()

ogdf::StressMinimization::~StressMinimization ( )

inline

Destructor.

Definition at line 69 of file StressMinimization.h.

Member Function Documentation

◆ calcStress()

double ogdf::StressMinimization::calcStress	(	const GraphAttributes &	GA,
		NodeArray< NodeArray< double > > &	shortestPathMatrix,
		NodeArray< NodeArray< double > > &	weightMatrix
	)

private

Calculates the stress for the given layout.

◆ calcWeights()

void ogdf::StressMinimization::calcWeights	(	const Graph &	G,
		NodeArray< NodeArray< double > > &	shortestPathMatrix,
		NodeArray< NodeArray< double > > &	weightMatrix
	)

private

Calculates the weight matrix of the shortest path matrix. This is done by w_ij = s_ij^{-2}.

◆ call() [1/2]

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

overridevirtual

Calls the layout algorithm with uniform edge costs.

Implements ogdf::LayoutModule.

◆ call() [2/2]

void ogdf::StressMinimization::call	(	GraphAttributes &	GA,
		NodeArray< NodeArray< double > > &	shortestPathMatrix,
		NodeArray< NodeArray< double > > &	weightMatrix
	)

private

Runs the stress for a given Graph, shortest path and weight matrix.

◆ computeInitialLayout()

void ogdf::StressMinimization::computeInitialLayout ( GraphAttributes & GA )

private

Calculates the intial layout of the graph if necessary.

◆ convergenceCriterion()

void ogdf::StressMinimization::convergenceCriterion ( TerminationCriterion criterion )

inline

Tells which TerminationCriterion should be used.

Definition at line 224 of file StressMinimization.h.

◆ copyLayout() [1/2]

void ogdf::StressMinimization::copyLayout	(	const GraphAttributes &	GA,
		NodeArray< double > &	newX,
		NodeArray< double > &	newY
	)

private

Convenience method copying the layout of the graph in case of epsilon convergence.

◆ copyLayout() [2/2]

void ogdf::StressMinimization::copyLayout	(	const GraphAttributes &	GA,
		NodeArray< double > &	newX,
		NodeArray< double > &	newY,
		NodeArray< double > &	newZ
	)

private

Convenience method copying the layout of the graph in case of epsilon convergence for 3D.

◆ finished()

bool ogdf::StressMinimization::finished	(	GraphAttributes &	GA,
		int	numberOfPerformedIterations,
		NodeArray< double > &	prevXCoords,
		NodeArray< double > &	prevYCoords,
		const double	prevStress,
		const double	curStress
	)

private

Checks for epsilon convergence and whether the performed number of iterations exceed the predefined maximum number of iterations.

◆ fixXCoordinates()

void ogdf::StressMinimization::fixXCoordinates ( bool fix )

inline

Tells whether the x coordinates are allowed to be modified or not.

Definition at line 206 of file StressMinimization.h.

◆ fixYCoordinates()

void ogdf::StressMinimization::fixYCoordinates ( bool fix )

inline

Tells whether the y coordinates are allowed to be modified or not.

Definition at line 208 of file StressMinimization.h.

◆ fixZCoordinates()

void ogdf::StressMinimization::fixZCoordinates ( bool fix )

inline

Tells whether the z coordinates are allowed to be modified or not.

◆ hasInitialLayout()

void ogdf::StressMinimization::hasInitialLayout ( bool hasInitialLayout )

inline

Tells whether the current layout should be used or the initial layout needs to be computed.

Definition at line 210 of file StressMinimization.h.

◆ initMatrices()

void ogdf::StressMinimization::initMatrices	(	const Graph &	G,
		NodeArray< NodeArray< double > > &	shortestPathMatrix,
		NodeArray< NodeArray< double > > &	weightMatrix
	)

private

Convenience method to initialize the matrices.

◆ layoutComponentsSeparately()

void ogdf::StressMinimization::layoutComponentsSeparately ( bool separate )

inline

Sets whether the graph's components should be layouted separately or a dummy distance should be used for nodes within different components.

Definition at line 214 of file StressMinimization.h.

◆ minimizeStress()

void ogdf::StressMinimization::minimizeStress	(	GraphAttributes &	GA,
		NodeArray< NodeArray< double > > &	shortestPathMatrix,
		NodeArray< NodeArray< double > > &	weightMatrix
	)

private

Minimizes the stress for each component separately given the shortest path matrix and the weight matrix.

◆ nextIteration()

void ogdf::StressMinimization::nextIteration	(	GraphAttributes &	GA,
		NodeArray< NodeArray< double > > &	shortestPathMatrix,
		NodeArray< NodeArray< double > > &	weightMatrix
	)

private

Runs the next iteration of the stress minimization process. Note that serial update is used.

◆ replaceInfinityDistances()

void ogdf::StressMinimization::replaceInfinityDistances	(	NodeArray< NodeArray< double > > &	shortestPathMatrix,
		double	newVal
	)

private

Replaces infinite distances to the given value.

◆ setEdgeCosts()

void ogdf::StressMinimization::setEdgeCosts ( double edgeCosts )

inline

Sets the desired distance between adjacent nodes. If the new value is smaller or equal 0 the default value (100) is used.

Definition at line 216 of file StressMinimization.h.

◆ setForcing2DLayout()

void ogdf::StressMinimization::setForcing2DLayout ( bool forcing2DLayout )

inline

Sets whether a 2D-layout should be calculated even when GraphAttributes::threeD is set.

If hasInitialLayout() is set to false, the initial layout will also be 2D only. The z-coordinates will never be changed and they will not influence the computation. This setting overrules fixZCoordinates().

Definition at line 232 of file StressMinimization.h.

◆ setIterations()

void ogdf::StressMinimization::setIterations ( int numberOfIterations )

inline

Sets a fixed number of iterations for stress majorization. If the new value is smaller or equal 0 the default value (200) is used.

Definition at line 220 of file StressMinimization.h.

◆ useEdgeCostsAttribute()

void ogdf::StressMinimization::useEdgeCostsAttribute ( bool useEdgeCostsAttribute )

inline

Tells whether the edge costs are uniform or defined by some edge costs attribute.

Definition at line 228 of file StressMinimization.h.

Member Data Documentation

◆ DEFAULT_NUMBER_OF_PIVOTS

const int ogdf::StressMinimization::DEFAULT_NUMBER_OF_PIVOTS

staticprivate

Default number of pivots used for the initial Pivot-MDS layout.

Definition at line 119 of file StressMinimization.h.

◆ EPSILON

const double ogdf::StressMinimization::EPSILON

staticprivate

Convergence constant.

Definition at line 116 of file StressMinimization.h.

◆ m_avgEdgeCosts

double ogdf::StressMinimization::m_avgEdgeCosts

private

The average edge costs. Needed to define distances of nodes belonging to different graph components.

Definition at line 136 of file StressMinimization.h.

◆ m_componentLayout

bool ogdf::StressMinimization::m_componentLayout

private

Indicates whether the components should be treated separately.

Definition at line 139 of file StressMinimization.h.

◆ m_edgeCosts

double ogdf::StressMinimization::m_edgeCosts

private

The weight of an edge.

Definition at line 132 of file StressMinimization.h.

◆ m_fixXCoords

bool ogdf::StressMinimization::m_fixXCoords

private

Indicates whether the x coordinates will be modified or not.

Definition at line 145 of file StressMinimization.h.

◆ m_fixYCoords

bool ogdf::StressMinimization::m_fixYCoords

private

Indicates whether the y coordinates will be modified or not.

Definition at line 148 of file StressMinimization.h.

◆ m_fixZCoords

bool ogdf::StressMinimization::m_fixZCoords

private

Indicates whether the z coordinates will be modified or not.

Definition at line 151 of file StressMinimization.h.

◆ m_forcing2DLayout

bool ogdf::StressMinimization::m_forcing2DLayout

private

Indicates whether a 2D-layout is calculated even when GraphAttributes::threeD is set.

Definition at line 155 of file StressMinimization.h.

◆ m_hasEdgeCostsAttribute

bool ogdf::StressMinimization::m_hasEdgeCostsAttribute

private

Tells whether the stress minimization is based on uniform edge costs or a edge costs attribute.

Definition at line 123 of file StressMinimization.h.

◆ m_hasInitialLayout

bool ogdf::StressMinimization::m_hasInitialLayout

private

Tells whether an initial layout has to be computed or not.

Definition at line 126 of file StressMinimization.h.

◆ m_numberOfIterations

int ogdf::StressMinimization::m_numberOfIterations

private

Number of iterations performed by the stress minimization.

Definition at line 129 of file StressMinimization.h.

◆ m_terminationCriterion

TerminationCriterion ogdf::StressMinimization::m_terminationCriterion

private

Indicates whether epsilon convergence is used or not.

Definition at line 142 of file StressMinimization.h.

◆ m_use3D

bool ogdf::StressMinimization::m_use3D

private

Indicates whether a 3D-layout is computed.

Definition at line 158 of file StressMinimization.h.

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

include/ogdf/energybased/StressMinimization.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Enumeration Documentation

◆ TerminationCriterion

Constructor & Destructor Documentation

◆ StressMinimization()

◆ ~StressMinimization()

Member Function Documentation

◆ calcStress()

◆ calcWeights()

◆ call() [1/2]

◆ call() [2/2]

◆ computeInitialLayout()

◆ convergenceCriterion()

◆ copyLayout() [1/2]

◆ copyLayout() [2/2]

◆ finished()

◆ fixXCoordinates()

◆ fixYCoordinates()

◆ fixZCoordinates()

◆ hasInitialLayout()

◆ initMatrices()

◆ layoutComponentsSeparately()

◆ minimizeStress()

◆ nextIteration()

◆ replaceInfinityDistances()

◆ setEdgeCosts()

◆ setForcing2DLayout()

◆ setIterations()

◆ useEdgeCostsAttribute()

Member Data Documentation

◆ DEFAULT_NUMBER_OF_PIVOTS

◆ EPSILON

◆ m_avgEdgeCosts

◆ m_componentLayout

◆ m_edgeCosts

◆ m_fixXCoords

◆ m_fixYCoords

◆ m_fixZCoords

◆ m_forcing2DLayout

◆ m_hasEdgeCostsAttribute

◆ m_hasInitialLayout

◆ m_numberOfIterations

◆ m_terminationCriterion

◆ m_use3D

Open
Graph Drawing
Framework