children)>0) {
if (count($this->order)>0) {
if (count($this->children[0]->children)>0) return $this->order[$this->children[0]->index];
}
return $this->children[0];
} else return null;
}
function getLast() {
if (count($this->children)>0) {
if (count($this->order)>0) {
if (count($this->children[count($this->children)-1]->children)>0) return $this->order[$this->children[count($this->children)-1]->index];
}
return $this->children[count($this->children)-1];
} else return null;
}
}
class TreeGen {
/** Kořenový uzel */
var $rootNode;
/** Hranice generátorů pozic */
var $border = array();
/** Maximální šířka hranice */
var $maxborder = 0;
/** Mód provedených operací */
var $mode = 0;
/** Vytvoří stromovou strukturu načtením záznamů z databáze */
function populate() {
global $Database;
$TopHostName = 'nix-router';
// rodičovský uzel
$parentNode = null;
// Aktuální uzel
$currentNode = null;
// Aktuální úroveň
$level = 0;
$this->border[0]=0;
$mark = array();
$markskip = 0;
do {
if ($level == 0) {
$query = 'SELECT dev.id AS id FROM NetworkDevice dev WHERE dev.name = "'.$TopHostName.'" LIMIT 0,1';
} else {
$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 ';
$query .= ' dev.id = '.$parentNode->index.' ORDER BY id';
$query .= ' LIMIT '.(count($parentNode->children)+$markskip).',1';
}
$DbResult = $Database->query($query);
$item = $DbResult->fetch_array();
if ($item) {
// echo $item['id'].','.$parentNode->index.','.$level.'
';
// flush();
if (!isset($mark[$item['id']])) {
$mark[$item['id']] = 1;
$currentNode = new TreeItem();
$currentNode->index = $item['id'];
$currentNode->level = $level;
$currentNode->parentItem = $parentNode;
if ($level==0) {
$this->rootNode = $currentNode;
} else {
if ($level>1 && count($parentNode->children)==0) $parentNode->parentItem->forkcnt++;
array_push($parentNode->children,$currentNode);
}
$parentNode = $currentNode;
$level++;
$this->border[$level] = 0;
$markskip = 0;
} else {
$markskip++;
}
} else {
$currentNode = $parentNode;
$parentNode = $currentNode->parentItem;
$level--;
$markskip = 0;
}
} while ($level >= 1);
}
function calc_pos($node) {
if ($this->mode > 1) {
return 1.5 + $this->maxborder-$node->rpos+$node->pos;
} else return $node->pos;
}
/** Store specific tree node to DB */
function store_node($node) {
global $Database;
$first = $node->getFirst();
if ($first) { $first = $this->calc_pos($first); } else $first = '-1';
$last = $node->getLast();
if ($last) { $last = $this->calc_pos($last); } else $last = '-1';
$Database->query("INSERT INTO NetworkTopology (Host, Depth, Pos, First, Last) '.
'VALUES (".$node->index.','.$node->level.','.$this->calc_pos($node).','.$first.','.$last.");");
foreach ($node->children as $key => $value) {
$this->store_node($value);
}
}
/** Store all nodes of tree to DB */
function store() {
global $Database;
$Database->query('DELETE FROM NetworkTopology;');
$this->store_node($this->rootNode);
}
/** Build most left tree on node and all subnodes on given border */
function left_align($node) {
$node->pos = $this->border[$node->level];
$this->border[$node->level]++;
if (count($node->children)>0) {
if ($this->border[$node->level +1]>=$this->border[$node->level]) {
$node->pos = $this->border[$node->level+1];
$this->setborder($node->level, $this->border[$node->level+1]+1);
}
foreach ($node->children as $key => $value) {
if ($key == count($node->children)-1) {
if ($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
}
$this->left_align($value);
if ($key == 0) {
if ($this->border[$node->level] <= $this->border[$node->level+1]) {
$node->pos = $this->border[$node->level+1]-1;
$this->setborder($node->level, $this->border[$node->level+1]);
}
}
}
}
}
/** Build most right tree on node and all subnodes on given border */
function right_align($node) {
$this->mode = 2;
$node->rpos = $this->border[$node->level];
$this->border[$node->level]++;
if (count($node->children)>0) {
if ($this->border[$node->level +1]>=$this->border[$node->level]) {
$node->rpos = $this->border[$node->level+1];
$this->setborder($node->level, $this->border[$node->level+1]+1);
}
for ($key=count($node->children)-1;$key>=0;$key--) {
$value = $node->children[$key];
if ((count($value->children)>0) && count($node->order)>0) {
$value = $node->order[$value->index];
}
if ($key == 0) {
if ($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
}
$this->right_align($value);
if ($key == count($node->children)-1) {
if ($this->border[$node->level] <= $this->border[$node->level+1]) {
$node->rpos = $this->border[$node->level+1]-1;
$this->setborder($node->level, $this->border[$node->level+1]);
}
}
}
}
}
/** Reset construction border **/
function reset_border() {
foreach ($this->border as $key => $value) $this->border[$key] = 0;
$this->maxborder = 0;
}
/** Heuristic reordering of fork nodes */
function reorder_heur($node) {
global $debug;
$node->pos = $this->border[$node->level];
$this->border[$node->level]++;
$order = array(); // Seznam změněných indexů
if ($node->forkcnt>1) {
$preborder = $this->border;
$premax = $this->maxborder;
$bestmax = 0; // Nejmenší rozměr
$bestfit = 0; // Index nejvhodnějšího kandidáta
$forkmap = array(); // Seznam indexů vydličkových potomků
$target = 0; // Index cílového uzlu
$lastindex = 0; // Index poslední vydličky
foreach ($node->children as $key => $value) {
if (count($value->children)>0) {
array_push($forkmap,$value);
$order[$value->index]=0;
$lastindex = $value->index;
}
}
for ($i=0;$i<$node->forkcnt-1;$i++) {
for ($j=0;$jborder = $preborder;
$this->maxborder = $premax;
$k = 0; // index zpracovávané vydličky
foreach ($node->children as $key => $value) {
if (count($value->children)>0) {
if ($order[$value->index]) {
$value = $order[$value->index];
} else {
if ($k > 0) {
if ($k < $j) { $value = $forkmap[$k-1]; } else $value = $forkmap[$k];
} else {
$target = $value->index;
$value = $forkmap[$j];
}
$k++;
}
}
if ($key == count($node->children)-1) {
if ($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
}
$this->left_align($value);
if ($key == 0) {
if ($this->border[$node->level] <= $this->border[$node->level+1]) {
$node->pos = $this->border[$node->level+1]-1;
$this->setborder($node->level, $this->border[$node->level+1]);
}
}
}
if (($j==0) || ($this->maxborder < $bestmax)) {
$bestmax = $this->maxborder;
$bestfit = $j;
}
}
$order[$target]=$forkmap[$bestfit];
if ($debug) echo 'ORDER: '.$target.' > '.$forkmap[$bestfit]->index."\n";
array_splice($forkmap, $bestfit, 1);
}
$order[$lastindex]=$forkmap[0];
if ($debug) echo 'ORDER: '.$lastindex.' > '.$forkmap[0]->index."\n";
if ($debug) echo 'ORDERSTORE: '.$node->index."\n";
$node->order = $order;
$this->border = $preborder;
$this->maxborder = $premax;
}
if (count($node->children)>0) {
if ($this->border[$node->level +1]>=$this->border[$node->level]) {
$node->pos = $this->border[$node->level+1];
$this->setborder($node->level, $this->border[$node->level+1]+1);
}
foreach ($node->children as $key => $value) {
if ((count($value->children)>0) && count($order)>0) {
$value = $order[$value->index];
}
if ($key == count($node->children)-1) {
if ($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
}
$this->reorder($value);
if ($key == 0) {
if ($this->border[$node->level] <= $this->border[$node->level+1]) {
$node->pos = $this->border[$node->level+1]-1;
$this->setborder($node->level, $this->border[$node->level+1]);
}
}
}
}
}
/** Build most left tree on node and all subnodes on given border without leafs */
function left_stub($node) {
$node->pos = $this->border[$node->level];
$this->border[$node->level]++;
if (count($node->children)>0) {
$stubborder = $this->border[$node->level +1] + count($node->children);
if ($this->border[$node->level +1]>=$this->border[$node->level]) {
$node->pos = $this->border[$node->level+1];
$this->setborder($node->level, $this->border[$node->level+1]+1);
}
$forkcnt = 0; // Fork counter
foreach ($node->children as $key => $value) {
if ($forkcnt == count($node->children)-1) {
if ($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
}
if (count($value->children)>0) {
$this->left_stub($value);
if ($forkcnt == 0) {
if ($this->border[$node->level] <= $this->border[$node->level+1]) {
$node->pos = $this->border[$node->level+1]-1;
$this->setborder($node->level, $this->border[$node->level+1]);
}
}
$forkcnt++;
}
}
if ($stubborder > $this->border[$node->level +1]) $this->setborder($node->level+1,$stubborder);
}
}
/** Full single level reordering */
function reorder($node) {
global $debug;
$node->pos = $this->border[$node->level];
$this->border[$node->level]++;
$order = array(); // Seznam změněných indexů
if ($node->forkcnt>1) {
$preborder = $this->border;
$premax = $this->maxborder;
$bestmax = 0; // Nejmenší rozměr
$bestfit = 0; // Index nejvhodnějšího kandidáta
$forkmap = array(); // Seznam indexů vydličkových potomků
$target = 0; // Index cílového uzlu
$lastindex = 0; // Index poslední vydličky
$fact = 1; // Faktoriál kombinací vydliček
foreach ($node->children as $key => $value) {
if (count($value->children)>0) {
if ($key>0) $fact = $fact * ($key+1);
array_push($forkmap,$value);
$order[$value->index]=0;
$lastindex = $value->index;
}
}
for ($i=0;$i<$node->forkcnt-1;$i++) {
for ($j=0;$jborder = $preborder;
$this->maxborder = $premax;
$k = 0; // index zpracovávané vydličky
foreach ($node->children as $key => $value) {
if (count($value->children)>0) {
if ($order[$value->index]) {
$value = $order[$value->index];
} else {
if ($k > 0) {
if ($k < $j) { $value = $forkmap[$k-1]; } else $value = $forkmap[$k];
} else {
$target = $value->index;
$value = $forkmap[$j];
}
$k++;
}
}
if ($key == count($node->children)-1) {
if ($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
}
$this->left_align($value);
if ($key == 0) {
if ($this->border[$node->level] <= $this->border[$node->level+1]) {
$node->pos = $this->border[$node->level+1]-1;
$this->setborder($node->level, $this->border[$node->level+1]);
}
}
}
if (($j==0) || ($this->maxborder < $bestmax)) {
$bestmax = $this->maxborder;
$bestfit = $j;
}
}
$order[$target]=$forkmap[$bestfit];
if ($debug) echo 'ORDER: '.$target.' > '.$forkmap[$bestfit]->index."\n";
array_splice($forkmap, $bestfit, 1);
}
$order[$lastindex]=$forkmap[0];
if ($debug) echo 'ORDER: '.$lastindex.' > '.$forkmap[0]->index."\n";
if ($debug) echo 'ORDERSTORE: '.$node->index."\n";
$node->order = $order;
$this->border = $preborder;
$this->maxborder = $premax;
}
// Missing stub stuffing
if (count($node->children)>0) {
if ($this->border[$node->level +1]>=$this->border[$node->level]) {
$node->pos = $this->border[$node->level+1];
$this->setborder($node->level, $this->border[$node->level+1]+1);
}
foreach ($node->children as $key => $value) {
if ((count($value->children)>0) && count($order)>0) {
$value = $order[$value->index];
}
if ($key == count($node->children)-1) {
if ($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
}
$this->reorder($value);
if ($key == 0) {
if ($this->border[$node->level] <= $this->border[$node->level+1]) {
$node->pos = $this->border[$node->level+1]-1;
$this->setborder($node->level, $this->border[$node->level+1]);
}
}
}
}
}
function setborder($level, $value) {
if ($value > $this->maxborder) $this->maxborder = $value;
$this->border[$level] = $value;
}
}
// Generator Main Procedure
$mytree = new TreeGen();
$mytree->populate();
$mytree->left_align($mytree->rootNode);
//$mytree->reorder($mytree->rootNode);
//$mytree->left_stub($mytree->rootNode);
$mytree->reset_border();
$mytree->right_align($mytree->rootNode);
$mytree->store();
echo('Topologie byla vygenerovana.');