Coordinate assignment phase for the Sugiyama algorithm by Ulrik Brandes and Boris Köpf. More...

#include <ogdf/layered/FastSimpleHierarchyLayout.h>

Inheritance diagram for ogdf::FastSimpleHierarchyLayout:

Public Member Functions
	FastSimpleHierarchyLayout ()
	Creates an instance of fast simple hierarchy layout.

	FastSimpleHierarchyLayout (const FastSimpleHierarchyLayout &)
	Copy constructor.

virtual	~FastSimpleHierarchyLayout ()

bool	balanced () const
	Returns the option balanced.

void	balanced (bool b)
	Sets the option balanced to `b`.

bool	downward () const
	Returns the option downward.

void	downward (bool d)
	Sets the option downward to `d`.

double	layerDistance () const
	Returns the option layer distance.

void	layerDistance (double dist)
	Sets the option layer distance to `dist`.

bool	leftToRight () const
	Returns the option left-to-right.

void	leftToRight (bool b)
	Sets the option left-to-right to `b`.

double	nodeDistance () const
	Returns the option node distance.

void	nodeDistance (double dist)
	Sets the option node distance to `dist`.

FastSimpleHierarchyLayout &	operator= (const FastSimpleHierarchyLayout &)
	Assignment operator.

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

virtual	~HierarchyLayoutModule ()

void	call (const HierarchyLevelsBase &levels, GraphAttributes &GA)
	Computes a hierarchy layout of `levels` in `GA`.

Protected Member Functions
virtual void	doCall (const HierarchyLevelsBase &levels, GraphAttributes &AGC) override
	Implements the actual algorithm call.

Private Member Functions
void	computeBlockWidths (const GraphCopy &GC, const GraphAttributes &GCA, NodeArray< node > &root, NodeArray< double > &blockWidth)
	Computes the width of each block, i.e., the maximal width of a node in the block, and stores it in blockWidth for the root of the block.

void	horizontalCompactation (const NodeArray< node > &align, const HierarchyLevelsBase &levels, const NodeArray< node > &root, const NodeArray< double > &blockWidth, NodeArray< double > &x, const bool leftToRight, bool downward)
	Calculate the coordinates for each node.

void	markType1Conflicts (const HierarchyLevelsBase &levels, bool downward, NodeArray< NodeArray< bool > > &type1Conflicts)
	Preprocessing step to find all type1 conflicts.

void	placeBlock (node v, NodeArray< node > &sink, NodeArray< double > &shift, NodeArray< double > &x, const NodeArray< node > &align, const HierarchyLevelsBase &levels, const NodeArray< double > &blockWidth, const NodeArray< node > &root, const bool leftToRight)
	Calculate the coordinate for root nodes (placing)

node	pred (const node v, const HierarchyLevelsBase &levels, const bool leftToRight)
	Predecessor of v on the same level,.

void	verticalAlignment (const HierarchyLevelsBase &levels, NodeArray< node > &root, NodeArray< node > &align, const NodeArray< NodeArray< bool > > &type1Conflicts, const bool downward, const bool leftToRight)
	Align each node to a node on the next higher level.

node	virtualTwinNode (const HierarchyLevelsBase &levels, const node v, const HierarchyLevelsBase::TraversingDir dir) const
	The twin of an inner Segment.

Private Attributes
bool	m_balanced
	stores the option balanced.

bool	m_downward
	stores the option downward.

bool	m_leftToRight
	stores the option left-to-right.

double	m_minXSep
	stores the option node distance.

double	m_ySep
	stores the option layer distance.

Additional Inherited Members
Static Public Member Functions inherited from ogdf::HierarchyLayoutModule
static void	dynLayerDistance (GraphAttributes &AGC, HierarchyLevelsBase &levels)

Static Protected Member Functions inherited from ogdf::HierarchyLayoutModule
static double	getHeight (const GraphAttributes &GA, const HierarchyLevelsBase &levels, node v)
	Returns the `GA` height of node `v` or 0 if it is a dummy node in the hierarchy of `levels`.

