Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::TreeLayout Class Reference

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
TreeLayoutoperator= (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.

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

Member Enumeration Documentation

◆ RootSelectionType

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 96 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
GAis 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
GAis the input graph and will also be assigned the layout information.
Gis 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 170 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 173 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 188 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 191 of file TreeLayout.h.

◆ orthogonalLayout() [1/2]

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

Returns whether orthogonal edge routing style is used.

Definition at line 182 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 185 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 194 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 197 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 158 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 161 of file TreeLayout.h.

◆ subtreeDistance() [1/2]

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

Returns the minimal required horizontal distance between subtrees.

Definition at line 164 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 167 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 176 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 179 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 105 of file TreeLayout.h.

◆ m_orientation

Orientation ogdf::TreeLayout::m_orientation
private

Option for orientation of tree layout.

Definition at line 109 of file TreeLayout.h.

◆ m_orthogonalLayout

bool ogdf::TreeLayout::m_orthogonalLayout
private

Option for orthogonal style (yes/no).

Definition at line 108 of file TreeLayout.h.

◆ m_selectRoot

RootSelectionType ogdf::TreeLayout::m_selectRoot
private

Option for how to determine the root.

Definition at line 110 of file TreeLayout.h.

◆ m_siblingDistance

double ogdf::TreeLayout::m_siblingDistance
private

The minimal distance between siblings.

Definition at line 103 of file TreeLayout.h.

◆ m_subtreeDistance

double ogdf::TreeLayout::m_subtreeDistance
private

The minimal distance between subtrees.

Definition at line 104 of file TreeLayout.h.

◆ m_treeDistance

double ogdf::TreeLayout::m_treeDistance
private

The minimal distance between trees.

Definition at line 106 of file TreeLayout.h.


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