1: <?php
2:
3: namespace Alpha\Util\Graph;
4:
5: use Alpha\Util\Logging\Logger;
6:
7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48:
49: class TreeGraph
50: {
51: 52: 53: 54: 55: 56: 57:
58: private $previousLevelNodes = array();
59:
60: 61: 62: 63: 64: 65: 66:
67: private $nodes = array();
68:
69: 70: 71: 72: 73: 74: 75:
76: private $root;
77:
78: 79: 80: 81: 82: 83: 84:
85: private $rowSpace;
86:
87: 88: 89: 90: 91: 92: 93:
94: private $colSpace;
95:
96: 97: 98: 99: 100: 101: 102:
103: private $branchSpace;
104:
105: 106: 107: 108: 109: 110: 111:
112: private $isRendered = false;
113:
114: 115: 116: 117: 118: 119: 120:
121: private $position = 0;
122:
123: 124: 125: 126: 127: 128: 129:
130: private $height = 0;
131:
132: 133: 134: 135: 136: 137: 138:
139: private $width = 0;
140:
141: 142: 143: 144: 145: 146: 147:
148: private static $logger = null;
149:
150: 151: 152: 153: 154: 155: 156: 157: 158:
159: public function __construct($rowSpace = 40, $colSpace = 40, $branchSpace = 80)
160: {
161: self::$logger = new Logger('TreeGraph');
162:
163: $this->root = new GraphNode(0, 0, 0);
164: $this->rowSpace = $rowSpace;
165: $this->colSpace = $colSpace;
166: $this->branchSpace = $branchSpace;
167: }
168:
169: 170: 171: 172: 173: 174: 175: 176: 177: 178: 179: 180: 181:
182: public function add($id, $pid, $message = '', $w = 0, $h = 0, $nodeColour, $URL)
183: {
184: $node = new GraphNode($id, $w, $h, $message, $nodeColour, $URL);
185:
186: if (isset($this->nodes[$pid])) {
187: $pnode = $this->nodes[$pid];
188: $node->setParentNode($pnode);
189: $pnode->addChild($node);
190: } else {
191: $pnode = $this->root;
192: $node->setParentNode($pnode);
193: $this->root->addChild($node);
194: }
195:
196: $this->nodes[$id] = $node;
197: }
198:
199: 200: 201: 202: 203: 204: 205: 206: 207:
208: public function get($id)
209: {
210: if (isset($this->nodes[$id])) {
211: return $this->nodes[$id];
212: } else {
213: return null;
214: }
215: }
216:
217: 218: 219: 220: 221: 222: 223: 224:
225: private function firstPass($node, $level)
226: {
227: $this->setNeighbours($node, $level);
228:
229: if ($node->childCount() == 0) {
230: $leftSibling = $node->getLeftSibling();
231:
232: if (isset($leftSibling)) {
233: $node->setOffset($leftSibling->getOffset() + $leftSibling->getWidth() + $this->colSpace);
234: } else {
235: $node->setOffset(0);
236: }
237: } else {
238: $childCount = $node->childCount();
239:
240: for ($i = 0; $i < $childCount; ++$i) {
241: $this->firstPass($node->getChildAt($i), $level + 1);
242: }
243:
244: $midPoint = $node->getChildrenCenter();
245: $midPoint -= $node->getWidth() / 2;
246: $leftSibling = $node->getLeftSibling();
247:
248: if (isset($leftSibling)) {
249: $node->setOffset($leftSibling->getOffset() + $leftSibling->getWidth() + $this->colSpace);
250: $node->setModifier($node->getOffset() - $midPoint);
251:
252: $this->layout($node, $level);
253: } else {
254: $node->setOffset($midPoint);
255: }
256: }
257:
258: self::$logger->debug('Memory usage at first scan ['.((memory_get_usage(true) / 1024) / 1024).' MB]');
259: }
260:
261: 262: 263: 264: 265: 266: 267: 268: 269: 270:
271: private function secondPass($node, $level, $x = 0, $y = 0)
272: {
273: $nodeX = $node->getOffset() + $x;
274: $nodeY = $y;
275:
276: $node->setX($nodeX);
277: $node->setY($nodeY);
278:
279: $this->height = ($this->height > $node->getY() + $node->getWidth()) ? $this->height : $node->getY() + $node->getWidth();
280: $this->width = ($this->width > $nodeX + $node->getWidth()) ? $this->width : $nodeX + $node->getWidth() + 10;
281:
282: if ($node->childCount() > 0) {
283: $this->secondPass($node->getChildAt(0), $level + 1, $x + $node->getModifier(), $y + $node->getHeight() + $this->rowSpace);
284: }
285:
286: $rightSibling = $node->getRightSibling();
287:
288: if (isset($rightSibling)) {
289: $this->secondPass($rightSibling, $level, $x, $y);
290: }
291:
292: self::$logger->debug('Memory usage at second scan ['.((memory_get_usage(true) / 1024) / 1024).' MB]');
293: }
294:
295: 296: 297: 298: 299: 300: 301: 302:
303: private function layout($node, $level)
304: {
305: $firstChild = $node->getChildAt(0);
306: $firstChildLeftNeighbour = $firstChild->getLeftSibling();
307:
308: for ($j = 1; $j <= $level; ++$j) {
309: $modifierSumRight = 0;
310: $modifierSumLeft = 0;
311: $rightAncestor = $firstChild;
312: $leftAncestor = $firstChildLeftNeighbour;
313:
314: for ($l = 0; $l < $j; ++$l) {
315: $rightAncestor = $rightAncestor->getParentNode();
316: $leftAncestor = $leftAncestor->getParentNode();
317: $modifierSumRight += $rightAncestor->getModifier();
318: $modifierSumLeft += $leftAncestor->getModifier();
319: }
320:
321: $totalGap = ($firstChildLeftNeighbour->getOffset() + $modifierSumLeft + $firstChildLeftNeighbour->getWidth() + $this->branchSpace) - ($firstChild->getOffset() + $modifierSumRight);
322:
323: if ($totalGap > 0) {
324: $subTree = $node;
325: $subTreesCount = 0;
326:
327: while (isset($subTree) && $subTree !== $leftAncestor) {
328: $subTree = $subTree->getLeftSibling();
329: ++$subTreesCount;
330: }
331:
332: $subTreeMove = $node;
333: $singleGap = $totalGap / $subTreesCount;
334:
335: while (isset($subTreeMove) && $subTreeMove !== $leftAncestor) {
336: $subTreeMove = $subTreeMove->getLeftSibling();
337:
338: if (isset($subTreeMove)) {
339: $subTreeMove->setOffset($subTreeMove->getOffset() + $totalGap);
340: $subTreeMove->setModifier($subTreeMove->getModifier() + $totalGap);
341: $totalGap -= $singleGap;
342: }
343: }
344: }
345:
346: if ($firstChild->childCount() == 0) {
347: $firstChild = $this->getLeftmost($node, 0, $j);
348: } else {
349: $firstChild = $firstChild->getChildAt(0);
350: }
351:
352: if (isset($firstChild)) {
353: $firstChildLeftNeighbour = $firstChild->getLeftSibling();
354: }
355: }
356: }
357:
358: 359: 360: 361: 362: 363: 364: 365:
366: private function setNeighbours($node, $level)
367: {
368: if (isset($this->previousLevelNodes[$level])) {
369: $node->setLeftSibling($this->previousLevelNodes[$level]);
370: }
371:
372: if ($node->getLeftSibling()) {
373: $node->getLeftSibling()->setRightSibling($node);
374: }
375: $this->previousLevelNodes[$level] = $node;
376: }
377:
378: 379: 380: 381: 382: 383: 384: 385: 386: 387: 388:
389: private function getLeftmost($node, $level, $maxlevel)
390: {
391: if ($level >= $maxlevel) {
392: return $node;
393: }
394:
395: $childCount = $node->childCount();
396:
397: if ($childCount == 0) {
398: return;
399: }
400:
401: for ($i = 0; $i < $childCount; ++$i) {
402: $child = $node->getChildAt($i);
403:
404: $leftmostDescendant = $this->getLeftmost($child, $level + 1, $maxlevel);
405:
406: if (isset($leftmostDescendant)) {
407: return $leftmostDescendant;
408: }
409: }
410:
411: return;
412: }
413:
414: 415: 416: 417: 418:
419: protected function render()
420: {
421: $this->firstPass($this->root, 0);
422: $this->secondPass($this->root, 0);
423:
424: foreach ($this->nodes as $node) {
425: $node->setUpLinks();
426: }
427:
428: $this->isRendered = true;
429: }
430:
431: 432: 433: 434: 435:
436: public function getWidth()
437: {
438: if (!$this->isRendered) {
439: $this->render();
440: }
441:
442: return $this->width;
443: }
444:
445: 446: 447: 448: 449:
450: public function getHeight()
451: {
452: if (!$this->isRendered) {
453: $this->render();
454: }
455:
456: return $this->height;
457: }
458:
459: 460: 461: 462: 463: 464: 465:
466: public function next()
467: {
468: if (!$this->isRendered) {
469: $this->render();
470: }
471:
472: if (isset($this->nodes[$this->position + 1])) {
473: ++$this->position;
474:
475: return $this->nodes[$this->position];
476: } else {
477: return;
478: }
479: }
480:
481: 482: 483: 484: 485: 486: 487:
488: public function hasNext()
489: {
490: if (isset($this->nodes[$this->position + 1])) {
491: return true;
492: } else {
493: return false;
494: }
495: }
496: }
497: