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. 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... | |
![]() | |
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... | |
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 110 of file TreeLayout.h.
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.
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 | ( | ) |
|
private |
|
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 & | GA, |
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. |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
private |
|
inline |
Returns the minimal required vertical distance between levels.
Definition at line 206 of file TreeLayout.h.
|
inline |
Sets the minimal required vertical distance between levels to x.
Definition at line 209 of file TreeLayout.h.
TreeLayout& ogdf::TreeLayout::operator= | ( | const TreeLayout & | tl | ) |
Assignment operator.
|
inline |
Returns the option that determines the orientation of the layout.
Definition at line 224 of file TreeLayout.h.
|
inline |
Sets the option that determines the orientation of the layout to orientation.
Definition at line 227 of file TreeLayout.h.
|
inline |
Returns whether orthogonal edge routing style is used.
Definition at line 218 of file TreeLayout.h.
|
inline |
Sets the option for orthogonal edge routing style to b.
Definition at line 221 of file TreeLayout.h.
|
inline |
Returns the option that determines how the root is selected.
Definition at line 230 of file TreeLayout.h.
|
inline |
Sets the option that determines how the root is selected to rootSelection.
Definition at line 233 of file TreeLayout.h.
|
private |
|
private |
|
private |
|
private |
|
private |
|
inline |
Returns the the minimal required horizontal distance between siblings.
Definition at line 194 of file TreeLayout.h.
|
inline |
Sets the the minimal required horizontal distance between siblings to x.
Definition at line 197 of file TreeLayout.h.
|
inline |
Returns the minimal required horizontal distance between subtrees.
Definition at line 200 of file TreeLayout.h.
|
inline |
Sets the minimal required horizontal distance between subtrees to x.
Definition at line 203 of file TreeLayout.h.
|
inline |
Returns the minimal required horizontal distance between trees in the forest.
Definition at line 212 of file TreeLayout.h.
|
inline |
Sets the minimal required horizontal distance between trees in the forest to x.
Definition at line 215 of file TreeLayout.h.
|
private |
Actual highest ancestor.
Definition at line 136 of file TreeLayout.h.
|
private |
Change of shift applied to subtrees.
Definition at line 140 of file TreeLayout.h.
Leftmost child, 0 if leaf.
Definition at line 133 of file TreeLayout.h.
Rightmost child, 0 if leaf.
Definition at line 134 of file TreeLayout.h.
Left sibling, 0 if none.
Definition at line 132 of file TreeLayout.h.
|
private |
The minimal distance between levels.
Definition at line 122 of file TreeLayout.h.
|
private |
Modifier of x-coordinates.
Definition at line 139 of file TreeLayout.h.
|
private |
Consecutive numbers for children.
Definition at line 129 of file TreeLayout.h.
|
private |
Option for orientation of tree layout.
Definition at line 126 of file TreeLayout.h.
|
private |
Option for orthogonal style (yes/no).
Definition at line 125 of file TreeLayout.h.
Parent node, 0 if root.
Definition at line 131 of file TreeLayout.h.
|
private |
The input graph.
Definition at line 144 of file TreeLayout.h.
|
private |
Preliminary x-coordinates.
Definition at line 138 of file TreeLayout.h.
List of temporarily removed edges.
Definition at line 143 of file TreeLayout.h.
|
private |
Option for how to determine the root.
Definition at line 127 of file TreeLayout.h.
|
private |
Shift applied to subtrees.
Definition at line 141 of file TreeLayout.h.
|
private |
The minimal distance between siblings.
Definition at line 120 of file TreeLayout.h.
|
private |
The minimal distance between subtrees.
Definition at line 121 of file TreeLayout.h.
Thread, 0 if none.
Definition at line 135 of file TreeLayout.h.
|
private |
The minimal distance between trees.
Definition at line 123 of file TreeLayout.h.