Changeset 81 for www/is


Ignore:
Timestamp:
Jun 22, 2008, 11:02:54 PM (17 years ago)
Author:
hajdam
Message:

Testovací verze topologie

File:
1 edited

Legend:

Unmodified
Added
Removed

  • www/is/topologie-gen.php

    r80 r81  
    11<?php
    22 // Skript pro generování grafu stromové struktury sítě do PNG obrázku
    3 include('../global.php');
     3include('../global2.php');
     4global $Database;
    45
    56if(array_key_exists('debug', $_GET)) $debug = $_GET['debug'];
    67else $debug = 0;
    7 $TopHostName = 'NIX-ROUTER';
    88// $debug = 0;
    99
    1010class treeitem {
    1111  /** Index prvku v databazi */
    12   var index = 0;
     12  var $index = 0;
    1313
    1414  /** Pozice prvku zleva */
    15   var pos = 0;
     15  var $pos = 0;
     16
     17  /** Pozice prvku zprava */
     18  var $rpos = 0;
    1619
    1720  /** Pozice prvku shora */
    18   var level = 0;
     21  var $level = 0;
     22
     23  /** Počet potomků s potomky */
     24  var $forkcnt = 0;
    1925
    2026  /** Pole potomků */
    21   var children = array();
     27  var $children = array();
    2228
    2329  /** Předek */
    24   var parentItem;
     30  var $parentItem;
    2531
    2632  function getFirst() {
     33    if (count($this->children)>0) {
     34      return $this->children[0];
     35    } else return null;
    2736  }
    2837
    2938  function getLast() {
     39    if (count($this->children)>0) {
     40      return $this->children[count($this->children)-1];
     41    } else return null;
    3042  }
    3143}
    … …  
    3446
    3547  /** Kořenový uzel */
    36   var rootNode;
    37 
     48  var $rootNode;
     49  /** Hranice generátorů pozic */
     50  var $border = array();
     51  /** Maximální šířka hranice */
     52  var $maxborder = 0;
     53
     54  /** Vytvoří stromovou strukturu načtením záznamů z databáze */
    3855  function populate() {
     56    global $Database;
     57    $TopHostName = 'NIX-ROUTER';
    3958    // rodičovský uzel
    40     var $parentNode;
     59    $parentNode = null;
    4160    // Aktuální uzel
    42     var $currentNode;
     61    $currentNode = null;
    4362    // Aktuální úroveň
    4463    $level = 0;
     64    $this->border[0]=0;
    4565
    4666    do {
    … …  
    4868      if ($level == 0) {
    4969        $query .= 'name = "'.$TopHostName.'" ORDER BY id';
     70        $query .= ' LIMIT 0,1';
    5071      } else {
    51         $query .= ' parent = '.$parentNode->level.' ORDER BY id';
    52       }
    53       $query .= ' LIMIT '.count($parentNode->children).',1';
     72        $query .= ' parent = '.$parentNode->index.' ORDER BY id';
     73        $query .= ' LIMIT '.count($parentNode->children).',1';
     74      }
    5475      $DbResult = $Database->query($query);
    5576      $item = $DbResult->fetch_array();
    … …  
    5778        $currentNode = new treeitem();
    5879        $currentNode->index = $item['id'];
    59         $currentNode->level = $item['level'];
     80        $currentNode->level = $level;
    6081        $currentNode->parentItem = $parentNode;
    6182        if ($level==0) {
    62           $rootNode = $currentNode;
     83          $this->rootNode = $currentNode;
    6384        } else {
     85          if ($level>1 && count($parentNode->children)==0) $parentNode->parentItem->forkcnt++;
    6486          array_push($parentNode->children,$currentNode);
    6587        }
    6688        $parentNode = $currentNode;
    6789        $level++;
     90        $this->border[$level] = 0;
    6891      } else {
    6992        $currentNode = $parentNode;
    … …  
    7194        $level--;
    7295      }
    73     } while($level >= 0);
     96    } while($level >= 1);
     97  }
     98
     99  function store_node($node) {
     100      global $Database;
     101      $first = $node->getFirst();
     102      if ($first) { $first = $first->pos; } else $first = '-1';
     103      $last = $node->getLast();
     104      if ($last) { $last = $last->pos; } else $last = '-1';
     105      $Database->query("INSERT INTO hosts_topology (host, depth, pos, first, last) VALUES (".$node->index.','.$node->level.','.$node->pos.','.$first.','.$last.");");
     106      foreach($node->children as $key => $value) {
     107        $this->store_node($value);
     108      }
    74109  }
    75110
    76111  function store() {
     112    global $Database;
    77113    $Database->query("DELETE FROM hosts_topology;");
    78     store_node($rootNode);
    79   }
    80 
    81   function store_node($node) {
    82     $Database->query("INSERT INTO hosts_topology (host, depth, pos, first, last) VALUES (".$node->index.','.$node->level.','.$node->pos.','.$node->getFirst()->pos.','.$node->getLast()->pos.");");
    83   }
    84 
    85 // === Zpětné vyvážení stromu do hloubky =======================================
    86 function balance($id, $level, &$vlast, &$vleft, &$vpred, &$vfirst, &$vnext, &$tbound, &$width, $limit)
    87 {
    88   global $debug, $bbound;
    89  
    90   if(!array_key_exists($id, $vfirst)) $vfirst[$id] = 0;
    91   if($i = $vfirst[$id])
    92   {
    93     //if ($debug==2) echo $id.':'.@$i.','.@$vpred[$i].'-'.@$vleft[@$vpred[$i]]."\n";
    94     if (($vlast[$id] > 0) && ($vleft[$id] > $vleft[$vlast[$id]]))
    95     {
    96       $diff=$vleft[$id]-$vleft[$vlast[$id]];
    97       $i=$vfirst[$id];
    98       if ($vleft[$id] >= $tbound[$level])
    99       {
    100         $tbound[$level] = $vleft[$id] + 2;
    101         if ($vleft[$id] > $width) $width = $vleft[$id];
    102       }
    103     } else {
    104       $diff=0;
    105       if ($vpred[$i]&&($vleft[$i]<=$vleft[$vpred[$i]]))
    106       {
    107         $diff=$vleft[$i]-$vleft[$vpred[$i]]+2;
    108       } else $i = 0;
     114    $this->store_node($this->rootNode);
     115  }
     116
     117  function left_align($node) {
     118    $node->pos = $this->border[$node->level];
     119    $this->border[$node->level]++;
     120    if (count($node->children)>0) {
     121      if ($this->border[$node->level +1]>=$this->border[$node->level]) {
     122        $node->pos = $this->border[$node->level+1];
     123        $this->setborder($node->level, $this->border[$node->level+1]+1);
     124      }
     125      foreach($node->children as $key => $value) {
     126        if ($key == count($node->children)-1) {
     127          if($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
     128        }
     129        $this->left_align($value);
     130        if ($key == 0) {
     131          if($this->border[$node->level] <= $this->border[$node->level+1]) {
     132            $node->pos = $this->border[$node->level+1]-1;
     133            $this->setborder($node->level, $this->border[$node->level+1]);
     134          }
     135        }
     136      }
    109137    }
    110     while ($i>0)
    111     {
    112       $vleft[$i]+=$diff;
    113       $limit = balance($i,$level+1, $vlast,$vleft,$vpred, $vfirst,$vnext,$tbound, $width, $limit) + 2;
    114       if(!array_key_exists($i, $vnext)) $vnext[$i] = 0;
    115       $i = $vnext[$i];
     138  }
     139
     140  function reorder($node) {
     141    $node->pos = $this->border[$node->level];
     142    $this->border[$node->level]++;
     143    $order = array(); // Seznam změněných indexů
     144    if ($node->forkcnt>1) {
     145      $preborder = $this->border;
     146      $premax = $this->maxborder;
     147      $bestmax = 0; // Nejmenší rozměr
     148      $bestfit = 0; // Index nejvhodnějšího kandidáta
     149      $forkmap = array(); // Seznam indexů vydličkových potomků
     150      $target = 0; // Index cílového uzlu
     151      $lastindex = 0; // Index poslední vydličky
     152      foreach($node->children as $key => $value) {
     153        if (count($value->children)>0) {
     154          array_push($forkmap,$value);
     155          $order[$value->index]=0;
     156          $lastindex = $value->index;
     157        }
     158      }
     159      if ($node->forkcnt > 0) echo $node->index.':'.$node->forkcnt."\n";
     160      for($i=0;$i<$node->forkcnt-1;$i++) {
     161        for($j=0;$j<count($forkmap);$j++) {
     162          $this->border = $preborder;
     163          $this->maxborder = $premax;
     164          $k = 0; // index zpracovávané vydličky
     165          foreach($node->children as $key => $value) {
     166            if (count($value->children)>0) {
     167              if ($order[$value->index]) {
     168                $value = $order[$value->index];
     169              } else {
     170                if ($k > 0) {
     171                  if ($k < $j) { $value = $forkmap[$k-1]; } else  $value = $forkmap[$k];
     172                } else {
     173                  $target = $value->index;
     174                  $value = $forkmap[$j];
     175                }
     176                $k++;
     177              }
     178            }
     179            if ($key == count($node->children)-1) {
     180              if($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
     181            }
     182            $this->left_align($value);
     183            if ($key == 0) {
     184              if($this->border[$node->level] <= $this->border[$node->level+1]) {
     185                $node->pos = $this->border[$node->level+1]-1;
     186                $this->setborder($node->level, $this->border[$node->level+1]);
     187              }
     188            }
     189          }
     190          if (($j==0) || ($this->maxborder < $bestmax)) {
     191            $bestmax = $this->maxborder;
     192            $bestfit = $j;
     193          }
     194        }
     195        $order[$target]=$forkmap[$bestfit];
     196        echo 'ORDER: '.$target.' > '.$forkmap[$bestfit]->index."\n";
     197        array_splice($forkmap, $bestfit, 1);
     198      }
     199      $order[$lastindex]=$forkmap[0];
     200      echo 'ORDER: '.$lastindex.' > '.$forkmap[0]->index."\n";
     201      $this->order[$node->index] = $order;
     202      $this->border = $preborder;
     203      $this->maxborder = $premax;
    116204    }
     205    if (count($node->children)>0) {
     206      if ($this->border[$node->level +1]>=$this->border[$node->level]) {
     207        $node->pos = $this->border[$node->level+1];
     208        $this->setborder($node->level, $this->border[$node->level+1]+1);
     209      }
     210      foreach($node->children as $key => $value) {
     211        if ((count($value->children)>0) && count($order)>0) {
     212          echo $node->index.' '.$value->index."\n";
     213          $value = $order[$value->index];
     214        }
     215        if ($key == count($node->children)-1) {
     216          if($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
     217        }
     218        $this->reorder($value);
     219        if ($key == 0) {
     220          if($this->border[$node->level] <= $this->border[$node->level+1]) {
     221            $node->pos = $this->border[$node->level+1]-1;
     222            $this->setborder($node->level, $this->border[$node->level+1]);
     223          }
     224        }
     225      }
     226    }
     227  }
     228
     229  function setborder($level, $value) {
     230    if ($value > $this->maxborder) $this->maxborder = $value;
     231    $this->border[$level] = $value;
    117232  }
    118233}
    119234
    120 // === Generování rovinné stromové struktury ===================================
    121 function gentree($mode)                         // depth-first algorithm
    122 {                       
    123   global $debug, $TopHostName, $Database;
    124  
    125   // --- Inicializace ----------------------------------------------------------
    126   $tbound = array();                               // Hranice pozic jednotlivých úrovní
    127   $tranger = array();                              // Hranicni prvek
    128   $position = array();                             // Pozice aktuálního prvku na dané úrovni
    129   $vfirst = array();                               // První potomek prvku
    130   $vlast = array();                                // Poslední potomek prvku
    131   $vnext = array();                                // Následující sourozenec
    132   $vleft = array();                                // Pozice prvku zleva
    133   $vtop = array();                                 // Pozice prvku shora
    134   $vpred = array();                                // Vedlejsi prvek na řádku
    135  
    136   $index = 0;                                    // Index aktuálního prvku
    137   $curr = 0;                                     // Aktuální prvek
    138   $level = 0;                                    // Aktuální úroveň hloubky ve stromu
    139   $width = 0;                                    // Šířka stromu
    140   $height = 0;                                   // Hloubka stromu
    141 
    142   $parent[$level] = 0;                             // Rodič dané úrovně
    143   $position[$level] = 0;                           // Aktuální pozice prvku na dané úrovni
    144   $count[$level] = 0;                              // Počet prvků na dané úrovni
    145  
    146   $maxindex = 0;
    147   $tbound[$level] = 0;
    148   $tranger[$level] = 0;
    149    
    150   // --- Hlavní cyklus ---------------------------------------------------------
    151   do
    152   {
    153   // --- Proveď databázový dotaz -----------------------------------------------
    154     $query = 'SELECT * FROM hosts WHERE used=1 AND ';
    155     if ($level == 0)
    156     {
    157       $query .= 'name = "'.$TopHostName.'" ORDER BY id';
    158     } else
    159     {
    160       $query .= ' parent = '.$parent[$level].' ORDER BY id';
    161     }
    162     if ($mode) $query.=' DESC';
    163     $query .= ' LIMIT '.$position[$level].',1';
    164     //echo($query.'<br>');
    165     $DbResult = $Database->query($query);
    166     $item = $DbResult->fetch_array();
    167     //print_r($item);
    168     if($item)
    169     {
    170   // --- Zpracování položky z DB -----------------------------------------------
    171       if($position[$level] > 0)
    172       {
    173         $vnext[$curr] = $item['id']; // Neprvní položka, nastav předchozí
    174       }
    175       $curr = $item['id'];
    176       if ($curr > $maxindex) $maxindex = $curr;
    177       if ($position[$level] == 0) $vfirst[$parent[$level]]=$curr; // První položka, nastav první
    178       $vlast[$parent[$level]] = $curr;
    179       $vtop[$curr] = $level;
    180       if(!array_key_exists($level, $tbound)) $tbound[$level] = 0;
    181       $vleft[$curr] = $tbound[$level];
    182       if(!array_key_exists($level, $tranger)) $tranger[$level] = 0;
    183       $vpred[$curr] = $tranger[$level];
    184       $tranger[$level] = $curr;
    185       if (($debug == 3) && ($level == 8)) echo $curr.',';
    186       $position[$level]++;
    187       $count[$level]++;
    188   // --- Zjisti existenci potomků ----------------------------------------------
    189       $DbResult = $Database->query("SELECT COUNT(*) FROM hosts WHERE used=1 AND parent = ".$curr);
    190       $childcnt = $DbResult->fetch_array();
    191       if ($childcnt[0] > 0)
    192       {   
    193         // Uzelový vrchol
    194         if(array_key_exists($level + 1, $tbound))                 
    195           if($tbound[$level + 1] > $vleft[$curr]) $vleft[$curr] = $tbound[$level + 1];
    196       }
    197       $tbound[$level] = $vleft[$curr] + 2;
    198       if ($vleft[$curr] > $width) $width = $vleft[$curr];
    199       if ($childcnt[0] > 0)
    200       {
    201         $level++;
    202         if ($level > $height) $height = $level;
    203         $parent[$level] = $curr;
    204         $position[$level] = 0;
    205         $count[$level] = 0;
    206       } else $index++;                            // Listový vrchol
    207     } else
    208     {
    209   // --- Zarovnávání prvků kvůli vzhledu
    210       if(!array_key_exists($vfirst[$parent[$level]], $vleft)) $vleft[$vfirst[$parent[$level]]] = 0;
    211       if(!array_key_exists($parent[$level], $vleft)) $vleft[$parent[$level]] = 0;
    212       if ($vleft[$vfirst[$parent[$level]]] > $vleft[$parent[$level]])
    213       {
    214         $vleft[$parent[$level]] = $vleft[$vfirst[$parent[$level]]];
    215         if ($vleft[$parent[$level]]+2>$tbound[$level-1]) $tbound[$level-1] = $vleft[$parent[$level]]+2;
    216       }
    217       balance($parent[$level],$level, $vlast,$vleft,$vpred,$vfirst,$vnext,$tbound, $width, 0);
    218       if ($position[$level]==1)
    219       {
    220         $vleft[$vfirst[$parent[$level]]] = $vleft[$parent[$level]];
    221       }
    222       $level--;
    223       if(!array_key_exists($level, $parent)) $parent[$level] = 0;
    224       if(!array_key_exists($parent[$level], $vlast)) $vlast[$parent[$level]] = 0;
    225       $curr = $vlast[$parent[$level]];
    226      
    227       if(!array_key_exists($level, $tbound)) $tbound[$level] = 0;
    228       if(!array_key_exists($level + 1, $tbound)) $tbound[$level + 1] = 0;
    229       if($tbound[$level] > $tbound[$level + 1]) $tbound[$level + 1] = $tbound[$level];
    230     }
    231   } while($level >= 0);
    232   $data = compact('tbound', 'count', 'tbound', 'vfirst', 'vlast', 'vtop', 'vleft', 'height', 'width', 'index', 'maxindex');
    233   return($data);
    234 };
    235 
    236 // === Vytvoř stromy a ulož výsledek do databáze ===============================
    237 $Database->query("DELETE FROM hosts_topology;");
    238 extract(gentree(0));
    239 // exit();
    240 $data = gentree(1);
    241 $datawidth = $data['width'];
    242 for($i=0; $i <= $maxindex; $i++)
    243 {
    244   if(!array_key_exists($i, $vleft)) $vleft[$i] = 0;
    245   if(!array_key_exists($i, $data['vleft'])) $data['vleft'][$i] = 0;
    246   if(!array_key_exists($i, $vtop)) $vtop[$i] = 0;
    247   if(!array_key_exists($i, $vfirst)) $vfirst[$i] = 0;
    248   if(!array_key_exists($i, $vlast)) $vlast[$i] = 0;
    249   if(!array_key_exists($vfirst[$i], $data['vleft'])) $data['vleft'][$vfirst[$i]] = 0;
    250   if(!array_key_exists($vlast[$i], $data['vleft'])) $data['vleft'][$vlast[$i]] = 0;
    251 //  $vleft[$i] = ($vleft[$i]*2 + ($datawidth - $data['vleft'][$i]));
    252   if($vfirst[$i] > 0) {
    253     $first = (($vleft[$vfirst[$i]] + ($datawidth - $data['vleft'][$vfirst[$i]]))/2);
    254     $last = (($vleft[$vlast[$i]] + ($datawidth - $data['vleft'][$vlast[$i]]))/2);
    255   } else {
    256     $first = -1;
    257     $last = -1;
    258   }
    259  
    260   $Database->query("INSERT INTO hosts_topology (host, depth, pos, first, last) VALUES (".$i.','.$vtop[$i].','.(($vleft[$i] + ($datawidth - $data['vleft'][$i]))/2).','.$first.','.$last.");");
    261 }
     235// Hlavní smyčka programu
     236$mytree = new treegen();
     237$mytree->populate();
     238//$mytree->left_align($mytree->rootNode);
     239$mytree->reorder($mytree->rootNode);
     240$mytree->store();
    262241
    263242echo('Topologie byla vygenerovana.'); ?>
Note: See TracChangeset for help on using the changeset viewer.