\src\ReingoldTilford\Algorithms\ReingoldTilfordAlgorithm.inc

Show: inherited
Table of Contents

\ReingoldTilford\Algorithms\ReingoldTilfordAlgorithm

Package: Default

This clas implements the Reingold-Tilford tree drawing algorithm. The alorithm works in O(n), where n is the number of nodes in the tree.

Properties

Propertyprivate  $BINARY_DEGREE= '2'
static

two children make an binary degree

Default value2Details
Type
Propertyprivate  $ONLY_CHILD_DEGREE= '1'
static

one child only makes an only child degree

Default value1Details
Type
Propertyprivate\ReingoldTilford\Algorithms\array[int]TreeNode  $children= 'null'

a reference to the children of the currently visited node (cached for performance reasons)

Default valuenullDetails
Type
\ReingoldTilford\Algorithms\array[int]TreeNode
Propertyprivatearray  $currentRightOutline= 'null'

the current right outline (i.e. right outline of the current left subtree)

Default valuenullDetails
Type
array
Propertyprivate\ReingoldTilford\Algorithms\SplObjectStorage  $depths= 'null'

hash table that maps a node to its depth

Default valuenullDetails
Type
\ReingoldTilford\Algorithms\SplObjectStorage
Propertyprivate\ReingoldTilford\Algorithms\SplObjectStorage  $leftOutline= 'null'

the left outline of the nodes

Default valuenullDetails
Type
\ReingoldTilford\Algorithms\SplObjectStorage
Propertyprivate\ReingoldTilford\Algorithms\SplObjectStorage  $leftThread= 'null'

the left threads

Default valuenullDetails
Type
\ReingoldTilford\Algorithms\SplObjectStorage
Propertyprivateint  $minDistance= '1'

the minimal horizontal distance of two nodes

Default value1Details
Type
int
Propertyprivate\ReingoldTilford\Models\ITreeModel  $model= 'null'

the tree model the algorithm uses

Default valuenullDetails
Type
\ReingoldTilford\Models\ITreeModel
Propertyprivateint  $nodeDegree= 'null'

the number of children of the currently visited node (cached for performance reasons)

Default valuenullDetails
Type
int
Propertyprivate\ReingoldTilford\Algorithms\SplObjectStorage  $offsets= 'null'

the x-offsets of the nodes

Default valuenullDetails
Type
\ReingoldTilford\Algorithms\SplObjectStorage
Propertyprivatestring  $orientation= 'TreeStyle::CENTERED'

the orientation variant of the tree

Default valueTreeStyle::CENTEREDDetails
Type
string
Propertyprivate\ReingoldTilford\Algorithms\SplObjectStorage  $parents= 'null'

hash table that maps a node to its parent

Default valuenullDetails
Type
\ReingoldTilford\Algorithms\SplObjectStorage
Propertyprivate\ReingoldTilford\Algorithms\SplObjectStorage  $rightOutline= 'null'

the right outline of the nodes

Default valuenullDetails
Type
\ReingoldTilford\Algorithms\SplObjectStorage
Propertyprivate\ReingoldTilford\Algorithms\SplObjectStorage  $rightThread= 'null'

the right threads

Default valuenullDetails
Type
\ReingoldTilford\Algorithms\SplObjectStorage
Propertyprivate\ReingoldTilford\Algorithms\TreeNode  $root= 'null'

the root of the (sub)tree to be printed

Default valuenullDetails
Type
\ReingoldTilford\Algorithms\TreeNode

Methods

methodpublic__construct( ) : void

This method acts as the constructor of the class.

methodprivatecalculateSubTreeShifts( object $node, \ReingoldTilford\Algorithms\array[int][int]TreeNode $leftOutlines, \ReingoldTilford\Algorithms\array[int][int]TreeNode $rightOutlines ) : \ReingoldTilford\Algorithms\array[int]int

This method returns the subtree shifts of the children of the current node.

Parameters
Name Type Description
$node object

the current node that is traversed

$leftOutlines \ReingoldTilford\Algorithms\array[int][int]TreeNode

the left outlines of the node

$rightOutlines \ReingoldTilford\Algorithms\array[int][int]TreeNode

the right outlines of the node

Returns
Type Description
\ReingoldTilford\Algorithms\array[int]int
methodprivatecalculatesOffsets( object $node ) : void

This method calculates the offsets of a node.

This is the main method of the algorithm.

Parameters
Name Type Description
$node object
methodprivategetChildren( object $node ) : \ArrayObject

This helper method returns the child nodes of a given node.

Parameters
Name Type Description
$node object

the node for which to get its child nodes

Returns
Type Description
\ArrayObject of child nodes
methodprivategetDegree( object $node ) : int

This helper method gets the degree of a given node.

Parameters
Name Type Description
$node object

the node of which the degree has to be calculated

Returns
Type Description
int the degree of the node
methodpublicgetLayout( \ReingoldTilford\Models\ITreeModel $model, \ReingoldTilford\Algorithms\type $orientation = TreeStyle::CENTERED ) : \ReingoldTilford\Algorithms\Layout

This method returns a Layout for a given ITreeModel.

Parameters
Name Type Description
$model \ReingoldTilford\Models\ITreeModel

the tree model to get a layout for

$orientation \ReingoldTilford\Algorithms\type

the orientation of the children of a node, either one of TreeStyle::CENTERED, TreeStyle::LEFT, TreeStyle::RIGHT

Returns
Type Description
\ReingoldTilford\Algorithms\Layout the layout of the given tree model
methodprivategetPostOrderEnumeration( ) : \SplDoublyLinkedList

This helper method returns the post-order enumaration of the tree model.

Returns
Type Description
\SplDoublyLinkedList the post-order enumaration of the tree model
methodprivategetPreOrderEnumeration( ) : \SplDoublyLinkedList

This helper method returns the pre-order enumaration of the tree model.

Returns
Type Description
\SplDoublyLinkedList the pre-order enumaration of the tree model
methodprivateinitialize( ) : void

This method (re)initializes the internal data structures, so an object of this class can be used for several trees to be drawn.

methodprivateinitializeMetaData( ) : void

This helper method initializes the meta data for use in the algorithm

methodprivatesetNodeOffsets( object $node, \ReingoldTilford\Algorithms\array[int]double $subTreeShifts ) : void

This method sets the offsets of the children of the current node.

Parameters
Name Type Description
$node object

the current node that is traversed

$subTreeShifts \ReingoldTilford\Algorithms\array[int]double

the shifts of the subtrees

methodprivateupdateOutlines( object $node, \ReingoldTilford\Algorithms\array[int][int]TreeNode $leftOutlines ) : void

This method updates the left and the right outline of the current node.

Parameters
Name Type Description
$node object

the current node that is traversed

$leftOutlines \ReingoldTilford\Algorithms\array[int][int]TreeNode

the left outlines of the node

Documentation was generated by DocBlox 0.15.1.