The tree layout algorithm. More...
#include <ogdf/tree/TreeLayout.h>
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. | |
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.
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.
Determines how to select the root of the tree.
| 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.
| 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 | ( | ) |
| 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.
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.
| 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.
Sorts the adjacency entries according to the positions of adjacent vertices in GA.
| 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.
| 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] |
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.
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.