Open Graph Drawing Framework  v.2007.11

Overview Class Hierarchy Class Index Class List Members Namespaces Source Files Search for:

ogdf::TreeLayout Class Reference

The tree layout algorithm. More...

#include <TreeLayout.h>

Inheritance diagram for ogdf::TreeLayout:

List of all members.

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 117 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 120 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::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.

double ogdf::TreeLayout::siblingDistance

(

)

const [inline]

Returns the the minimal required horizontal distance between siblings.

Definition at line 201 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 204 of file TreeLayout.h.

double ogdf::TreeLayout::subtreeDistance

(

)

const [inline]

Returns the minimal required horizontal distance between subtrees.

Definition at line 207 of file TreeLayout.h.

void ogdf::TreeLayout::subtreeDistance

(

double

x

)

[inline]

Sets the minimal required horizontal distance between subtrees to x.

Definition at line 210 of file TreeLayout.h.

double ogdf::TreeLayout::levelDistance

(

)

const [inline]

Returns the minimal required vertical distance between levels.

Definition at line 213 of file TreeLayout.h.

void ogdf::TreeLayout::levelDistance

(

double

x

)

[inline]

Sets the minimal required vertical distance between levels to x.

Definition at line 216 of file TreeLayout.h.

double ogdf::TreeLayout::treeDistance

(

)

const [inline]

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

Definition at line 219 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 222 of file TreeLayout.h.

bool ogdf::TreeLayout::orthogonalLayout

(

)

const [inline]

Returns whether orthogonal edge routing style is used.

Definition at line 225 of file TreeLayout.h.

void ogdf::TreeLayout::orthogonalLayout

(

bool

b

)

[inline]

Sets the option for orthogonal edge routing style to b.

Definition at line 228 of file TreeLayout.h.

Orientation ogdf::TreeLayout::orientation

(

)

const [inline]

Returns the option that determines the orientation of the layout.

Definition at line 231 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 234 of file TreeLayout.h.

RootSelectionType ogdf::TreeLayout::rootSelection

(

)

const [inline]

Returns the option that determines how the root is selected.

Definition at line 237 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 240 of file TreeLayout.h.

TreeLayout& ogdf::TreeLayout::operator=

(

const TreeLayout &

tl

)

Assignment operator.

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

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

void ogdf::TreeLayout::undoReverseEdges

(

GraphAttributes &

AG

)

[private]

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

void ogdf::TreeLayout::deleteTreeStructure

(

)

[private]

int ogdf::TreeLayout::isLeaf

(

node

v

)

const [private]

node ogdf::TreeLayout::nextOnLeftContour

(

node

v

)

const [private]

node ogdf::TreeLayout::nextOnRightContour

(

node

v

)

const [private]

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

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

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::computeYCoordinatesAndEdgeShapes	(	node	root,
		GraphAttributes &	AG
	)			[private]

void ogdf::TreeLayout::computeXCoordinatesAndEdgeShapes	(	node	root,
		GraphAttributes &	AG
	)			[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::findMaxX	(	GraphAttributes &	AG,
		node	root,
		double &	maxX
	)			[private]

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

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

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

---

Member Data Documentation

double ogdf::TreeLayout::m_siblingDistance [private]

The minimal distance between siblings.

Definition at line 127 of file TreeLayout.h.

double ogdf::TreeLayout::m_subtreeDistance [private]

The minimal distance between subtrees.

Definition at line 128 of file TreeLayout.h.

double ogdf::TreeLayout::m_levelDistance [private]

The minimal distance between levels.

Definition at line 129 of file TreeLayout.h.

double ogdf::TreeLayout::m_treeDistance [private]

The minimal distance between trees.

Definition at line 130 of file TreeLayout.h.

bool ogdf::TreeLayout::m_orthogonalLayout [private]

Option for orthogonal style (yes/no).

Definition at line 132 of file TreeLayout.h.

Orientation ogdf::TreeLayout::m_orientation [private]

Option for orientation of tree layout.

Definition at line 133 of file TreeLayout.h.

RootSelectionType ogdf::TreeLayout::m_selectRoot [private]

Option for how to determine the root.

Definition at line 134 of file TreeLayout.h.

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

Consecutive numbers for children.

Definition at line 136 of file TreeLayout.h.

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

Parent node, 0 if root.

Definition at line 138 of file TreeLayout.h.

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

Left sibling, 0 if none.

Definition at line 139 of file TreeLayout.h.

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

Leftmost child, 0 if leaf.

Definition at line 140 of file TreeLayout.h.

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

Rightmost child, 0 if leaf.

Definition at line 141 of file TreeLayout.h.

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

Thread, 0 if none.

Definition at line 142 of file TreeLayout.h.

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

Actual highest ancestor.

Definition at line 143 of file TreeLayout.h.

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

Preliminary x-coordinates.

Definition at line 145 of file TreeLayout.h.

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

Modifier of x-coordinates.

Definition at line 146 of file TreeLayout.h.

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

Change of shift applied to subtrees.

Definition at line 147 of file TreeLayout.h.

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

Shift applied to subtrees.

Definition at line 148 of file TreeLayout.h.

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

List of temporarily removed edges.

Definition at line 150 of file TreeLayout.h.

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

The input graph.

Definition at line 151 of file TreeLayout.h.

---

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

• ogdf/tree/TreeLayout.h

---