The tree layout algorithm. More...

#include <ogdf/tree/TreeLayout.h>

Inheritance diagram for ogdf::TreeLayout:

Public Types
enum	RootSelectionType { RootSelectionType::Source, RootSelectionType::Sink, RootSelectionType::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. More...

	TreeLayout (const TreeLayout &tl)
	Copy constructor. More...

	~TreeLayout ()=default
	Destructor. More...

Algorithm call
virtual void	call (GraphAttributes &GA) override
	Calls tree layout for graph attributes `GA`. More...

void	callSortByPositions (GraphAttributes &GA, Graph &G)
	Calls tree layout for graph attributes `GA`. More...

Optional parameters
double	siblingDistance () const
	Returns the the minimal required horizontal distance between siblings. More...

void	siblingDistance (double x)
	Sets the the minimal required horizontal distance between siblings to `x`. More...

double	subtreeDistance () const
	Returns the minimal required horizontal distance between subtrees. More...

void	subtreeDistance (double x)
	Sets the minimal required horizontal distance between subtrees to `x`. More...

double	levelDistance () const
	Returns the minimal required vertical distance between levels. More...

void	levelDistance (double x)
	Sets the minimal required vertical distance between levels to `x`. More...

double	treeDistance () const
	Returns the minimal required horizontal distance between trees in the forest. More...

void	treeDistance (double x)
	Sets the minimal required horizontal distance between trees in the forest to `x`. More...

bool	orthogonalLayout () const
	Returns whether orthogonal edge routing style is used. More...

void	orthogonalLayout (bool b)
	Sets the option for orthogonal edge routing style to `b`. More...

Orientation	orientation () const
	Returns the option that determines the orientation of the layout. More...

void	orientation (Orientation orientation)
	Sets the option that determines the orientation of the layout to `orientation`. More...

RootSelectionType	rootSelection () const
	Returns the option that determines how the root is selected. More...

void	rootSelection (RootSelectionType rootSelection)
	Sets the option that determines how the root is selected to `rootSelection`. More...

Operators
TreeLayout &	operator= (const TreeLayout &tl)
	Assignment operator. 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
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. More...

Orientation	m_orientation
	Option for orientation of tree layout. More...

bool	m_orthogonalLayout
	Option for orthogonal style (yes/no). More...

RootSelectionType	m_selectRoot
	Option for how to determine the root. More...

double	m_siblingDistance
	The minimal distance between siblings. More...

double	m_subtreeDistance
	The minimal distance between subtrees. More...

double	m_treeDistance
	The minimal distance between trees. More...

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 98 of file TreeLayout.h.

Member Enumeration Documentation

◆ RootSelectionType

enum 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 101 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 174 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 177 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 192 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 195 of file TreeLayout.h.

◆ orthogonalLayout() [1/2]

bool ogdf::TreeLayout::orthogonalLayout ( ) const

inline

Returns whether orthogonal edge routing style is used.

Definition at line 186 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 189 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 198 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 201 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 162 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 165 of file TreeLayout.h.

◆ subtreeDistance() [1/2]

double ogdf::TreeLayout::subtreeDistance ( ) const

inline

Returns the minimal required horizontal distance between subtrees.

Definition at line 168 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 171 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 180 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 183 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 110 of file TreeLayout.h.

◆ m_orientation

Orientation ogdf::TreeLayout::m_orientation

private

Option for orientation of tree layout.

Definition at line 114 of file TreeLayout.h.

◆ m_orthogonalLayout

bool ogdf::TreeLayout::m_orthogonalLayout

private

Option for orthogonal style (yes/no).

Definition at line 113 of file TreeLayout.h.

◆ m_selectRoot

RootSelectionType ogdf::TreeLayout::m_selectRoot

private

Option for how to determine the root.

Definition at line 115 of file TreeLayout.h.

◆ m_siblingDistance

double ogdf::TreeLayout::m_siblingDistance

private

The minimal distance between siblings.

Definition at line 108 of file TreeLayout.h.

◆ m_subtreeDistance

double ogdf::TreeLayout::m_subtreeDistance

private

The minimal distance between subtrees.

Definition at line 109 of file TreeLayout.h.

◆ m_treeDistance

double ogdf::TreeLayout::m_treeDistance

private

The minimal distance between trees.

Definition at line 111 of file TreeLayout.h.

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

include/ogdf/tree/TreeLayout.h

OpenGraph DrawingFramework

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Optional parameters

Member Enumeration Documentation

◆ RootSelectionType

Constructor & Destructor Documentation

◆ TreeLayout() [1/2]

◆ TreeLayout() [2/2]

◆ ~TreeLayout()

Member Function Documentation

◆ adjustEdgeDirections()

◆ apportion()

◆ call()

◆ callSortByPositions()

◆ computeXCoordinatesAndEdgeShapes()

◆ computeYCoordinatesAndEdgeShapes()

◆ findMaxX()

◆ findMaxY()

◆ findMinX()

◆ findMinY()

◆ firstWalk()

◆ levelDistance() [1/2]

◆ levelDistance() [2/2]

◆ operator=()

◆ orientation() [1/2]

◆ orientation() [2/2]

◆ orthogonalLayout() [1/2]

◆ orthogonalLayout() [2/2]

◆ rootSelection() [1/2]

◆ rootSelection() [2/2]

◆ secondWalkX()

◆ secondWalkY()

◆ setRoot()

◆ shiftTreeX()

◆ shiftTreeY()

◆ siblingDistance() [1/2]

◆ siblingDistance() [2/2]

◆ subtreeDistance() [1/2]

◆ subtreeDistance() [2/2]

◆ treeDistance() [1/2]

◆ treeDistance() [2/2]

◆ undoReverseEdges()

Member Data Documentation

◆ m_levelDistance

◆ m_orientation

◆ m_orthogonalLayout

◆ m_selectRoot

◆ m_siblingDistance

◆ m_subtreeDistance

◆ m_treeDistance

Open
Graph Drawing
Framework