| alpha--util--graphs

# Source for file AlphaTreeGraph.inc Documentation is available at AlphaTreeGraph.inc <?php require_once $config->get('sysRoot').'alpha/util/graphs/AlphaGraphNode.inc'; /** * * Maintains the geometry for a tree graph * * @package alpha::util::graphs * @since 1.0 * @author John Collins <dev@alphaframework.org> * @version $Id: AlphaTreeGraph.inc 1341 2011-03-17 15:02:02Z johnc $ * @license http://www.opensource.org/licenses/bsd-license.php The BSD License * @copyright Copyright (c) 2011, John Collins (founder of Alpha Framework). * All rights reserved. * * <pre> * 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 * following disclaimer. * * 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. * </pre> * */ class AlphaTreeGraph { /** * An array of nodes on the previous level * * @var array * @since 1.0 */ private $previousLevelNodes = array(); /** * An array of nodes in this graph * * @var array * @since 1.0 */ private $nodes = array(); /** * The root node of the graph * * @var AlphaGraphNode * @since 1.0 */ private $root; /** * The amount of space between graph rows * * @var integer * @since 1.0 */ private $rowSpace; /** * The amount of space between graph columns * * @var integer * @since 1.0 */ private $colSpace; /** * The amount of space between graph branches * * @var integer * @since 1.0 */ private $branchSpace; /** * Flag to track whether the chart is rendered or not * * @var boolean * @since 1.0 */ private $isRendered = false; /** * The index of the current node in the graph we are inspecting * * @var integer * @since 1.0 */ private $position = 0; /** * The height of the graph * * @var integer * @since 1.0 */ private $height = 0; /** * The width of the graph * * @var integer * @since 1.0 */ private $width = 0; /** * Trace logger * * @var Logger * @since 1.0 */ private static $logger = null; /** * Constructor * * @param integer $rowSpace * @param integer $colSpace * @param integer $branchSpace * @since 1.0 */ public function __construct($rowSpace = 40 , $colSpace = 40, $branchSpace = 80) { self::$logger = new Logger('AlphaTreeGraph'); $this->root = new AlphaGraphNode(0, 0, 0); $this->rowSpace = $rowSpace; $this->colSpace = $colSpace; $this->branchSpace = $branchSpace; } /** * Add a new node to the graph * * @param integer $id * @param integer $pid * @param string $message * @param integer $w * @param integer $h * @param string $nodeColour * @param string $URL * @since 1.0 */ public function add($id, $pid, $message = '', $w = 0, $h = 0, $nodeColour, $URL) { $node = new AlphaGraphNode($id, $w, $h, $message, $nodeColour, $URL); if(isset($this->nodes[$pid])) { $pnode = $this->nodes[$pid]; $node->setParentNode($pnode); $pnode->addChild($node); }else{ $pnode = $this->root; $node->setParentNode($pnode); $this->root->addChild($node); } $this->nodes[$id] = $node; } /** * The first pass of the graph * * @param AlphaGraphNode $node * @param integer $level * @since 1.0 */ 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); }else{ $node->setOffset(0); } }else{ $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); }else{ $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 * @param integer $level * @param integer $x * @param integer $y * @since 1.0 */ private function secondPass($node, $level, $x = 0, $y = 0) { $nodeX = $node->getOffset()+$x; $nodeY = $y; $node->setX($nodeX); $node->setY($nodeY); $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 * @param integer $level * @since 1.0 */ private function layout($node, $level) { $firstChild = $node->getChildAt(0); $firstChildLeftNeighbour = $firstChild->getLeftSibling(); for($j = 1; $j <= $level; $j++) { $modifierSumRight = 0; $modifierSumLeft = 0; $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); if($totalGap > 0) { $subTree = $node; $subTreesCount = 0; while(isset($subTree) && $subTree !== $leftAncestor) { $subTree = $subTree->getLeftSibling(); $subTreesCount++; } $subTreeMove = $node; $singleGap = $totalGap / $subTreesCount; while(isset($subTreeMove) && $subTreeMove !== $leftAncestor){ $subTreeMove = $subTreeMove->getLeftSibling(); if(isset($subTreeMove)) { $subTreeMove->setOffset($subTreeMove->getOffset() + $totalGap); $subTreeMove->setModifier($subTreeMove->getModifier() + $totalGap); $totalGap -= $singleGap; } } } if($firstChild->childCount() == 0) { $firstChild = $this->getLeftmost($node, 0, $j); }else{ $firstChild = $firstChild->getChildAt(0); } if(isset($firstChild)) { $firstChildLeftNeighbour = $firstChild->getLeftSibling(); } } } /** * Setup neighbour nodes * * @param AlphaGraphNode $node * @param integer $level * @since 1.0 */ 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 $level * @param integer $maxlevel * @return AlphaGraphNode * @since 1.0 */ private function getLeftmost($node, $level, $maxlevel) { if($level >= $maxlevel) { return $node; } $childCount = $node->childCount(); if($childCount == 0) { return null; } for($i = 0; $i < $childCount; $i++) { $child = $node->getChildAt($i); $leftmostDescendant = $this->getLeftmost($child, $level + 1, $maxlevel); if(isset($leftmostDescendant)) { return $leftmostDescendant; } } return null; } /** * Render the chart in memory * * @since 1.0 */ protected function render() { $this->firstPass($this->root, 0); $this->secondPass($this->root, 0); foreach($this->nodes as $node) { $node->setUpLinks(); } $this->isRendered = true; } /** * Get the width of the graph, will invoke render() if not already rendered * * @since 1.0 */ public function getWidth() { if(!$this->isRendered) { $this->render(); } return $this->width; } /** * Get the heith of the graph, will invoke render() if not already rendered * * @since 1.0 */ public function getHeight() { if(!$this->isRendered) $this->render(); return $this->height; } /** * Get the next AlphaGraphNode instance in the graph, will invoke render() if not already rendered * * @return AlphaGraphNode * @since 1.0 */ public function next() { if(!$this->isRendered) { $this->render(); } if(isset($this->nodes[$this->position+1])) { $this->position++; return $this->nodes[$this->position]; }else{ return null; } } /** * Check to see if another AlphaGraphNode instance in the graph is available * * @return boolean * @since 1.0 */ public function hasNext() { if(isset($this->nodes[$this->position+1])) return true; else return false; } } ?> Documentation generated on Thu, 17 Mar 2011 16:43:40 +0000 by phpDocumentor 1.4.3