static double	getWidth (const GraphAttributes &GA, const HierarchyLevelsBase &levels, node v)
	Returns the `GA` width of node `v` or 0 if it is a dummy node in the hierarchy of `levels`.

Detailed Description

Coordinate assignment phase for the Sugiyama algorithm by Ulrik Brandes and Boris Köpf.

This class implements a hierarchy layout algorithm, i.e., it layouts hierarchies with a given order of nodes on each layer. It is used as a third phase of the Sugiyama algorithm.

The Algorithm runs in three phases.

Alignment (4x)
Horizontal Compactation (4x)
Balancing

The Alignment and Horzontal Compactation phase are calculated downward, upward, left-to-right and right-to-left. The four resulting layouts are combined in a balancing step.

The implementation is based on:

Ulrik Brandes, Boris Köpf: Fast and Simple Horizontal Coordinate Assignment. LNCS 2002, Volume 2265/2002, pp. 33-36

Optional Parameters

Option	Type	Default	Description
node distance	int	150	the minimal horizontal distance between two nodes on the same layer
layer distance	int	75	the minimal vertical distance between two nodes on adjacent layers
balanced	bool	true	determines whether balancing is used
left-to-right	bool	true	determines whether block alignment is computed by a left-to-right (true) or right-to-left traversal
downward	bool	true	determines whether block alignment is computed by a downward (true) or upward traversal

Definition at line 89 of file FastSimpleHierarchyLayout.h.

Constructor & Destructor Documentation

◆ FastSimpleHierarchyLayout() [1/2]

ogdf::FastSimpleHierarchyLayout::FastSimpleHierarchyLayout ( )

Creates an instance of fast simple hierarchy layout.

Sets the options to default values, i.e., use balanced layout with left-to-right node direction on each layer, node distance as given by LayoutStandards, and layer distance as 1.5 times node distance.

◆ FastSimpleHierarchyLayout() [2/2]

ogdf::FastSimpleHierarchyLayout::FastSimpleHierarchyLayout ( const FastSimpleHierarchyLayout & )

Copy constructor.

◆ ~FastSimpleHierarchyLayout()

virtual ogdf::FastSimpleHierarchyLayout::~FastSimpleHierarchyLayout ( )

inlinevirtual

Definition at line 114 of file FastSimpleHierarchyLayout.h.

Member Function Documentation

◆ balanced() [1/2]

bool ogdf::FastSimpleHierarchyLayout::balanced ( ) const

inline

Returns the option balanced.

Definition at line 144 of file FastSimpleHierarchyLayout.h.

◆ balanced() [2/2]

void ogdf::FastSimpleHierarchyLayout::balanced ( bool b )

inline

Sets the option balanced to b.

Definition at line 147 of file FastSimpleHierarchyLayout.h.

◆ computeBlockWidths()

void ogdf::FastSimpleHierarchyLayout::computeBlockWidths	(	const GraphCopy &	GC,
		const GraphAttributes &	GCA,
		NodeArray< node > &	root,
		NodeArray< double > &	blockWidth
	)

private

Computes the width of each block, i.e., the maximal width of a node in the block, and stores it in blockWidth for the root of the block.

Parameters

GC	The input graph copy
GCA	The input graph copies (gives in particular the widths of nodes)
root	The root for each node (calculated by this method)
blockWidth	Is assigned the width of each block (stored for the root)

◆ doCall()

virtual void ogdf::FastSimpleHierarchyLayout::doCall	(	const HierarchyLevelsBase &	levels,
		GraphAttributes &	AGC
	)

overrideprotectedvirtual

Implements the actual algorithm call.

Must be implemented by derived classes.

Parameters

levels	is the input hierarchy.
AGC	has to be assigned the hierarchy layout.

Implements ogdf::HierarchyLayoutModule.

◆ downward() [1/2]

