ogdf::TreeLayout Class Reference

The tree layout algorithm. More...

#include <ogdf/tree/TreeLayout.h>

Inheritance diagram for ogdf::TreeLayout:

Public Types
enum class	RootSelectionType { Source , Sink , ByCoord }
	Determines how to select the root of the tree. More...

Public Member Functions
	TreeLayout ()
	Creates an instance of tree layout and sets options to default values.
	TreeLayout (const TreeLayout &tl)
	Copy constructor.
	~TreeLayout ()=default
	Destructor.
Algorithm call
virtual void	call (GraphAttributes &GA) override
	Calls tree layout for graph attributes GA.
void	callSortByPositions (GraphAttributes &GA, Graph &G)
	Calls tree layout for graph attributes GA.
Optional parameters
double	siblingDistance () const
	Returns the the minimal required horizontal distance between siblings.
void	siblingDistance (double x)
	Sets the the minimal required horizontal distance between siblings to x.
double	subtreeDistance () const
	Returns the minimal required horizontal distance between subtrees.
void	subtreeDistance (double x)
	Sets the minimal required horizontal distance between subtrees to x.
double	levelDistance () const
	Returns the minimal required vertical distance between levels.
void	levelDistance (double x)
	Sets the minimal required vertical distance between levels to x.
double	treeDistance () const
	Returns the minimal required horizontal distance between trees in the forest.
void	treeDistance (double x)
	Sets the minimal required horizontal distance between trees in the forest to x.
bool	orthogonalLayout () const
	Returns whether orthogonal edge routing style is used.
void	orthogonalLayout (bool b)
	Sets the option for orthogonal edge routing style to b.
Orientation	orientation () const
	Returns the option that determines the orientation of the layout.
void	orientation (Orientation orientation)
	Sets the option that determines the orientation of the layout to orientation.
RootSelectionType	rootSelection () const
	Returns the option that determines how the root is selected.
void	rootSelection (RootSelectionType rootSelection)
	Sets the option that determines how the root is selected to rootSelection.
Operators
TreeLayout &	operator= (const TreeLayout &tl)
	Assignment operator.
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
void	adjustEdgeDirections (Graph &G, SListPure< edge > &reversedEdges, node v, node parent)
void	apportion (TreeStructure &ts, node subtree, node &defaultAncestor, bool upDown)
void	computeXCoordinatesAndEdgeShapes (node root, GraphAttributes &AG)
void	computeYCoordinatesAndEdgeShapes (node root, GraphAttributes &AG)
void	findMaxX (GraphAttributes &AG, node root, double &maxX)
void	findMaxY (GraphAttributes &AG, node root, double &maxY)
void	findMinX (GraphAttributes &AG, node root, double &minX)
void	findMinY (GraphAttributes &AG, node root, double &minY)
void	firstWalk (TreeStructure &ts, node subtree, bool upDown)
void	secondWalkX (TreeStructure &ts, node subtree, double modifierSum)
void	secondWalkY (TreeStructure &ts, node subtree, double modifierSum)
void	setRoot (GraphAttributes &AG, Graph &tree, SListPure< edge > &reversedEdges)
void	shiftTreeX (GraphAttributes &AG, node root, double shift)
void	shiftTreeY (GraphAttributes &AG, node root, double shift)
void	undoReverseEdges (GraphAttributes &AG, Graph &tree, SListPure< edge > &reversedEdges)

Private Attributes
double	m_levelDistance
	The minimal distance between levels.
Orientation	m_orientation
	Option for orientation of tree layout.
bool	m_orthogonalLayout
	Option for orthogonal style (yes/no).
RootSelectionType	m_selectRoot
	Option for how to determine the root.
double	m_siblingDistance
	The minimal distance between siblings.
double	m_subtreeDistance
	The minimal distance between subtrees.
double	m_treeDistance
	The minimal distance between trees.

Detailed Description

The tree layout algorithm.

The class TreeLayout represents the improved version of the tree layout algorithm by Walker presented in:

Christoph Buchheim, Michael Jünger, Sebastian Leipert: Drawing rooted trees in linear time. Software: Practice and Experience 36(6), pp. 651-665, 2006.

The algorithm also allows to lay out a forest, i.e., a collection of trees.

Optional parameters

Tree layout provides various optional parameters.

