Open
Graph Drawing
Framework

 v.2015.05
 

ogdf::TreeLayout Class Reference

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
TreeLayoutoperator= (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< nodem_ancestor
 Actual highest ancestor. More...
 
NodeArray< double > m_change
 Change of shift applied to subtrees. More...
 
NodeArray< nodem_firstChild
 Leftmost child, 0 if leaf. More...
 
NodeArray< nodem_lastChild
 Rightmost child, 0 if leaf. More...
 
NodeArray< nodem_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< nodem_parent
 Parent node, 0 if root. More...
 
Graphm_pGraph
 The input graph. More...
 
NodeArray< double > m_preliminary
 Preliminary x-coordinates. More...
 
SListPure< edgem_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< nodem_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.

OptionTypeDefaultDescription
siblingDistancedouble20.0 The horizontal spacing between adjacent sibling nodes.
subtreeDistancedouble20.0 The horizontal spacing between adjacent subtrees.
levelDistancedouble50.0 The vertical spacing between adjacent levels.
treeDistancedouble50.0 The horizontal spacing between adjacent trees in a forest.
orthogonalLayoutboolfalse Determines whether edges are routed in an orthogonal or straight-line fashion.
orientationOrientation topToBottom Determines if the tree is laid out in a top-to-bottom, bottom-to-top, left-to-right, or right-to-left fashion.
selectRootRootSelectionType 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

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
GAis 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
GAis the input graph and will also be assigned the layout information.
Gis 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: