Source for file AlphaTreeGraph.inc
Documentation is available at AlphaTreeGraph.inc
require_once $config->get('sysRoot'). 'alpha/util/graphs/AlphaGraphNode.inc';
* Maintains the geometry for a tree graph
* @package alpha::util::graphs
* @author John Collins <dev@alphaframework.org>
* @version $Id: AlphaTreeGraph.inc 1454 2011-12-04 15:14:05Z johnc $
* @license http://www.opensource.org/licenses/bsd-license.php The BSD License
* @copyright Copyright (c) 2011, John Collins (founder of Alpha Framework).
* Redistribution and use in source and binary forms, with or
* without modification, are permitted provided that the
* following conditions are met:
* * Redistributions of source code must retain the above
* copyright notice, this list of conditions and the
* * Redistributions in binary form must reproduce the above
* copyright notice, this list of conditions and the
* following disclaimer in the documentation and/or other
* materials provided with the distribution.
* * Neither the name of the Alpha Framework nor the names
* of its contributors may be used to endorse or promote
* products derived from this software without specific
* prior written permission.
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
* CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
* OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
* SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
* An array of nodes on the previous level
private $previousLevelNodes = array();
* An array of nodes in this graph
private $nodes = array();
* The root node of the graph
* The amount of space between graph rows
* The amount of space between graph columns
* The amount of space between graph branches
* Flag to track whether the chart is rendered or not
private $isRendered = false;
* The index of the current node in the graph we are inspecting
* The height of the graph
private static $logger = null;
* @param integer $rowSpace
* @param integer $colSpace
* @param integer $branchSpace
public function __construct($rowSpace = 40 , $colSpace = 40, $branchSpace = 80) {
self::$logger = new Logger('AlphaTreeGraph');
$this->rowSpace = $rowSpace;
$this->colSpace = $colSpace;
$this->branchSpace = $branchSpace;
* Add a new node to the graph
* @param string $nodeColour
public function add($id, $pid, $message = '', $w = 0, $h = 0, $nodeColour, $URL) {
if(isset ($this->nodes[$pid])) {
$pnode = $this->nodes[$pid];
$node->setParentNode($pnode);
$node->setParentNode($pnode);
$this->nodes[$id] = $node;
* The first pass of the graph
* @param AlphaGraphNode $node
private function firstPass($node, $level) {
$this->setNeighbours($node, $level);
if($node->childCount() == 0) {
$leftSibling = $node->getLeftSibling();
if(isset ($leftSibling)) {
$node->setOffset($leftSibling->getOffset() + $leftSibling->getWidth() + $this->colSpace);
$childCount = $node->childCount();
for($i = 0; $i < $childCount; $i++ ) {
$this->firstPass($node->getChildAt($i), $level + 1);
$midPoint = $node->getChildrenCenter();
$midPoint -= $node->getWidth()/ 2;
$leftSibling = $node->getLeftSibling();
if(isset ($leftSibling)) {
$node->setOffset($leftSibling->getOffset() + $leftSibling->getWidth() + $this->colSpace);
$node->setModifier($node->getOffset() - $midPoint);
$this->layout($node, $level);
$node->setOffset($midPoint);
self::$logger->debug('Memory usage at first scan ['. ((memory_get_usage(true)/ 1024)/ 1024). ' MB]');
* The second pass of the graph
* @param AlphaGraphNode $node
private function secondPass($node, $level, $x = 0, $y = 0) {
$nodeX = $node->getOffset()+ $x;
$this->height = ($this->height > $node->getY() + $node->getWidth()) ? $this->height : $node->getY() + $node->getWidth();
$this->width = ($this->width > $nodeX + $node->getWidth()) ? $this->width : $nodeX + $node->getWidth()+ 10;
if($node->childCount() > 0) {
$this->secondPass($node->getChildAt(0), $level + 1, $x + $node->getModifier(), $y + $node->getHeight() + $this->rowSpace);
$rightSibling = $node->getRightSibling();
if(isset ($rightSibling)) {
$this->secondPass($rightSibling, $level, $x, $y);
self::$logger->debug('Memory usage at second scan ['. ((memory_get_usage(true)/ 1024)/ 1024). ' MB]');
* Handles the laying out of multi-branch trees
* @param AlphaGraphNode $node
private function layout($node, $level) {
$firstChild = $node->getChildAt(0);
$firstChildLeftNeighbour = $firstChild->getLeftSibling();
for($j = 1; $j <= $level; $j++ ) {
$rightAncestor = $firstChild;
$leftAncestor = $firstChildLeftNeighbour;
for($l = 0; $l < $j; $l++ ) {
$rightAncestor = $rightAncestor->getParentNode();
$leftAncestor = $leftAncestor->getParentNode();
$modifierSumRight += $rightAncestor->getModifier();
$modifierSumLeft += $leftAncestor->getModifier();
$totalGap = ($firstChildLeftNeighbour->getOffset() + $modifierSumLeft + $firstChildLeftNeighbour->getWidth() + $this->branchSpace) - ($firstChild->getOffset() + $modifierSumRight);
while(isset ($subTree) && $subTree !== $leftAncestor) {
$subTree = $subTree->getLeftSibling();
$singleGap = $totalGap / $subTreesCount;
while(isset ($subTreeMove) && $subTreeMove !== $leftAncestor){
$subTreeMove = $subTreeMove->getLeftSibling();
if(isset ($subTreeMove)) {
$subTreeMove->setOffset($subTreeMove->getOffset() + $totalGap);
$subTreeMove->setModifier($subTreeMove->getModifier() + $totalGap);
if($firstChild->childCount() == 0) {
$firstChild = $this->getLeftmost($node, 0, $j);
$firstChild = $firstChild->getChildAt(0);
$firstChildLeftNeighbour = $firstChild->getLeftSibling();
* @param AlphaGraphNode $node
private function setNeighbours($node, $level) {
if(isset ($this->previousLevelNodes[$level]))
$node->setLeftSibling($this->previousLevelNodes[$level]);
if($node->getLeftSibling()) {
$node->getLeftSibling()->setRightSibling($node);
$this->previousLevelNodes[$level] = $node;
* Get left most node in the branch
* @param AlphaGraphNode $node
* @param integer $maxlevel
private function getLeftmost($node, $level, $maxlevel) {
if($level >= $maxlevel) {
$childCount = $node->childCount();
for($i = 0; $i < $childCount; $i++ ) {
$child = $node->getChildAt($i);
$leftmostDescendant = $this->getLeftmost($child, $level + 1, $maxlevel);
if(isset ($leftmostDescendant)) {
return $leftmostDescendant;
* Render the chart in memory
$this->firstPass($this->root, 0);
$this->secondPass($this->root, 0);
foreach($this->nodes as $node) {
$this->isRendered = true;
* Get the width of the graph, will invoke render() if not already rendered
* Get the heith of the graph, will invoke render() if not already rendered
* Get the next AlphaGraphNode instance in the graph, will invoke render() if not already rendered
if(isset ($this->nodes[$this->position+ 1])) {
return $this->nodes[$this->position];
* Check to see if another AlphaGraphNode instance in the graph is available
if(isset ($this->nodes[$this->position+ 1]))
|