The tree layout algorithm. More...

#include <ogdf/tree/TreeLayout.h>

Inheritance diagram for ogdf::TreeLayout:

Public Types
enum	RootSelectionType { rootIsSource, rootIsSink, rootByCoord }
	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 ()
Algorithm call

void	call (GraphAttributes &GA)
	Calls tree layout for graph attributes GA.
void	callSortByPositions (GraphAttributes &AG, 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.
Private Member Functions
void	adjustEdgeDirections (Graph &G, node v, node parent)
void	setRoot (GraphAttributes &AG, Graph &tree)
void	undoReverseEdges (GraphAttributes &AG)
void	initializeTreeStructure (const Graph &tree, List< node > &roots)
void	deleteTreeStructure ()
int	isLeaf (node v) const
node	nextOnLeftContour (node v) const
node	nextOnRightContour (node v) const
void	firstWalk (node subtree, const GraphAttributes &AG, bool upDown)
void	apportion (node subtree, node &defaultAncestor, const GraphAttributes &AG, bool upDown)
void	secondWalkX (node subtree, double modifierSum, GraphAttributes &AG)
void	secondWalkY (node subtree, double modifierSum, GraphAttributes &AG)
void	computeYCoordinatesAndEdgeShapes (node root, GraphAttributes &AG)
void	computeXCoordinatesAndEdgeShapes (node root, GraphAttributes &AG)
void	findMinX (GraphAttributes &AG, node root, double &minX)
void	findMinY (GraphAttributes &AG, node root, double &minY)
void	findMaxX (GraphAttributes &AG, node root, double &maxX)
void	findMaxY (GraphAttributes &AG, node root, double &maxY)
void	shiftTreeX (GraphAttributes &AG, node root, double shift)
void	shiftTreeY (GraphAttributes &AG, node root, double shift)
Private Attributes
double	m_siblingDistance
	The minimal distance between siblings.
double	m_subtreeDistance
	The minimal distance between subtrees.
double	m_levelDistance
	The minimal distance between levels.
double	m_treeDistance
	The minimal distance between trees.
bool	m_orthogonalLayout
	Option for orthogonal style (yes/no).
Orientation	m_orientation
	Option for orientation of tree layout.
RootSelectionType	m_selectRoot
	Option for how to determine the root.
NodeArray< int >	m_number
	Consecutive numbers for children.
NodeArray< node >	m_parent
	Parent node, 0 if root.
NodeArray< node >	m_leftSibling
	Left sibling, 0 if none.
NodeArray< node >	m_firstChild
	Leftmost child, 0 if leaf.
NodeArray< node >	m_lastChild
	Rightmost child, 0 if leaf.
NodeArray< node >	m_thread
	Thread, 0 if none.
NodeArray< node >	m_ancestor
	Actual highest ancestor.
NodeArray< double >	m_preliminary
	Preliminary x-coordinates.
NodeArray< double >	m_modifier
	Modifier of x-coordinates.
NodeArray< double >	m_change
	Change of shift applied to subtrees.
NodeArray< double >	m_shift
	Shift applied to subtrees.
SListPure< edge >	m_reversedEdges
	List of temporarily removed edges.
Graph *	m_pGraph
	The input graph.

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	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	rootIsSource	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 th eselection strategy given by selectRoot.

Definition at line 119 of file TreeLayout.h.

Member Enumeration Documentation

enum ogdf::TreeLayout::RootSelectionType

Determines how to select the root of the tree.

Enumerator:

rootIsSource	Select a source in the graph.
rootIsSink	Select a sink in the graph.
rootByCoord	Use the coordinates, e.g., select the topmost node if orientation is topToBottom.

Definition at line 122 of file TreeLayout.h.

Constructor & Destructor Documentation

ogdf::TreeLayout::TreeLayout ( )

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

ogdf::TreeLayout::TreeLayout ( const TreeLayout & tl )

Copy constructor.

ogdf::TreeLayout::~TreeLayout ( )

Member Function Documentation

void ogdf::TreeLayout::adjustEdgeDirections	(	Graph &	G,
		node	v,
		node	parent
	)			`[private]`

void ogdf::TreeLayout::apportion	(	node	subtree,
		node &	defaultAncestor,
		const GraphAttributes &	AG,
		bool	upDown
	)			`[private]`

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

Calls tree layout for graph attributes GA.

Precondition:: The graph is a tree.

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.

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

Calls tree layout for graph attributes GA.

Precondition:: The graph is a tree.

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.

void ogdf::TreeLayout::computeXCoordinatesAndEdgeShapes	(	node	root,
		GraphAttributes &	AG
	)			`[private]`

void ogdf::TreeLayout::computeYCoordinatesAndEdgeShapes	(	node	root,
		GraphAttributes &	AG
	)			`[private]`

void ogdf::TreeLayout::deleteTreeStructure ( ) [private]

void ogdf::TreeLayout::findMaxX	(	GraphAttributes &	AG,
		node	root,
		double &	maxX
	)			`[private]`

void ogdf::TreeLayout::findMaxY	(	GraphAttributes &	AG,
		node	root,
		double &	maxY
	)			`[private]`

void ogdf::TreeLayout::findMinX	(	GraphAttributes &	AG,
		node	root,
		double &	minX
	)			`[private]`

void ogdf::TreeLayout::findMinY	(	GraphAttributes &	AG,
		node	root,
		double &	minY
	)			`[private]`

void ogdf::TreeLayout::firstWalk	(	node	subtree,
		const GraphAttributes &	AG,
		bool	upDown
	)			`[private]`

void ogdf::TreeLayout::initializeTreeStructure	(	const Graph &	tree,
		List< node > &	roots
	)			`[private]`

int ogdf::TreeLayout::isLeaf ( node v ) const [private]

void ogdf::TreeLayout::levelDistance ( double x ) [inline]

Sets the minimal required vertical distance between levels to x.

Definition at line 218 of file TreeLayout.h.

double ogdf::TreeLayout::levelDistance ( ) const [inline]

Returns the minimal required vertical distance between levels.

Definition at line 215 of file TreeLayout.h.

node ogdf::TreeLayout::nextOnLeftContour ( node v ) const [private]

node ogdf::TreeLayout::nextOnRightContour ( node v ) const [private]

TreeLayout& ogdf::TreeLayout::operator= ( const TreeLayout & tl )

Assignment operator.

Orientation ogdf::TreeLayout::orientation ( ) const [inline]

Returns the option that determines the orientation of the layout.

Definition at line 233 of file TreeLayout.h.

void ogdf::TreeLayout::orientation ( Orientation orientation ) [inline]

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

Definition at line 236 of file TreeLayout.h.

void ogdf::TreeLayout::orthogonalLayout ( bool b ) [inline]

Sets the option for orthogonal edge routing style to b.

Definition at line 230 of file TreeLayout.h.

bool ogdf::TreeLayout::orthogonalLayout ( ) const [inline]

Returns whether orthogonal edge routing style is used.

Definition at line 227 of file TreeLayout.h.

RootSelectionType ogdf::TreeLayout::rootSelection ( ) const [inline]

Returns the option that determines how the root is selected.

Definition at line 239 of file TreeLayout.h.

void ogdf::TreeLayout::rootSelection ( RootSelectionType rootSelection ) [inline]

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

Definition at line 242 of file TreeLayout.h.

void ogdf::TreeLayout::secondWalkX	(	node	subtree,
		double	modifierSum,
		GraphAttributes &	AG
	)			`[private]`

void ogdf::TreeLayout::secondWalkY	(	node	subtree,
		double	modifierSum,
		GraphAttributes &	AG
	)			`[private]`

void ogdf::TreeLayout::setRoot	(	GraphAttributes &	AG,
		Graph &	tree
	)			`[private]`

void ogdf::TreeLayout::shiftTreeX	(	GraphAttributes &	AG,
		node	root,
		double	shift
	)			`[private]`

void ogdf::TreeLayout::shiftTreeY	(	GraphAttributes &	AG,
		node	root,
		double	shift
	)			`[private]`

double ogdf::TreeLayout::siblingDistance ( ) const [inline]

Returns the the minimal required horizontal distance between siblings.

Definition at line 203 of file TreeLayout.h.

void ogdf::TreeLayout::siblingDistance ( double x ) [inline]

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

Definition at line 206 of file TreeLayout.h.

void ogdf::TreeLayout::subtreeDistance ( double x ) [inline]

Sets the minimal required horizontal distance between subtrees to x.

Definition at line 212 of file TreeLayout.h.

double ogdf::TreeLayout::subtreeDistance ( ) const [inline]

Returns the minimal required horizontal distance between subtrees.

Definition at line 209 of file TreeLayout.h.

void ogdf::TreeLayout::treeDistance ( double x ) [inline]

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

Definition at line 224 of file TreeLayout.h.

double ogdf::TreeLayout::treeDistance ( ) const [inline]

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

Definition at line 221 of file TreeLayout.h.

void ogdf::TreeLayout::undoReverseEdges ( GraphAttributes & AG ) [private]

Member Data Documentation

NodeArray<node> ogdf::TreeLayout::m_ancestor [private]

Actual highest ancestor.

Definition at line 145 of file TreeLayout.h.

NodeArray<double> ogdf::TreeLayout::m_change [private]

Change of shift applied to subtrees.

Definition at line 149 of file TreeLayout.h.

NodeArray<node> ogdf::TreeLayout::m_firstChild [private]

Leftmost child, 0 if leaf.

Definition at line 142 of file TreeLayout.h.

NodeArray<node> ogdf::TreeLayout::m_lastChild [private]

Rightmost child, 0 if leaf.

Definition at line 143 of file TreeLayout.h.

NodeArray<node> ogdf::TreeLayout::m_leftSibling [private]

Left sibling, 0 if none.

Definition at line 141 of file TreeLayout.h.

double ogdf::TreeLayout::m_levelDistance [private]

The minimal distance between levels.

Definition at line 131 of file TreeLayout.h.

NodeArray<double> ogdf::TreeLayout::m_modifier [private]

Modifier of x-coordinates.

Definition at line 148 of file TreeLayout.h.

NodeArray<int> ogdf::TreeLayout::m_number [private]

Consecutive numbers for children.

Definition at line 138 of file TreeLayout.h.

Orientation ogdf::TreeLayout::m_orientation [private]

Option for orientation of tree layout.

Definition at line 135 of file TreeLayout.h.

bool ogdf::TreeLayout::m_orthogonalLayout [private]

Option for orthogonal style (yes/no).

Definition at line 134 of file TreeLayout.h.

NodeArray<node> ogdf::TreeLayout::m_parent [private]

Parent node, 0 if root.

Definition at line 140 of file TreeLayout.h.

Graph* ogdf::TreeLayout::m_pGraph [private]

The input graph.

Definition at line 153 of file TreeLayout.h.

NodeArray<double> ogdf::TreeLayout::m_preliminary [private]

Preliminary x-coordinates.

Definition at line 147 of file TreeLayout.h.

SListPure<edge> ogdf::TreeLayout::m_reversedEdges [private]

List of temporarily removed edges.

Definition at line 152 of file TreeLayout.h.

RootSelectionType ogdf::TreeLayout::m_selectRoot [private]

Option for how to determine the root.

Definition at line 136 of file TreeLayout.h.

NodeArray<double> ogdf::TreeLayout::m_shift [private]

Shift applied to subtrees.

Definition at line 150 of file TreeLayout.h.

double ogdf::TreeLayout::m_siblingDistance [private]

The minimal distance between siblings.

Definition at line 129 of file TreeLayout.h.

double ogdf::TreeLayout::m_subtreeDistance [private]

The minimal distance between subtrees.

Definition at line 130 of file TreeLayout.h.

NodeArray<node> ogdf::TreeLayout::m_thread [private]

Thread, 0 if none.

Definition at line 144 of file TreeLayout.h.

double ogdf::TreeLayout::m_treeDistance [private]

The minimal distance between trees.

Definition at line 132 of file TreeLayout.h.

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

ogdf/tree/TreeLayout.h

Open
Graph Drawing
Framework

ogdf::TreeLayout Class Reference

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Optional parameters

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

OpenGraph DrawingFramework

ogdf::TreeLayout Class Reference

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Optional parameters

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

Open
Graph Drawing
Framework