bool ogdf::FastSimpleHierarchyLayout::downward ( ) const

inline

Returns the option downward.

Definition at line 132 of file FastSimpleHierarchyLayout.h.

◆ downward() [2/2]

void ogdf::FastSimpleHierarchyLayout::downward ( bool d )

inline

Sets the option downward to d.

Definition at line 135 of file FastSimpleHierarchyLayout.h.

◆ horizontalCompactation()

void ogdf::FastSimpleHierarchyLayout::horizontalCompactation	(	const NodeArray< node > &	align,
		const HierarchyLevelsBase &	levels,
		const NodeArray< node > &	root,
		const NodeArray< double > &	blockWidth,
		NodeArray< double > &	x,
		const bool	leftToRight,
		bool	downward
	)

private

Calculate the coordinates for each node.

Parameters

align	The alignment to the next level node (align(v)=u <=> u is aligned to v)
levels	The Hierarchy
root	The root for each node
blockWidth	The width of each block
x	The x-coordinates for each node (calculated by this method)
leftToRight	The node direction on each level
downward	The level direction

◆ layerDistance() [1/2]

double ogdf::FastSimpleHierarchyLayout::layerDistance ( ) const

inline

Returns the option layer distance.

Definition at line 126 of file FastSimpleHierarchyLayout.h.

◆ layerDistance() [2/2]

void ogdf::FastSimpleHierarchyLayout::layerDistance ( double dist )

inline

Sets the option layer distance to dist.

Definition at line 129 of file FastSimpleHierarchyLayout.h.

◆ leftToRight() [1/2]

bool ogdf::FastSimpleHierarchyLayout::leftToRight ( ) const

inline

Returns the option left-to-right.

Definition at line 138 of file FastSimpleHierarchyLayout.h.

◆ leftToRight() [2/2]

void ogdf::FastSimpleHierarchyLayout::leftToRight ( bool b )

inline

Sets the option left-to-right to b.

Definition at line 141 of file FastSimpleHierarchyLayout.h.

◆ markType1Conflicts()

void ogdf::FastSimpleHierarchyLayout::markType1Conflicts	(	const HierarchyLevelsBase &	levels,
		bool	downward,
		NodeArray< NodeArray< bool > > &	type1Conflicts
	)

private

Preprocessing step to find all type1 conflicts.

A type1 conflict is a crossing of a inner segment with a non-inner segment.

This is for preferring straight inner segments.

Parameters

levels	The Hierarchy
downward	The level direction
type1Conflicts	is assigned the conflicts, (type1Conflicts[v])[u]=true means (u,v) is marked, u is the upper node

◆ nodeDistance() [1/2]

double ogdf::FastSimpleHierarchyLayout::nodeDistance ( ) const

inline

Returns the option node distance.

Definition at line 120 of file FastSimpleHierarchyLayout.h.

◆ nodeDistance() [2/2]

void ogdf::FastSimpleHierarchyLayout::nodeDistance ( double dist )

inline

Sets the option node distance to dist.

Definition at line 123 of file FastSimpleHierarchyLayout.h.

◆ operator=()

FastSimpleHierarchyLayout & ogdf::FastSimpleHierarchyLayout::operator= ( const FastSimpleHierarchyLayout & )

Assignment operator.

◆ placeBlock()

void ogdf::FastSimpleHierarchyLayout::placeBlock	(	node	v,
		NodeArray< node > &	sink,
		NodeArray< double > &	shift,
		NodeArray< double > &	x,
		const NodeArray< node > &	align,
		const HierarchyLevelsBase &	levels,
		const NodeArray< double > &	blockWidth,
		const NodeArray< node > &	root,
		const bool	leftToRight
	)

private

Calculate the coordinate for root nodes (placing)

Parameters

v	The root node to place
sink	The Sink for each node. A sink identifies each block class (calculated by this method)
shift	The shift for each class (calculated by this method)
x	The class relative x-coordinate for each node (calculated by this method)
align	The alignment to the next level node (align(v)=u <=> u is aligned to v)
levels	The Hierarchy
blockWidth	The width of each block
root	The root for each node
leftToRight	The node direction on each level

◆ pred()

node ogdf::FastSimpleHierarchyLayout::pred	(	const node	v,
		const HierarchyLevelsBase &	levels,
		const bool	leftToRight
	)

private

Predecessor of v on the same level,.

Parameters

v	The node for which the predecessor should be calculated.
levels	The Hierarchy
leftToRight	If true the left predecessor is choosen. Otherwise the right predecessor.

Returns: Predescessor on the same level. nullptr if there is no predecessor.

◆ verticalAlignment()

void ogdf::FastSimpleHierarchyLayout::verticalAlignment	(	const HierarchyLevelsBase &	levels,
		NodeArray< node > &	root,
		NodeArray< node > &	align,
		const NodeArray< NodeArray< bool > > &	type1Conflicts,
		const bool	downward,
		const bool	leftToRight
	)

private

Align each node to a node on the next higher level.

The result is a blockgraph where each node is in a block whith a nother node when they have the same root.

Parameters

levels	The Hierarchy
root	The root for each node (calculated by this method)
align	The alignment to the next level node (align(v)=u <=> u is aligned to v) (calculated by this method)
type1Conflicts	Type1 conflicts to prefer straight inner segments
downward	The level direction
leftToRight	The node direction on each level

◆ virtualTwinNode()

node ogdf::FastSimpleHierarchyLayout::virtualTwinNode	(	const HierarchyLevelsBase &	levels,
		const node	v,
		const HierarchyLevelsBase::TraversingDir	dir
	)		const

private

The twin of an inner Segment.

Returns: Parent node which is connected by an inner segment. nullptr if there is no parent segment or if the segment is not an inner segment.

Member Data Documentation

◆ m_balanced

bool ogdf::FastSimpleHierarchyLayout::m_balanced

private

stores the option balanced.

Definition at line 93 of file FastSimpleHierarchyLayout.h.

◆ m_downward

bool ogdf::FastSimpleHierarchyLayout::m_downward

private

stores the option downward.

Definition at line 94 of file FastSimpleHierarchyLayout.h.

◆ m_leftToRight

bool ogdf::FastSimpleHierarchyLayout::m_leftToRight

private

stores the option left-to-right.

Definition at line 95 of file FastSimpleHierarchyLayout.h.

◆ m_minXSep

double ogdf::FastSimpleHierarchyLayout::m_minXSep

private

stores the option node distance.

Definition at line 91 of file FastSimpleHierarchyLayout.h.

◆ m_ySep

double ogdf::FastSimpleHierarchyLayout::m_ySep

private

stores the option layer distance.

Definition at line 92 of file FastSimpleHierarchyLayout.h.

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

include/ogdf/layered/FastSimpleHierarchyLayout.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Optional Parameters

Constructor & Destructor Documentation

◆ FastSimpleHierarchyLayout() [1/2]

◆ FastSimpleHierarchyLayout() [2/2]

◆ ~FastSimpleHierarchyLayout()

Member Function Documentation

◆ balanced() [1/2]

◆ balanced() [2/2]

◆ computeBlockWidths()

◆ doCall()

◆ downward() [1/2]

◆ downward() [2/2]

◆ horizontalCompactation()

◆ layerDistance() [1/2]

◆ layerDistance() [2/2]

◆ leftToRight() [1/2]

◆ leftToRight() [2/2]

◆ markType1Conflicts()

◆ nodeDistance() [1/2]

◆ nodeDistance() [2/2]

◆ operator=()

◆ placeBlock()

◆ pred()

◆ verticalAlignment()

◆ virtualTwinNode()

Member Data Documentation

◆ m_balanced

◆ m_downward

◆ m_leftToRight

◆ m_minXSep

◆ m_ySep

Open
Graph Drawing
Framework