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. More...

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

	~TreeLayout ()

Algorithm call
void	call (GraphAttributes &GA)
	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 ()

virtual void	call (GraphAttributes &GA, GraphConstraints &GC)
	Computes a layout of graph GA wrt the constraints in GC (if applicable). More...

void	operator() (GraphAttributes &GA)
	Computes a layout of graph GA. More...

Private Member Functions
void	adjustEdgeDirections (Graph &G, node v, node parent)

void	apportion (node subtree, node &defaultAncestor, const GraphAttributes &AG, bool upDown)

void	computeXCoordinatesAndEdgeShapes (node root, GraphAttributes &AG)

void	computeYCoordinatesAndEdgeShapes (node root, GraphAttributes &AG)

void	deleteTreeStructure ()

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 (node subtree, const GraphAttributes &AG, bool upDown)

void	initializeTreeStructure (const Graph &tree, List< node > &roots)

int	isLeaf (node v) const

node	nextOnLeftContour (node v) const

node	nextOnRightContour (node v) const

void	secondWalkX (node subtree, double modifierSum, GraphAttributes &AG)

void	secondWalkY (node subtree, double modifierSum, GraphAttributes &AG)

void	setRoot (GraphAttributes &AG, Graph &tree)

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

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

void	undoReverseEdges (GraphAttributes &AG)

Private Attributes
NodeArray< node >	m_ancestor
	Actual highest ancestor. More...

NodeArray< double >	m_change
	Change of shift applied to subtrees. More...

NodeArray< node >	m_firstChild
	Leftmost child, 0 if leaf. More...

NodeArray< node >	m_lastChild
	Rightmost child, 0 if leaf. More...

NodeArray< node >	m_leftSibling
	Left sibling, 0 if none. More...

double	m_levelDistance
	The minimal distance between levels. More...

NodeArray< double >	m_modifier
	Modifier of x-coordinates. More...

NodeArray< int >	m_number
	Consecutive numbers for children. More...

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

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

NodeArray< node >	m_parent
	Parent node, 0 if root. More...

Graph *	m_pGraph
	The input graph. More...

NodeArray< double >	m_preliminary
	Preliminary x-coordinates. More...

SListPure< edge >	m_reversedEdges
	List of temporarily removed edges. More...

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

NodeArray< double >	m_shift
	Shift applied to subtrees. More...

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

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

NodeArray< node >	m_thread
	Thread, 0 if none. 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	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 110 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 113 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 &	GA,
		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

double ogdf::TreeLayout::levelDistance ( ) const

inline

Returns the minimal required vertical distance between levels.

Definition at line 206 of file TreeLayout.h.

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

inline

Sets the minimal required vertical distance between levels to x.

Definition at line 209 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 224 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 227 of file TreeLayout.h.

bool ogdf::TreeLayout::orthogonalLayout ( ) const

inline

Returns whether orthogonal edge routing style is used.

Definition at line 218 of file TreeLayout.h.

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

inline

Sets the option for orthogonal edge routing style to b.

Definition at line 221 of file TreeLayout.h.

RootSelectionType ogdf::TreeLayout::rootSelection ( ) const

inline

Returns the option that determines how the root is selected.

Definition at line 230 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 233 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 194 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 197 of file TreeLayout.h.

double ogdf::TreeLayout::subtreeDistance ( ) const

inline

Returns the minimal required horizontal distance between subtrees.

Definition at line 200 of file TreeLayout.h.

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

inline

Sets the minimal required horizontal distance between subtrees to x.

Definition at line 203 of file TreeLayout.h.

double ogdf::TreeLayout::treeDistance ( ) const

inline

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

Definition at line 212 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 215 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 136 of file TreeLayout.h.

NodeArray<double> ogdf::TreeLayout::m_change

private

Change of shift applied to subtrees.

Definition at line 140 of file TreeLayout.h.

NodeArray<node> ogdf::TreeLayout::m_firstChild

private

Leftmost child, 0 if leaf.

Definition at line 133 of file TreeLayout.h.

NodeArray<node> ogdf::TreeLayout::m_lastChild

private

Rightmost child, 0 if leaf.

Definition at line 134 of file TreeLayout.h.

NodeArray<node> ogdf::TreeLayout::m_leftSibling

private

Left sibling, 0 if none.

Definition at line 132 of file TreeLayout.h.

double ogdf::TreeLayout::m_levelDistance

private

The minimal distance between levels.

Definition at line 122 of file TreeLayout.h.

NodeArray<double> ogdf::TreeLayout::m_modifier

private

Modifier of x-coordinates.

Definition at line 139 of file TreeLayout.h.

NodeArray<int> ogdf::TreeLayout::m_number

private

Consecutive numbers for children.

Definition at line 129 of file TreeLayout.h.

Orientation ogdf::TreeLayout::m_orientation

private

Option for orientation of tree layout.

Definition at line 126 of file TreeLayout.h.

bool ogdf::TreeLayout::m_orthogonalLayout

private

Option for orthogonal style (yes/no).

Definition at line 125 of file TreeLayout.h.

NodeArray<node> ogdf::TreeLayout::m_parent

private

Parent node, 0 if root.

Definition at line 131 of file TreeLayout.h.

Graph* ogdf::TreeLayout::m_pGraph

private

The input graph.

Definition at line 144 of file TreeLayout.h.

NodeArray<double> ogdf::TreeLayout::m_preliminary

private

Preliminary x-coordinates.

Definition at line 138 of file TreeLayout.h.

SListPure<edge> ogdf::TreeLayout::m_reversedEdges

private

List of temporarily removed edges.

Definition at line 143 of file TreeLayout.h.

RootSelectionType ogdf::TreeLayout::m_selectRoot

private

Option for how to determine the root.

Definition at line 127 of file TreeLayout.h.

NodeArray<double> ogdf::TreeLayout::m_shift

private

Shift applied to subtrees.

Definition at line 141 of file TreeLayout.h.

double ogdf::TreeLayout::m_siblingDistance

private

The minimal distance between siblings.

Definition at line 120 of file TreeLayout.h.

double ogdf::TreeLayout::m_subtreeDistance

private

The minimal distance between subtrees.

Definition at line 121 of file TreeLayout.h.

NodeArray<node> ogdf::TreeLayout::m_thread

private

Thread, 0 if none.

Definition at line 135 of file TreeLayout.h.

double ogdf::TreeLayout::m_treeDistance

private

The minimal distance between trees.

Definition at line 123 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

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

Open
Graph Drawing
Framework