Option	Type	Default	Description
siblingDistance	double	20.0	The horizontal spacing between adjacent sibling nodes.
subtreeDistance	double	20.0	The horizontal spacing between adjacent subtrees.
levelDistance	double	50.0	The vertical spacing between adjacent levels.
treeDistance	double	50.0	The horizontal spacing between adjacent trees in a forest.
orthogonalLayout	bool	false	Determines whether edges are routed in an orthogonal or straight-line fashion.
orientation	Orientation	Orientation::topToBottom	Determines if the tree is laid out in a top-to-bottom, bottom-to-top, left-to-right, or right-to-left fashion.
selectRoot	RootSelectionType	RootSelectionType::Source	Determines how to select the root of the tree(s). Possible selection strategies are to take a (unique) source or sink in the graph, or to use the coordinates and to select the topmost node for top-to-bottom orientation, etc.

The spacing between nodes is determined by the siblingDistance, subtreeDistance, levelDistance, and treeDistance. The layout style is determined by orthogonalLayout and orientation; the root of the tree is selected according to the selection strategy given by selectRoot.

Definition at line 93 of file TreeLayout.h.

Member Enumeration Documentation

RootSelectionType

enum class ogdf::TreeLayout::RootSelectionType

strong

Determines how to select the root of the tree.

Enumerator
Source	Select a source in the graph.
Sink	Select a sink in the graph.
ByCoord	Use the coordinates, e.g., select the topmost node if orientation is topToBottom.

Definition at line 96 of file TreeLayout.h.

Constructor & Destructor Documentation

TreeLayout() [1/2]

ogdf::TreeLayout::TreeLayout

(

)

Creates an instance of tree layout and sets options to default values.

TreeLayout() [2/2]

ogdf::TreeLayout::TreeLayout

(

const TreeLayout &

tl

)

Copy constructor.

~TreeLayout()

ogdf::TreeLayout::~TreeLayout ( )

default

Destructor.

Member Function Documentation

adjustEdgeDirections()

void ogdf::TreeLayout::adjustEdgeDirections ( Graph &  G, SListPure< edge > &  reversedEdges, node  v, node  parent  )

private

apportion()

void ogdf::TreeLayout::apportion ( TreeStructure &  ts, node  subtree, node &  defaultAncestor, bool  upDown  )

private

call()

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

overridevirtual

Calls tree layout for graph attributes GA.

Precondition

The graph is a tree or a forest.

The order of children is given by the adjacency lists. The successor of the unique in-edge of a non-root node leads to its leftmost child; the leftmost child of the root is given by its first adjacency entry.

Parameters

GA	is the input graph and will also be assigned the layout information.

Implements ogdf::LayoutModule.

callSortByPositions()

void ogdf::TreeLayout::callSortByPositions	(	GraphAttributes &	GA,
		Graph &	G
	)

Calls tree layout for graph attributes GA.

Precondition

The graph is a tree or a forest.

Sorts the adjacency entries according to the positions of adjacent vertices in GA.

Parameters

GA	is the input graph and will also be assigned the layout information.
G	is the graph associated with GA.

computeXCoordinatesAndEdgeShapes()

void ogdf::TreeLayout::computeXCoordinatesAndEdgeShapes ( node  root, GraphAttributes &  AG  )

private

computeYCoordinatesAndEdgeShapes()

void ogdf::TreeLayout::computeYCoordinatesAndEdgeShapes ( node  root, GraphAttributes &  AG  )

private

findMaxX()

void ogdf::TreeLayout::findMaxX ( GraphAttributes &  AG, node  root, double &  maxX  )

private

findMaxY()

void ogdf::TreeLayout::findMaxY ( GraphAttributes &  AG, node  root, double &  maxY  )

private

findMinX()

void ogdf::TreeLayout::findMinX ( GraphAttributes &  AG, node  root, double &  minX  )

private

findMinY()

void ogdf::TreeLayout::findMinY ( GraphAttributes &  AG, node  root, double &  minY  )

private

firstWalk()

void ogdf::TreeLayout::firstWalk ( TreeStructure &  ts, node  subtree, bool  upDown  )

private

levelDistance() [1/2]

double ogdf::TreeLayout::levelDistance ( ) const

inline

Returns the minimal required vertical distance between levels.

Definition at line 169 of file TreeLayout.h.

levelDistance() [2/2]

void ogdf::TreeLayout::levelDistance ( double  x )

inline

Sets the minimal required vertical distance between levels to x.

Definition at line 172 of file TreeLayout.h.

operator=()

TreeLayout & ogdf::TreeLayout::operator=

(

const TreeLayout &

tl

)

Assignment operator.

orientation() [1/2]

Orientation ogdf::TreeLayout::orientation ( ) const

inline

Returns the option that determines the orientation of the layout.

