1: <?php
2:
3: 4: 5: 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: class AlphaTreeGraph {
49: 50: 51: 52: 53: 54:
55: private $previousLevelNodes = array();
56:
57: 58: 59: 60: 61: 62:
63: private $nodes = array();
64:
65: 66: 67: 68: 69: 70:
71: private $root;
72:
73: 74: 75: 76: 77: 78:
79: private $rowSpace;
80:
81: 82: 83: 84: 85: 86:
87: private $colSpace;
88:
89: 90: 91: 92: 93: 94:
95: private $branchSpace;
96:
97: 98: 99: 100: 101: 102:
103: private $isRendered = false;
104:
105: 106: 107: 108: 109: 110:
111: private $position = 0;
112:
113: 114: 115: 116: 117: 118:
119: private $height = 0;
120:
121: 122: 123: 124: 125: 126:
127: private $width = 0;
128:
129: 130: 131: 132: 133: 134:
135: private static $logger = null;
136:
137: 138: 139: 140: 141: 142: 143: 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: 157: 158: 159: 160: 161: 162: 163: 164: 165: 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: 185: 186: 187: 188: 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: 227: 228: 229: 230: 231: 232: 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: 259: 260: 261: 262: 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: 321: 322: 323: 324: 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: 338: 339: 340: 341: 342: 343: 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: 371: 372: 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: 387: 388: 389:
390: public function getWidth() {
391: if(!$this->isRendered) {
392: $this->render();
393: }
394: return $this->width;
395: }
396:
397: 398: 399: 400: 401:
402: public function getHeight() {
403: if(!$this->isRendered)
404: $this->render();
405:
406: return $this->height;
407: }
408:
409: 410: 411: 412: 413: 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: 430: 431: 432: 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: ?>