Changeset 81 for www/is/topologie-gen.php

Timestamp:

Jun 22, 2008, 11:02:54 PM (16 years ago)

Author:

hajdam

Message:

Testovací verze topologie

File:

• www/is/topologie-gen.php (modified) (5 diffs)

www/is/topologie-gen.php

@@ -1 +1 @@
 <?php
  // Skript pro generování grafu stromové struktury sítě do PNG obrázku
-include('../global.php');
+include('../global2.php');
+global $Database;
 
 if(array_key_exists('debug', $_GET)) $debug = $_GET['debug'];
 else $debug = 0;
-$TopHostName = 'NIX-ROUTER';
 // $debug = 0;
 
 class treeitem {
   /** Index prvku v databazi */
-  var index = 0;
+  var $index = 0;
 
   /** Pozice prvku zleva */
-  var pos = 0;
+  var $pos = 0;
+
+  /** Pozice prvku zprava */
+  var $rpos = 0;
 
   /** Pozice prvku shora */
-  var level = 0;
+  var $level = 0;
+
+  /** Počet potomků s potomky */
+  var $forkcnt = 0;
 
   /** Pole potomků */
-  var children = array();
+  var $children = array();
 
   /** Předek */
-  var parentItem;
+  var $parentItem;
 
   function getFirst() {
+    if (count($this->children)>0) {
+      return $this->children[0];
+    } else return null;
   }
 
   function getLast() {
+    if (count($this->children)>0) {
+      return $this->children[count($this->children)-1];
+    } else return null;
   }
 }
@@ -34 +46 @@
 
   /** Kořenový uzel */
-  var rootNode;
-
+  var $rootNode;
+  /** Hranice generátorů pozic */
+  var $border = array();
+  /** Maximální šířka hranice */
+  var $maxborder = 0;
+
+  /** Vytvoří stromovou strukturu načtením záznamů z databáze */
   function populate() {
+    global $Database;
+    $TopHostName = 'NIX-ROUTER';
     // rodičovský uzel
-    var $parentNode;
+    $parentNode = null;
     // Aktuální uzel
-    var $currentNode;
+    $currentNode = null;
     // Aktuální úroveň
     $level = 0;
+    $this->border[0]=0;
 
     do {
@@ -48 +68 @@
       if ($level == 0) {
         $query .= 'name = "'.$TopHostName.'" ORDER BY id';
+        $query .= ' LIMIT 0,1';
       } else {
-        $query .= ' parent = '.$parentNode->level.' ORDER BY id';
-      }
-      $query .= ' LIMIT '.count($parentNode->children).',1';
+        $query .= ' parent = '.$parentNode->index.' ORDER BY id';
+        $query .= ' LIMIT '.count($parentNode->children).',1';
+      }
       $DbResult = $Database->query($query);
       $item = $DbResult->fetch_array();
@@ -57 +78 @@
         $currentNode = new treeitem();
         $currentNode->index = $item['id'];
-        $currentNode->level = $item['level'];
+        $currentNode->level = $level;
         $currentNode->parentItem = $parentNode;
         if ($level==0) {
-          $rootNode = $currentNode;
+          $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;
@@ -71 +94 @@
         $level--;
       }
-    } while($level >= 0);
+    } while($level >= 1);
+  }
+
+  function store_node($node) {
+      global $Database;
+      $first = $node->getFirst();
+      if ($first) { $first = $first->pos; } else $first = '-1';
+      $last = $node->getLast();
+      if ($last) { $last = $last->pos; } else $last = '-1';
+      $Database->query("INSERT INTO hosts_topology (host, depth, pos, first, last) VALUES (".$node->index.','.$node->level.','.$node->pos.','.$first.','.$last.");");
+      foreach($node->children as $key => $value) {
+        $this->store_node($value);
+      }
   }
 
   function store() {
+    global $Database;
     $Database->query("DELETE FROM hosts_topology;");
-    store_node($rootNode);
-  }
-
-  function store_node($node) {
-    $Database->query("INSERT INTO hosts_topology (host, depth, pos, first, last) VALUES (".$node->index.','.$node->level.','.$node->pos.','.$node->getFirst()->pos.','.$node->getLast()->pos.");");
-  }
-
-// === Zpětné vyvážení stromu do hloubky =======================================
-function balance($id, $level, &$vlast, &$vleft, &$vpred, &$vfirst, &$vnext, &$tbound, &$width, $limit) 
-{
-  global $debug, $bbound;
-  
-  if(!array_key_exists($id, $vfirst)) $vfirst[$id] = 0;
-  if($i = $vfirst[$id]) 
-  {
-    //if ($debug==2) echo $id.':'.@$i.','.@$vpred[$i].'-'.@$vleft[@$vpred[$i]]."\n";
-    if (($vlast[$id] > 0) && ($vleft[$id] > $vleft[$vlast[$id]])) 
-    {
-      $diff=$vleft[$id]-$vleft[$vlast[$id]];
-      $i=$vfirst[$id];
-      if ($vleft[$id] >= $tbound[$level]) 
-      {
-        $tbound[$level] = $vleft[$id] + 2;
-        if ($vleft[$id] > $width) $width = $vleft[$id];
-      }
-    } else {
-      $diff=0;
-      if ($vpred[$i]&&($vleft[$i]<=$vleft[$vpred[$i]])) 
-      {
-        $diff=$vleft[$i]-$vleft[$vpred[$i]]+2;
-      } else $i = 0;
+    $this->store_node($this->rootNode);
+  }
+
+  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]);
+          }
+        }
+      }
     }