Definition at line 187 of file TreeLayout.h.

orientation() [2/2]

void ogdf::TreeLayout::orientation ( Orientation  orientation )

inline

Sets the option that determines the orientation of the layout to orientation.

Definition at line 190 of file TreeLayout.h.

orthogonalLayout() [1/2]

bool ogdf::TreeLayout::orthogonalLayout ( ) const

inline

Returns whether orthogonal edge routing style is used.

Definition at line 181 of file TreeLayout.h.

orthogonalLayout() [2/2]

void ogdf::TreeLayout::orthogonalLayout ( bool  b )

inline

Sets the option for orthogonal edge routing style to b.

Definition at line 184 of file TreeLayout.h.

rootSelection() [1/2]

RootSelectionType ogdf::TreeLayout::rootSelection ( ) const

inline

Returns the option that determines how the root is selected.

Definition at line 193 of file TreeLayout.h.

rootSelection() [2/2]

void ogdf::TreeLayout::rootSelection ( RootSelectionType  rootSelection )

inline

Sets the option that determines how the root is selected to rootSelection.

Definition at line 196 of file TreeLayout.h.

secondWalkX()

void ogdf::TreeLayout::secondWalkX ( TreeStructure &  ts, node  subtree, double  modifierSum  )

private

secondWalkY()

void ogdf::TreeLayout::secondWalkY ( TreeStructure &  ts, node  subtree, double  modifierSum  )

private

setRoot()

void ogdf::TreeLayout::setRoot ( GraphAttributes &  AG, Graph &  tree, SListPure< edge > &  reversedEdges  )

private

shiftTreeX()

void ogdf::TreeLayout::shiftTreeX ( GraphAttributes &  AG, node  root, double  shift  )

private

shiftTreeY()

void ogdf::TreeLayout::shiftTreeY ( GraphAttributes &  AG, node  root, double  shift  )

private

siblingDistance() [1/2]

double ogdf::TreeLayout::siblingDistance ( ) const

inline

Returns the the minimal required horizontal distance between siblings.

Definition at line 157 of file TreeLayout.h.

siblingDistance() [2/2]

void ogdf::TreeLayout::siblingDistance ( double  x )

inline

Sets the the minimal required horizontal distance between siblings to x.

Definition at line 160 of file TreeLayout.h.

subtreeDistance() [1/2]

double ogdf::TreeLayout::subtreeDistance ( ) const

inline

Returns the minimal required horizontal distance between subtrees.

Definition at line 163 of file TreeLayout.h.

subtreeDistance() [2/2]

void ogdf::TreeLayout::subtreeDistance ( double  x )

inline

Sets the minimal required horizontal distance between subtrees to x.

Definition at line 166 of file TreeLayout.h.

treeDistance() [1/2]

double ogdf::TreeLayout::treeDistance ( ) const

inline

Returns the minimal required horizontal distance between trees in the forest.

Definition at line 175 of file TreeLayout.h.

treeDistance() [2/2]

void ogdf::TreeLayout::treeDistance ( double  x )

inline

Sets the minimal required horizontal distance between trees in the forest to x.

Definition at line 178 of file TreeLayout.h.

undoReverseEdges()

void ogdf::TreeLayout::undoReverseEdges ( GraphAttributes &  AG, Graph &  tree, SListPure< edge > &  reversedEdges  )

private

Member Data Documentation

m_levelDistance

double ogdf::TreeLayout::m_levelDistance

private

The minimal distance between levels.

Definition at line 105 of file TreeLayout.h.

m_orientation

Orientation ogdf::TreeLayout::m_orientation

private

Option for orientation of tree layout.

Definition at line 109 of file TreeLayout.h.

m_orthogonalLayout

bool ogdf::TreeLayout::m_orthogonalLayout

private

Option for orthogonal style (yes/no).

Definition at line 108 of file TreeLayout.h.

m_selectRoot

RootSelectionType ogdf::TreeLayout::m_selectRoot

private

Option for how to determine the root.

Definition at line 110 of file TreeLayout.h.

m_siblingDistance

double ogdf::TreeLayout::m_siblingDistance

private

The minimal distance between siblings.

Definition at line 103 of file TreeLayout.h.

m_subtreeDistance

double ogdf::TreeLayout::m_subtreeDistance

private

The minimal distance between subtrees.

Definition at line 104 of file TreeLayout.h.

m_treeDistance

double ogdf::TreeLayout::m_treeDistance

private

The minimal distance between trees.

Definition at line 106 of file TreeLayout.h.

---

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

• include/ogdf/tree/TreeLayout.h