source: trunk/Modules/NetworkTopology/topologie-gen.php

Last change on this file was 873, checked in by chronos, 5 years ago
  • Modified: Improved code format.
File size: 15.4 KB
Line 
1<?php
2// Vertically-balanced Tree Topology Generator
3// Author: Miroslav Hajda hajdam@users.sf.net
4
5include('../global.php');
6global $Database, $debug;
7
8if (array_key_exists('debug', $_GET)) $debug = $_GET['debug'];
9else $debug = 0;
10//$debug = 0;
11
12class TreeItem {
13 /** Index prvku v databazi */
14 var $index = 0;
15 /** Pozice prvku zleva */
16 var $pos = 0;
17 /** Pozice prvku zprava */
18 var $rpos = 0;
19 /** Pozice prvku shora */
20 var $level = 0;
21 /** Počet potomků s potomky */
22 var $forkcnt = 0;
23 /** Pole potomků */
24 var $children = array();
25 /** Předek */
26 var $parentItem;
27 /** Změna pořadí prvků */
28 var $order = array();
29
30 function getFirst() {
31 if (count($this->children)>0) {
32 if (count($this->order)>0) {
33 if (count($this->children[0]->children)>0) return $this->order[$this->children[0]->index];
34 }
35 return $this->children[0];
36 } else return null;
37 }
38
39 function getLast() {
40 if (count($this->children)>0) {
41 if (count($this->order)>0) {
42 if (count($this->children[count($this->children)-1]->children)>0) return $this->order[$this->children[count($this->children)-1]->index];
43 }
44 return $this->children[count($this->children)-1];
45 } else return null;
46 }
47}
48
49class TreeGen {
50
51 /** Kořenový uzel */
52 var $rootNode;
53 /** Hranice generátorů pozic */
54 var $border = array();
55 /** Maximální šířka hranice */
56 var $maxborder = 0;
57 /** Mód provedených operací */
58 var $mode = 0;
59
60 /** Vytvoří stromovou strukturu načtením záznamů z databáze */
61 function populate() {
62 global $Database;
63 $TopHostName = 'nix-router';
64 // rodičovský uzel
65 $parentNode = null;
66 // Aktuální uzel
67 $currentNode = null;
68 // Aktuální úroveň
69 $level = 0;
70 $this->border[0]=0;
71 $mark = array();
72 $markskip = 0;
73
74 do {
75 if ($level == 0) {
76 $query = 'SELECT dev.id AS id FROM NetworkDevice dev WHERE dev.name = "'.$TopHostName.'" LIMIT 0,1';
77 } else {
78 $query = 'SELECT trg.device AS id FROM NetworkDevice dev, NetworkInterface ifc, NetworkLink lnk, NetworkInterface trg WHERE ifc.device = dev.id AND lnk.interface2 = ifc.id AND lnk.interface1 = trg.id AND dev.used=1 AND ';
79 $query .= ' dev.id = '.$parentNode->index.' ORDER BY id';
80 $query .= ' LIMIT '.(count($parentNode->children)+$markskip).',1';
81 }
82 $DbResult = $Database->query($query);
83 $item = $DbResult->fetch_array();
84 if ($item) {
85// echo $item['id'].','.$parentNode->index.','.$level.'<br/>';
86// flush();
87 if (!isset($mark[$item['id']])) {
88 $mark[$item['id']] = 1;
89 $currentNode = new TreeItem();
90 $currentNode->index = $item['id'];
91 $currentNode->level = $level;
92 $currentNode->parentItem = $parentNode;
93 if ($level==0) {
94 $this->rootNode = $currentNode;
95 } else {
96 if ($level>1 && count($parentNode->children)==0) $parentNode->parentItem->forkcnt++;
97 array_push($parentNode->children,$currentNode);
98 }
99 $parentNode = $currentNode;
100 $level++;
101 $this->border[$level] = 0;
102 $markskip = 0;
103 } else {
104 $markskip++;
105 }
106 } else {
107 $currentNode = $parentNode;
108 $parentNode = $currentNode->parentItem;
109 $level--;
110 $markskip = 0;
111 }
112 } while ($level >= 1);
113 }
114
115 function calc_pos($node) {
116 if ($this->mode > 1) {
117 return 1.5 + $this->maxborder-$node->rpos+$node->pos;
118 } else return $node->pos;
119 }
120
121 /** Store specific tree node to DB */
122 function store_node($node) {
123 global $Database;
124 $first = $node->getFirst();
125 if ($first) { $first = $this->calc_pos($first); } else $first = '-1';
126 $last = $node->getLast();
127 if ($last) { $last = $this->calc_pos($last); } else $last = '-1';
128 $Database->query("INSERT INTO NetworkTopology (Host, Depth, Pos, First, Last) '.
129 'VALUES (".$node->index.','.$node->level.','.$this->calc_pos($node).','.$first.','.$last.");");
130 foreach ($node->children as $key => $value) {
131 $this->store_node($value);
132 }
133 }
134
135 /** Store all nodes of tree to DB */
136 function store() {
137 global $Database;
138 $Database->query('DELETE FROM NetworkTopology;');
139 $this->store_node($this->rootNode);
140 }
141
142 /** Build most left tree on node and all subnodes on given border */
143 function left_align($node) {
144 $node->pos = $this->border[$node->level];
145 $this->border[$node->level]++;
146 if (count($node->children)>0) {
147 if ($this->border[$node->level +1]>=$this->border[$node->level]) {
148 $node->pos = $this->border[$node->level+1];
149 $this->setborder($node->level, $this->border[$node->level+1]+1);
150 }
151 foreach ($node->children as $key => $value) {
152 if ($key == count($node->children)-1) {
153 if ($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
154 }
155 $this->left_align($value);
156 if ($key == 0) {
157 if ($this->border[$node->level] <= $this->border[$node->level+1]) {
158 $node->pos = $this->border[$node->level+1]-1;
159 $this->setborder($node->level, $this->border[$node->level+1]);
160 }
161 }
162 }
163 }
164 }
165
166 /** Build most right tree on node and all subnodes on given border */
167 function right_align($node) {
168 $this->mode = 2;
169 $node->rpos = $this->border[$node->level];
170 $this->border[$node->level]++;
171 if (count($node->children)>0) {
172 if ($this->border[$node->level +1]>=$this->border[$node->level]) {
173 $node->rpos = $this->border[$node->level+1];
174 $this->setborder($node->level, $this->border[$node->level+1]+1);
175 }
176 for ($key=count($node->children)-1;$key>=0;$key--) {
177 $value = $node->children[$key];
178 if ((count($value->children)>0) && count($node->order)>0) {
179 $value = $node->order[$value->index];
180 }
181 if ($key == 0) {
182 if ($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
183 }
184 $this->right_align($value);
185 if ($key == count($node->children)-1) {
186 if ($this->border[$node->level] <= $this->border[$node->level+1]) {
187 $node->rpos = $this->border[$node->level+1]-1;
188 $this->setborder($node->level, $this->border[$node->level+1]);
189 }
190 }
191 }
192 }
193 }
194
195
196 /** Reset construction border **/
197 function reset_border() {
198 foreach ($this->border as $key => $value) $this->border[$key] = 0;
199 $this->maxborder = 0;
200 }
201
202 /** Heuristic reordering of fork nodes */
203 function reorder_heur($node) {
204 global $debug;
205 $node->pos = $this->border[$node->level];
206 $this->border[$node->level]++;
207 $order = array(); // Seznam změněných indexů
208 if ($node->forkcnt>1) {
209 $preborder = $this->border;
210 $premax = $this->maxborder;
211 $bestmax = 0; // Nejmenší rozměr
212 $bestfit = 0; // Index nejvhodnějšího kandidáta
213 $forkmap = array(); // Seznam indexů vydličkových potomků
214 $target = 0; // Index cílového uzlu
215 $lastindex = 0; // Index poslední vydličky
216 foreach ($node->children as $key => $value) {
217 if (count($value->children)>0) {
218 array_push($forkmap,$value);
219 $order[$value->index]=0;
220 $lastindex = $value->index;
221 }
222 }
223 for ($i=0;$i<$node->forkcnt-1;$i++) {
224 for ($j=0;$j<count($forkmap);$j++) {
225 $this->border = $preborder;
226 $this->maxborder = $premax;
227 $k = 0; // index zpracovávané vydličky
228 foreach ($node->children as $key => $value) {
229 if (count($value->children)>0) {
230 if ($order[$value->index]) {
231 $value = $order[$value->index];
232 } else {
233 if ($k > 0) {
234 if ($k < $j) { $value = $forkmap[$k-1]; } else $value = $forkmap[$k];
235 } else {
236 $target = $value->index;
237 $value = $forkmap[$j];
238 }
239 $k++;
240 }
241 }
242 if ($key == count($node->children)-1) {
243 if ($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
244 }
245 $this->left_align($value);
246 if ($key == 0) {
247 if ($this->border[$node->level] <= $this->border[$node->level+1]) {
248 $node->pos = $this->border[$node->level+1]-1;
249 $this->setborder($node->level, $this->border[$node->level+1]);
250 }
251 }
252 }
253 if (($j==0) || ($this->maxborder < $bestmax)) {
254 $bestmax = $this->maxborder;
255 $bestfit = $j;
256 }
257 }
258 $order[$target]=$forkmap[$bestfit];
259 if ($debug) echo 'ORDER: '.$target.' > '.$forkmap[$bestfit]->index."\n";
260 array_splice($forkmap, $bestfit, 1);
261 }
262 $order[$lastindex]=$forkmap[0];
263 if ($debug) echo 'ORDER: '.$lastindex.' > '.$forkmap[0]->index."\n";
264 if ($debug) echo 'ORDERSTORE: '.$node->index."\n";
265 $node->order = $order;
266 $this->border = $preborder;
267 $this->maxborder = $premax;
268 }
269 if (count($node->children)>0) {
270 if ($this->border[$node->level +1]>=$this->border[$node->level]) {
271 $node->pos = $this->border[$node->level+1];
272 $this->setborder($node->level, $this->border[$node->level+1]+1);
273 }
274 foreach ($node->children as $key => $value) {
275 if ((count($value->children)>0) && count($order)>0) {
276 $value = $order[$value->index];
277 }
278 if ($key == count($node->children)-1) {
279 if ($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
280 }
281 $this->reorder($value);
282 if ($key == 0) {
283 if ($this->border[$node->level] <= $this->border[$node->level+1]) {
284 $node->pos = $this->border[$node->level+1]-1;
285 $this->setborder($node->level, $this->border[$node->level+1]);
286 }
287 }
288 }
289 }
290 }
291
292 /** Build most left tree on node and all subnodes on given border without leafs */
293 function left_stub($node) {
294 $node->pos = $this->border[$node->level];
295 $this->border[$node->level]++;
296 if (count($node->children)>0) {
297 $stubborder = $this->border[$node->level +1] + count($node->children);
298 if ($this->border[$node->level +1]>=$this->border[$node->level]) {
299 $node->pos = $this->border[$node->level+1];
300 $this->setborder($node->level, $this->border[$node->level+1]+1);
301 }
302 $forkcnt = 0; // Fork counter
303 foreach ($node->children as $key => $value) {
304 if ($forkcnt == count($node->children)-1) {
305 if ($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
306 }
307 if (count($value->children)>0) {
308 $this->left_stub($value);
309 if ($forkcnt == 0) {
310 if ($this->border[$node->level] <= $this->border[$node->level+1]) {
311 $node->pos = $this->border[$node->level+1]-1;
312 $this->setborder($node->level, $this->border[$node->level+1]);
313 }
314 }
315 $forkcnt++;
316 }
317 }
318 if ($stubborder > $this->border[$node->level +1]) $this->setborder($node->level+1,$stubborder);
319 }
320 }
321
322 /** Full single level reordering */
323 function reorder($node) {
324 global $debug;
325 $node->pos = $this->border[$node->level];
326 $this->border[$node->level]++;
327 $order = array(); // Seznam změněných indexů
328 if ($node->forkcnt>1) {
329 $preborder = $this->border;
330 $premax = $this->maxborder;
331 $bestmax = 0; // Nejmenší rozměr
332 $bestfit = 0; // Index nejvhodnějšího kandidáta
333 $forkmap = array(); // Seznam indexů vydličkových potomků
334 $target = 0; // Index cílového uzlu
335 $lastindex = 0; // Index poslední vydličky
336 $fact = 1; // Faktoriál kombinací vydliček
337 foreach ($node->children as $key => $value) {
338 if (count($value->children)>0) {
339 if ($key>0) $fact = $fact * ($key+1);
340 array_push($forkmap,$value);
341 $order[$value->index]=0;
342 $lastindex = $value->index;
343 }
344 }
345 for ($i=0;$i<$node->forkcnt-1;$i++) {
346 for ($j=0;$j<count($forkmap);$j++) {
347 $this->border = $preborder;
348 $this->maxborder = $premax;
349 $k = 0; // index zpracovávané vydličky
350 foreach ($node->children as $key => $value) {
351 if (count($value->children)>0) {
352 if ($order[$value->index]) {
353 $value = $order[$value->index];
354 } else {
355 if ($k > 0) {
356 if ($k < $j) { $value = $forkmap[$k-1]; } else $value = $forkmap[$k];
357 } else {
358 $target = $value->index;
359 $value = $forkmap[$j];
360 }
361 $k++;
362 }
363 }
364 if ($key == count($node->children)-1) {
365 if ($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
366 }
367 $this->left_align($value);
368 if ($key == 0) {
369 if ($this->border[$node->level] <= $this->border[$node->level+1]) {
370 $node->pos = $this->border[$node->level+1]-1;
371 $this->setborder($node->level, $this->border[$node->level+1]);
372 }
373 }
374 }
375 if (($j==0) || ($this->maxborder < $bestmax)) {
376 $bestmax = $this->maxborder;
377 $bestfit = $j;
378 }
379 }
380 $order[$target]=$forkmap[$bestfit];
381 if ($debug) echo 'ORDER: '.$target.' > '.$forkmap[$bestfit]->index."\n";
382 array_splice($forkmap, $bestfit, 1);
383 }
384 $order[$lastindex]=$forkmap[0];
385 if ($debug) echo 'ORDER: '.$lastindex.' > '.$forkmap[0]->index."\n";
386 if ($debug) echo 'ORDERSTORE: '.$node->index."\n";
387 $node->order = $order;
388 $this->border = $preborder;
389 $this->maxborder = $premax;
390 }
391 // Missing stub stuffing
392 if (count($node->children)>0) {
393 if ($this->border[$node->level +1]>=$this->border[$node->level]) {
394 $node->pos = $this->border[$node->level+1];
395 $this->setborder($node->level, $this->border[$node->level+1]+1);
396 }
397 foreach ($node->children as $key => $value) {
398 if ((count($value->children)>0) && count($order)>0) {
399 $value = $order[$value->index];
400 }
401 if ($key == count($node->children)-1) {
402 if ($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
403 }
404 $this->reorder($value);
405 if ($key == 0) {
406 if ($this->border[$node->level] <= $this->border[$node->level+1]) {
407 $node->pos = $this->border[$node->level+1]-1;
408 $this->setborder($node->level, $this->border[$node->level+1]);
409 }
410 }
411 }
412 }
413 }
414
415 function setborder($level, $value) {
416 if ($value > $this->maxborder) $this->maxborder = $value;
417 $this->border[$level] = $value;
418 }
419}
420
421// Generator Main Procedure
422$mytree = new TreeGen();
423$mytree->populate();
424$mytree->left_align($mytree->rootNode);
425//$mytree->reorder($mytree->rootNode);
426//$mytree->left_stub($mytree->rootNode);
427$mytree->reset_border();
428$mytree->right_align($mytree->rootNode);
429$mytree->store();
430
431echo('Topologie byla vygenerovana.');
Note: See TracBrowser for help on using the repository browser.