Changeset 222 for trunk/is/topologie-gen.php

Timestamp:

May 31, 2009, 8:48:51 PM (15 years ago)

Author:

hajdam

Message:

Úprava zobrazení topologie

File:

• trunk/is/topologie-gen.php (modified) (12 diffs)

trunk/is/topologie-gen.php

@@ -1 +1 @@
 <?php
- // Skript pro generování grafu stromové struktury sítě do PNG obrázku
-include('../global2.php');
+// Vertically-balanced Tree Topology Generator
+// Author: Miroslav Hajda hajdam@users.sf.net
+
+include('../global.php');
 global $Database, $debug;
 
 if(array_key_exists('debug', $_GET)) $debug = $_GET['debug'];
 else $debug = 0;
-$debug = 0;
-
-class treeitem {
+//$debug = 0;
+
+class TreeItem {
   /** Index prvku v databazi */
   var $index = 0;
-
   /** Pozice prvku zleva */
   var $pos = 0;
-
   /** Pozice prvku zprava */
   var $rpos = 0;
-
   /** Pozice prvku shora */
   var $level = 0;
-
   /** Počet potomků s potomky */
   var $forkcnt = 0;
-
   /** Pole potomků */
   var $children = array();
-
   /** Předek */
   var $parentItem;
-
   /** Změna pořadí prvků */
   var $order = array();
@@ -52 +47 @@
 }
 
-class treegen {
+class TreeGen {
 
   /** Kořenový uzel */
@@ -66 +61 @@
   function populate() {
     global $Database;
-    $TopHostName = 'NIX-ROUTER';
+    $TopHostName = 'nix-router';
     // rodičovský uzel
     $parentNode = null;
@@ -74 +69 @@
     $level = 0;
     $this->border[0]=0;
+    $mark = array();
 
     do {
-      $query = 'SELECT * FROM hosts WHERE used=1 AND ';
       if ($level == 0) {
-        $query .= 'name = "'.$TopHostName.'" ORDER BY id';
-        $query .= ' LIMIT 0,1';
+        $query = 'SELECT dev.id AS id FROM NetworkDevice dev WHERE dev.name = "'.$TopHostName.'" LIMIT 0,1';
       } else {
-        $query .= ' parent = '.$parentNode->index.' ORDER BY id';
+        $query = 'SELECT trg.id 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).',1';
       }
       $DbResult = $Database->query($query);
       $item = $DbResult->fetch_array();
-      if($item) {
-        $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;
+      if ($item) {
+//        echo $item['id'].'<br/>';
+//        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;
+        }
       } else {
         $currentNode = $parentNode;
@@ -109 +109 @@
 
   function calc_pos($node) {
-    if ($this->mode) {
+    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;
@@ -126 +127 @@
   }
 
+  /** Store all nodes of tree to DB */
   function store() {
     global $Database;
@@ -132 +134 @@
   }
 
+  /** Build most left tree on node and all subnodes on given border */
   function left_align($node) {
     $node->pos = $this->border[$node->level];
@@ -155 +158 @@
   }
 
+  /** Build most right tree on node and all subnodes on given border */
   function right_align($node) {
-    $this->mode = 1;
+    $this->mode = 2;
     $node->rpos = $this->border[$node->level];
     $this->border[$node->level]++;
@@ -183 +187 @@
   }
 
+
+  /** Reset construction border **/
   function reset_border() {
     foreach($this->border as $key => $value) $this->border[$key] = 0;
@@ -188 +194 @@
   }
 
-  function reorder($node) {
+  /** Heuristic reordering of fork nodes */
+  function reorder_heur($node) {
     global $debug;
     $node->pos = $this->border[$node->level];
@@ -277 +284 @@
   }
 
+  /** 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;$j<count($forkmap);$j++) {
+          $this->border = $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;
@@ -283 +413 @@
 }
 
-// Hlavní smyčka programu
-$mytree = new treegen();
+// Generator Main Procedure
+$mytree = new TreeGen();
 $mytree->populate();
-//$mytree->left_align($mytree->rootNode);
-$mytree->reorder($mytree->rootNode);
+$mytree->left_align($mytree->rootNode);
+//$mytree->reorder($mytree->rootNode);
+//$mytree->left_stub($mytree->rootNode);
 $mytree->reset_border();
 $mytree->right_align($mytree->rootNode);