      1: <?php
      2:
      3: /**
      4:  *
      5:  * Maintains the geometry for a tree graph
      6:  *
      7:  * @package alpha::util::graphs
      8:  * @since 1.0
      9:  * @author John Collins <dev@alphaframework.org>
     10:  * @version $Id: AlphaTreeGraph.inc 1496 2012-02-12 20:32:21Z alphadev $
     11:  * @license http://www.opensource.org/licenses/bsd-license.php The BSD License
     12:  * @copyright Copyright (c) 2012, John Collins (founder of Alpha Framework).
     13:  * All rights reserved.
     14:  *
     15:  * <pre>
     16:  * Redistribution and use in source and binary forms, with or
     17:  * without modification, are permitted provided that the
     18:  * following conditions are met:
     19:  *
     20:  * * Redistributions of source code must retain the above
     21:  *   copyright notice, this list of conditions and the
     22:  *   following disclaimer.
     23:  * * Redistributions in binary form must reproduce the above
     24:  *   copyright notice, this list of conditions and the
     25:  *   following disclaimer in the documentation and/or other
     26:  *   materials provided with the distribution.
     27:  * * Neither the name of the Alpha Framework nor the names
     28:  *   of its contributors may be used to endorse or promote
     29:  *   products derived from this software without specific
     30:  *   prior written permission.
     31:  *
     32:  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
     33:  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
     34:  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
     35:  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
     36:  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
     37:  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     38:  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     39:  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
     40:  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     41:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
     42:  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE
     43:  * OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
     44:  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     45:  * </pre>
     46:  *
     47:  */
     48: class AlphaTreeGraph {
     49:     /**
     50:      * An array of nodes on the previous level
     51:      *
     52:      * @var array
     53:      * @since 1.0
     54:      */
     55:     private $previousLevelNodes = array();
     56:
     57:     /**
     58:      * An array of nodes in this graph
     59:      *
     60:      * @var array
     61:      * @since 1.0
     62:      */
     63:     private $nodes = array();
     64:
     65:     /**
     66:      * The root node of the graph
     67:      *
     68:      * @var AlphaGraphNode
     69:      * @since 1.0
     70:      */
     71:     private $root;
     72:
     73:     /**
     74:      * The amount of space between graph rows
     75:      *
     76:      * @var integer
     77:      * @since 1.0
     78:      */
     79:     private $rowSpace;
     80:
     81:     /**
     82:      * The amount of space between graph columns
     83:      *
     84:      * @var integer
     85:      * @since 1.0
     86:      */
     87:     private $colSpace;
     88:
     89:     /**
     90:      * The amount of space between graph branches
     91:      *
     92:      * @var integer
     93:      * @since 1.0
     94:      */
     95:     private $branchSpace;
     96:
     97:     /**
     98:      * Flag to track whether the chart is rendered or not
     99:      *
    100:      * @var boolean
    101:      * @since 1.0
    102:      */
    103:     private $isRendered = false;
    104:
    105:     /**
    106:      * The index of the current node in the graph we are inspecting
    107:      *
    108:      * @var integer
    109:      * @since 1.0
    110:      */
    111:     private $position = 0;
    112:
    113:     /**
    114:      * The height of the graph
    115:      *
    116:      * @var integer
    117:      * @since 1.0
    118:      */
    119:     private $height = 0;
    120:
    121:     /**
    122:      * The width of the graph
    123:      *
    124:      * @var integer
    125:      * @since 1.0
    126:      */
    127:     private $width = 0;
    128:
    129:     /**
    130:      * Trace logger
    131:      *
    132:      * @var Logger
    133:      * @since 1.0
    134:      */
    135:     private static $logger = null;
    136:
    137:     /**
    138:      * Constructor
    139:      *
    140:      * @param integer $rowSpace
    141:      * @param integer $colSpace
    142:      * @param integer $branchSpace
    143:      * @since 1.0
    144:      */
    145:     public function __construct($rowSpace = 40 , $colSpace = 40, $branchSpace = 80) {
    146:         self::$logger = new Logger('AlphaTreeGraph');
    147:
    148:         $this->root = new AlphaGraphNode(0, 0, 0);
    149:         $this->rowSpace = $rowSpace;
    150:         $this->colSpace = $colSpace;
    151:         $this->branchSpace = $branchSpace;
    152:     }
    153:
    154:
    155:     /**
    156:      * Add a new node to the graph
    157:      *
    158:      * @param integer $id
    159:      * @param integer $pid
    160:      * @param string $message
    161:      * @param integer $w
    162:      * @param integer $h
    163:      * @param string $nodeColour
    164:      * @param string $URL
    165:      * @since 1.0
    166:      */
    167:     public function add($id, $pid, $message = '', $w = 0, $h = 0, $nodeColour, $URL) {
    168:         $node = new AlphaGraphNode($id, $w, $h, $message, $nodeColour, $URL);
    169:
    170:         if(isset($this->nodes[$pid])) {
    171:             $pnode = $this->nodes[$pid];
    172:             $node->setParentNode($pnode);
    173:             $pnode->addChild($node);
    174:         }else{
    175:             $pnode = $this->root;
    176:             $node->setParentNode($pnode);
    177:             $this->root->addChild($node);
    178:         }
    179:
    180:         $this->nodes[$id] = $node;
    181:     }
    182:
    183:     /**
    184:      * The first pass of the graph
    185:      *
    186:      * @param AlphaGraphNode $node
    187:      * @param integer $level
    188:      * @since 1.0
    189:      */
    190:     private function firstPass($node, $level) {
    191:         $this->setNeighbours($node, $level);
    192:
    193:         if($node->childCount() == 0) {
    194:             $leftSibling = $node->getLeftSibling();
    195:
    196:             if(isset($leftSibling)) {
    197:                 $node->setOffset($leftSibling->getOffset() + $leftSibling->getWidth() + $this->colSpace);
    198:             }else{
    199:                 $node->setOffset(0);
    200:             }
    201:         }else{
    202:             $childCount = $node->childCount();
    203:
    204:             for($i = 0; $i < $childCount; $i++) {
    205:                 $this->firstPass($node->getChildAt($i), $level + 1);
    206:             }
    207:
    208:             $midPoint = $node->getChildrenCenter();
    209:             $midPoint -= $node->getWidth()/2;
    210:             $leftSibling = $node->getLeftSibling();
    211:
    212:             if(isset($leftSibling)) {
    213:                 $node->setOffset($leftSibling->getOffset() + $leftSibling->getWidth() + $this->colSpace);
    214:                 $node->setModifier($node->getOffset() - $midPoint);
    215:
    216:                 $this->layout($node, $level);
    217:             }else{
    218:                 $node->setOffset($midPoint);
    219:             }
    220:         }
    221:
    222:         self::$logger->debug('Memory usage at first scan ['.((memory_get_usage(true)/1024)/1024).' MB]');
    223:     }
    224:
    225:     /**
    226:      * The second pass of the graph
    227:      *
    228:      * @param AlphaGraphNode $node
    229:      * @param integer $level
    230:      * @param integer $x
    231:      * @param integer $y
    232:      * @since 1.0
    233:      */
    234:     private function secondPass($node, $level, $x = 0, $y = 0) {
    235:         $nodeX = $node->getOffset()+$x;
    236:         $nodeY = $y;
    237:
    238:         $node->setX($nodeX);
    239:         $node->setY($nodeY);
    240:
    241:         $this->height = ($this->height > $node->getY() + $node->getWidth()) ? $this->height : $node->getY() + $node->getWidth();
    242:         $this->width = ($this->width > $nodeX + $node->getWidth()) ? $this->width : $nodeX + $node->getWidth()+10;
    243:
    244:         if($node->childCount() > 0) {
    245:             $this->secondPass($node->getChildAt(0), $level + 1, $x + $node->getModifier(), $y + $node->getHeight() + $this->rowSpace);
    246:         }
    247:
    248:         $rightSibling = $node->getRightSibling();
    249:
    250:         if(isset($rightSibling)) {
    251:             $this->secondPass($rightSibling, $level, $x, $y);
    252:         }
    253:
    254:         self::$logger->debug('Memory usage at second scan ['.((memory_get_usage(true)/1024)/1024).' MB]');
    255:     }
    256:
    257:     /**
    258:      * Handles the laying out of multi-branch trees
    259:      *
    260:      * @param AlphaGraphNode $node
    261:      * @param integer $level
    262:      * @since 1.0
    263:      */
    264:     private function layout($node, $level) {
    265:
    266:         $firstChild = $node->getChildAt(0);
    267:         $firstChildLeftNeighbour = $firstChild->getLeftSibling();
    268:
    269:         for($j = 1; $j <= $level; $j++) {
    270:             $modifierSumRight = 0;
    271:             $modifierSumLeft = 0;
    272:             $rightAncestor = $firstChild;
    273:             $leftAncestor = $firstChildLeftNeighbour;
    274:
    275:             for($l = 0; $l < $j; $l++) {
    276:                 $rightAncestor = $rightAncestor->getParentNode();
    277:                 $leftAncestor = $leftAncestor->getParentNode();
    278:                 $modifierSumRight += $rightAncestor->getModifier();
    279:                 $modifierSumLeft += $leftAncestor->getModifier();
    280:             }
    281:
    282:             $totalGap = ($firstChildLeftNeighbour->getOffset() + $modifierSumLeft + $firstChildLeftNeighbour->getWidth() + $this->branchSpace) - ($firstChild->getOffset() + $modifierSumRight);
    283:
    284:             if($totalGap > 0) {
    285:                 $subTree = $node;
    286:                 $subTreesCount = 0;
    287:
    288:                 while(isset($subTree) && $subTree !== $leftAncestor) {
    289:                     $subTree = $subTree->getLeftSibling();
    290:                     $subTreesCount++;
    291:                 }
    292:
    293:                 $subTreeMove = $node;
    294:                 $singleGap = $totalGap / $subTreesCount;
    295:
    296:                 while(isset($subTreeMove) && $subTreeMove !== $leftAncestor){
    297:                     $subTreeMove = $subTreeMove->getLeftSibling();
    298:
    299:                     if(isset($subTreeMove)) {
    300:                         $subTreeMove->setOffset($subTreeMove->getOffset() + $totalGap);
    301:                         $subTreeMove->setModifier($subTreeMove->getModifier() + $totalGap);
    302:                         $totalGap -= $singleGap;
    303:                     }
    304:                 }
    305:             }
    306:
    307:             if($firstChild->childCount() == 0) {
    308:                 $firstChild = $this->getLeftmost($node, 0, $j);
    309:             }else{
    310:                 $firstChild = $firstChild->getChildAt(0);
    311:             }
    312:
    313:             if(isset($firstChild))  {
    314:                 $firstChildLeftNeighbour = $firstChild->getLeftSibling();
    315:             }
    316:         }
    317:     }
    318:
    319:     /**
    320:      * Setup neighbour nodes
    321:      *
    322:      * @param AlphaGraphNode $node
    323:      * @param integer $level
    324:      * @since 1.0
    325:      */
    326:     private function setNeighbours($node, $level) {
    327:         if(isset($this->previousLevelNodes[$level]))
    328:             $node->setLeftSibling($this->previousLevelNodes[$level]);
    329:
    330:         if($node->getLeftSibling()) {
    331:             $node->getLeftSibling()->setRightSibling($node);
    332:         }
    333:         $this->previousLevelNodes[$level] = $node;
    334:     }
    335:
    336:     /**
    337:      * Get left most node in the branch
    338:      *
    339:      * @param AlphaGraphNode $node
    340:      * @param integer $level
    341:      * @param integer $maxlevel
    342:      * @return AlphaGraphNode
    343:      * @since 1.0
    344:      */
    345:     private function getLeftmost($node, $level, $maxlevel) {
    346:         if($level >= $maxlevel) {
    347:             return $node;
    348:         }
    349:
    350:         $childCount = $node->childCount();
    351:
    352:         if($childCount == 0) {
    353:             return null;
    354:         }
    355:
    356:         for($i = 0; $i < $childCount; $i++) {
    357:             $child = $node->getChildAt($i);
    358:
    359:             $leftmostDescendant = $this->getLeftmost($child, $level + 1, $maxlevel);
    360:
    361:             if(isset($leftmostDescendant)) {
    362:                 return $leftmostDescendant;
    363:             }
    364:         }
    365:
    366:         return null;
    367:     }
    368:
    369:     /**
    370:      * Render the chart in memory
    371:      *
    372:      * @since 1.0
    373:      */
    374:     protected function render() {
    375:         $this->firstPass($this->root, 0);
    376:         $this->secondPass($this->root, 0);
    377:
    378:         foreach($this->nodes as $node) {
    379:             $node->setUpLinks();
    380:         }
    381:
    382:         $this->isRendered = true;
    383:     }
    384:
    385:     /**
    386:      * Get the width of the graph, will invoke render() if not already rendered
    387:      *
    388:      * @since 1.0
    389:      */
    390:     public function getWidth() {
    391:         if(!$this->isRendered) {
    392:             $this->render();
    393:         }
    394:         return $this->width;
    395:     }
    396:
    397:     /**
    398:      * Get the heith of the graph, will invoke render() if not already rendered
    399:      *
    400:      * @since 1.0
    401:      */
    402:     public function getHeight() {
    403:         if(!$this->isRendered)
    404:             $this->render();
    405:
    406:         return $this->height;
    407:     }
    408:
    409:     /**
    410:      * Get the next AlphaGraphNode instance in the graph, will invoke render() if not already rendered
    411:      *
    412:      * @return AlphaGraphNode
    413:      * @since 1.0
    414:      */
    415:     public function next() {
    416:         if(!$this->isRendered) {
    417:             $this->render();
    418:         }
    419:
    420:         if(isset($this->nodes[$this->position+1])) {
    421:             $this->position++;
    422:             return $this->nodes[$this->position];
    423:         }else{
    424:             return null;
    425:         }
    426:     }
    427:
    428:     /**
    429:      * Check to see if another AlphaGraphNode instance in the graph is available
    430:      *
    431:      * @return boolean
    432:      * @since 1.0
    433:      */
    434:     public function hasNext() {
    435:         if(isset($this->nodes[$this->position+1]))
    436:             return true;
    437:         else
    438:             return false;
    439:     }
    440: }
    441:
    442: ?>