-    while ($i>0) 
-    {
-      $vleft[$i]+=$diff;
-      $limit = balance($i,$level+1, $vlast,$vleft,$vpred, $vfirst,$vnext,$tbound, $width, $limit) + 2;
-      if(!array_key_exists($i, $vnext)) $vnext[$i] = 0;
-      $i = $vnext[$i];
+  }
+
+  function reorder($node) {
+    $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;
+        }
+      }
+      if ($node->forkcnt > 0) echo $node->index.':'.$node->forkcnt."\n";
+      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];
+        echo 'ORDER: '.$target.' > '.$forkmap[$bestfit]->index."\n";
+        array_splice($forkmap, $bestfit, 1);
+      }
+      $order[$lastindex]=$forkmap[0];
+      echo 'ORDER: '.$lastindex.' > '.$forkmap[0]->index."\n";
+      $this->order[$node->index] = $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) {
+          echo $node->index.' '.$value->index."\n";
+          $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;
   }
 }
 
-// === Generování rovinné stromové struktury ===================================
-function gentree($mode)                         // depth-first algorithm
-{                        
-  global $debug, $TopHostName, $Database;
-  
-  // --- Inicializace ----------------------------------------------------------
-  $tbound = array();                               // Hranice pozic jednotlivých úrovní
-  $tranger = array();                              // Hranicni prvek
-  $position = array();                             // Pozice aktuálního prvku na dané úrovni
-  $vfirst = array();                               // První potomek prvku
-  $vlast = array();                                // Poslední potomek prvku
-  $vnext = array();                                // Následující sourozenec
-  $vleft = array();                                // Pozice prvku zleva
-  $vtop = array();                                 // Pozice prvku shora
-  $vpred = array();                                // Vedlejsi prvek na řádku
-  
-  $index = 0;                                    // Index aktuálního prvku
-  $curr = 0;                                     // Aktuální prvek
-  $level = 0;                                    // Aktuální úroveň hloubky ve stromu
-  $width = 0;                                    // Šířka stromu
-  $height = 0;                                   // Hloubka stromu
-
-  $parent[$level] = 0;                             // Rodič dané úrovně
-  $position[$level] = 0;                           // Aktuální pozice prvku na dané úrovni
-  $count[$level] = 0;                              // Počet prvků na dané úrovni
-  
-  $maxindex = 0;
-  $tbound[$level] = 0;
-  $tranger[$level] = 0;
-   
-  // --- Hlavní cyklus ---------------------------------------------------------
-  do 
-  {
-  // --- Proveď databázový dotaz -----------------------------------------------
-    $query = 'SELECT * FROM hosts WHERE used=1 AND ';
-    if ($level == 0) 
-    { 
-      $query .= 'name = "'.$TopHostName.'" ORDER BY id'; 
-    } else 
-    {
-      $query .= ' parent = '.$parent[$level].' ORDER BY id';
-    }
-    if ($mode) $query.=' DESC';
-    $query .= ' LIMIT '.$position[$level].',1';
-    //echo($query.'<br>');
-    $DbResult = $Database->query($query);
-    $item = $DbResult->fetch_array();
-    //print_r($item);
-    if($item) 
-    {
-  // --- Zpracování položky z DB -----------------------------------------------
-      if($position[$level] > 0) 
-      {
-        $vnext[$curr] = $item['id']; // Neprvní položka, nastav předchozí
-      }
-      $curr = $item['id'];
-      if ($curr > $maxindex) $maxindex = $curr;
-      if ($position[$level] == 0) $vfirst[$parent[$level]]=$curr; // První položka, nastav první
-      $vlast[$parent[$level]] = $curr;
-      $vtop[$curr] = $level;
-      if(!array_key_exists($level, $tbound)) $tbound[$level] = 0;
-      $vleft[$curr] = $tbound[$level];
-      if(!array_key_exists($level, $tranger)) $tranger[$level] = 0;
-      $vpred[$curr] = $tranger[$level];
-      $tranger[$level] = $curr;
-      if (($debug == 3) && ($level == 8)) echo $curr.',';
-      $position[$level]++;
-      $count[$level]++;
-  // --- Zjisti existenci potomků ----------------------------------------------
-      $DbResult = $Database->query("SELECT COUNT(*) FROM hosts WHERE used=1 AND parent = ".$curr);
-      $childcnt = $DbResult->fetch_array();
-      if ($childcnt[0] > 0) 
-      {    
-        // Uzelový vrchol
-        if(array_key_exists($level + 1, $tbound))                  
-          if($tbound[$level + 1] > $vleft[$curr]) $vleft[$curr] = $tbound[$level + 1];
-      }
-      $tbound[$level] = $vleft[$curr] + 2;
-      if ($vleft[$curr] > $width) $width = $vleft[$curr];
-      if ($childcnt[0] > 0) 
-      {
-        $level++;
-        if ($level > $height) $height = $level;
-        $parent[$level] = $curr;
-        $position[$level] = 0;
-        $count[$level] = 0;
-      } else $index++;                            // Listový vrchol
-    } else 
-    {
-  // --- Zarovnávání prvků kvůli vzhledu
-      if(!array_key_exists($vfirst[$parent[$level]], $vleft)) $vleft[$vfirst[$parent[$level]]] = 0;
-      if(!array_key_exists($parent[$level], $vleft)) $vleft[$parent[$level]] = 0;
-      if ($vleft[$vfirst[$parent[$level]]] > $vleft[$parent[$level]]) 
-      {
-        $vleft[$parent[$level]] = $vleft[$vfirst[$parent[$level]]];
-        if ($vleft[$parent[$level]]+2>$tbound[$level-1]) $tbound[$level-1] = $vleft[$parent[$level]]+2;
-      }
-      balance($parent[$level],$level, $vlast,$vleft,$vpred,$vfirst,$vnext,$tbound, $width, 0);
-      if ($position[$level]==1) 
-      {
-        $vleft[$vfirst[$parent[$level]]] = $vleft[$parent[$level]];
-      }
-      $level--;
-      if(!array_key_exists($level, $parent)) $parent[$level] = 0;
-      if(!array_key_exists($parent[$level], $vlast)) $vlast[$parent[$level]] = 0;
-      $curr = $vlast[$parent[$level]];
-      
-      if(!array_key_exists($level, $tbound)) $tbound[$level] = 0;
-      if(!array_key_exists($level + 1, $tbound)) $tbound[$level + 1] = 0;
-      if($tbound[$level] > $tbound[$level + 1]) $tbound[$level + 1] = $tbound[$level];
-    }
-  } while($level >= 0);
-  $data = compact('tbound', 'count', 'tbound', 'vfirst', 'vlast', 'vtop', 'vleft', 'height', 'width', 'index', 'maxindex');
-  return($data);
-};
-
-// === Vytvoř stromy a ulož výsledek do databáze ===============================
-$Database->query("DELETE FROM hosts_topology;");
-extract(gentree(0));
-// exit();
-$data = gentree(1);
-$datawidth = $data['width'];
-for($i=0; $i <= $maxindex; $i++)
-{ 
-  if(!array_key_exists($i, $vleft)) $vleft[$i] = 0;
-  if(!array_key_exists($i, $data['vleft'])) $data['vleft'][$i] = 0;
-  if(!array_key_exists($i, $vtop)) $vtop[$i] = 0;
-  if(!array_key_exists($i, $vfirst)) $vfirst[$i] = 0;
-  if(!array_key_exists($i, $vlast)) $vlast[$i] = 0;
-  if(!array_key_exists($vfirst[$i], $data['vleft'])) $data['vleft'][$vfirst[$i]] = 0;
-  if(!array_key_exists($vlast[$i], $data['vleft'])) $data['vleft'][$vlast[$i]] = 0;
-//  $vleft[$i] = ($vleft[$i]*2 + ($datawidth - $data['vleft'][$i]));
-  if($vfirst[$i] > 0) {
-    $first = (($vleft[$vfirst[$i]] + ($datawidth - $data['vleft'][$vfirst[$i]]))/2);
-    $last = (($vleft[$vlast[$i]] + ($datawidth - $data['vleft'][$vlast[$i]]))/2);
-  } else {
-    $first = -1;
-    $last = -1;
-  }
-  
-  $Database->query("INSERT INTO hosts_topology (host, depth, pos, first, last) VALUES (".$i.','.$vtop[$i].','.(($vleft[$i] + ($datawidth - $data['vleft'][$i]))/2).','.$first.','.$last.");");
-}
+// Hlavní smyčka programu
+$mytree = new treegen();
+$mytree->populate();
+//$mytree->left_align($mytree->rootNode);
+$mytree->reorder($mytree->rootNode);
+$mytree->store();
 
 echo('Topologie byla vygenerovana.'); ?>