Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::StressMinimization Class Reference

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

#include <ogdf/energybased/StressMinimization.h>

+ Inheritance diagram for ogdf::StressMinimization:

Public Types

enum  TerminationCriterion { TerminationCriterion::None, TerminationCriterion::PositionDifference, TerminationCriterion::Stress }
 

Public Member Functions

 StressMinimization ()
 Constructor: Constructs instance of stress majorization. More...
 
 ~StressMinimization ()
 Destructor. More...
 
virtual void call (GraphAttributes &GA) override
 Calls the layout algorithm with uniform edge costs. More...
 
void convergenceCriterion (TerminationCriterion criterion)
 Tells which TerminationCriterion should be used. More...
 
void fixXCoordinates (bool fix)
 Tells whether the x coordinates are allowed to be modified or not. More...
 
void fixYCoordinates (bool fix)
 Tells whether the y coordinates are allowed to be modified or not. More...
 
void fixZCoordinates (bool fix)
 Tells whether the z coordinates are allowed to be modified or not. More...
 
void hasInitialLayout (bool hasInitialLayout)
 Tells whether the current layout should be used or the initial layout needs to be computed. More...
 
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. More...
 
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. More...
 
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. More...
 
void useEdgeCostsAttribute (bool useEdgeCostsAttribute)
 Tells whether the edge costs are uniform or defined by some edge costs attribute. More...
 
- 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...
 

Private Member Functions

double calcStress (const GraphAttributes &GA, NodeArray< NodeArray< double > > &shortestPathMatrix, NodeArray< NodeArray< double > > &weightMatrix)
 Calculates the stress for the given layout. More...
 
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}. More...
 
void call (GraphAttributes &GA, NodeArray< NodeArray< double > > &shortestPathMatrix, NodeArray< NodeArray< double > > &weightMatrix)
 Runs the stress for a given Graph, shortest path and weight matrix. More...
 
void computeInitialLayout (GraphAttributes &GA)
 Calculates the intial layout of the graph if necessary. More...
 
void copyLayout (const GraphAttributes &GA, NodeArray< double > &newX, NodeArray< double > &newY)
 Convenience method copying the layout of the graph in case of epsilon convergence. More...
 
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. More...
 
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. More...
 
void initMatrices (const Graph &G, NodeArray< NodeArray< double > > &shortestPathMatrix, NodeArray< NodeArray< double > > &weightMatrix)
 Convenience method to initialize the matrices. More...
 
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. More...
 
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. More...
 
void replaceInfinityDistances (NodeArray< NodeArray< double > > &shortestPathMatrix, double newVal)
 Replaces infinite distances to the given value. More...
 

Private Attributes

double m_avgEdgeCosts
 The average edge costs. Needed to define distances of nodes belonging to different graph components. More...
 
bool m_componentLayout
 Indicates whether the components should be treated separately. More...
 
double m_edgeCosts
 The weight of an edge. More...
 
bool m_fixXCoords
 Indicates whether the x coordinates will be modified or not. More...
 
bool m_fixYCoords
 Indicates whether the y coordinates will be modified or not. More...
 
bool m_fixZCoords
 Indicates whether the z coordinates will be modified or not. More...
 
bool m_hasEdgeCostsAttribute
 Tells whether the stress minimization is based on uniform edge costs or a edge costs attribute. More...
 
bool m_hasInitialLayout
 Tells whether an initial layout has to be computed or not. More...
 
int m_numberOfIterations
 Number of iterations performed by the stress minimization. More...
 
TerminationCriterion m_terminationCriterion
 Indicates whether epsilon convergence is used or not. More...
 

Static Private Attributes

const static int DEFAULT_NUMBER_OF_PIVOTS
 Default number of pivots used for the initial Pivot-MDS layout. More...
 
const static double EPSILON
 Convergence constant. More...
 

Detailed Description

Energy-based layout using stress minimization.

Definition at line 50 of file StressMinimization.h.

Member Enumeration Documentation

◆ TerminationCriterion

Enumerator
None 
PositionDifference 
Stress 

Definition at line 53 of file StressMinimization.h.

Constructor & Destructor Documentation

◆ StressMinimization()

ogdf::StressMinimization::StressMinimization ( )
inline

Constructor: Constructs instance of stress majorization.

Definition at line 58 of file StressMinimization.h.

◆ ~StressMinimization()

ogdf::StressMinimization::~StressMinimization ( )
inline

Destructor.

Definition at line 66 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 223 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 199 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 203 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 207 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 211 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 215 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 219 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 227 of file StressMinimization.h.

Member Data Documentation

◆ DEFAULT_NUMBER_OF_PIVOTS

const static int ogdf::StressMinimization::DEFAULT_NUMBER_OF_PIVOTS
staticprivate

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

Definition at line 109 of file StressMinimization.h.

◆ EPSILON

const static double ogdf::StressMinimization::EPSILON
staticprivate

Convergence constant.

Definition at line 106 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 126 of file StressMinimization.h.

◆ m_componentLayout

bool ogdf::StressMinimization::m_componentLayout
private

Indicates whether the components should be treated separately.

Definition at line 129 of file StressMinimization.h.

◆ m_edgeCosts

double ogdf::StressMinimization::m_edgeCosts
private

The weight of an edge.

Definition at line 122 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 135 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 138 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 141 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 113 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 116 of file StressMinimization.h.

◆ m_numberOfIterations

int ogdf::StressMinimization::m_numberOfIterations
private

Number of iterations performed by the stress minimization.

Definition at line 119 of file StressMinimization.h.

◆ m_terminationCriterion

TerminationCriterion ogdf::StressMinimization::m_terminationCriterion
private

Indicates whether epsilon convergence is used or not.

Definition at line 132 of file StressMinimization.h.


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