Ignore:
Timestamp:
May 31, 2009, 8:48:51 PM (15 years ago)
Author:
hajdam
Message:

Úprava zobrazení topologie

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/is/topologie-gen.php

    r84 r222  
    11<?php
    2  // Skript pro generování grafu stromové struktury sítě do PNG obrázku
    3 include('../global2.php');
     2// Vertically-balanced Tree Topology Generator
     3// Author: Miroslav Hajda hajdam@users.sf.net
     4
     5include('../global.php');
    46global $Database, $debug;
    57
    68if(array_key_exists('debug', $_GET)) $debug = $_GET['debug'];
    79else $debug = 0;
    8 $debug = 0;
    9 
    10 class treeitem {
     10//$debug = 0;
     11
     12class TreeItem {
    1113  /** Index prvku v databazi */
    1214  var $index = 0;
    13 
    1415  /** Pozice prvku zleva */
    1516  var $pos = 0;
    16 
    1717  /** Pozice prvku zprava */
    1818  var $rpos = 0;
    19 
    2019  /** Pozice prvku shora */
    2120  var $level = 0;
    22 
    2321  /** Počet potomků s potomky */
    2422  var $forkcnt = 0;
    25 
    2623  /** Pole potomků */
    2724  var $children = array();
    28 
    2925  /** Předek */
    3026  var $parentItem;
    31 
    3227  /** Změna pořadí prvků */
    3328  var $order = array();
     
    5247}
    5348
    54 class treegen {
     49class TreeGen {
    5550
    5651  /** Kořenový uzel */
     
    6661  function populate() {
    6762    global $Database;
    68     $TopHostName = 'NIX-ROUTER';
     63    $TopHostName = 'nix-router';
    6964    // rodičovský uzel
    7065    $parentNode = null;
     
    7469    $level = 0;
    7570    $this->border[0]=0;
     71    $mark = array();
    7672
    7773    do {
    78       $query = 'SELECT * FROM hosts WHERE used=1 AND ';
    7974      if ($level == 0) {
    80         $query .= 'name = "'.$TopHostName.'" ORDER BY id';
    81         $query .= ' LIMIT 0,1';
     75        $query = 'SELECT dev.id AS id FROM NetworkDevice dev WHERE dev.name = "'.$TopHostName.'" LIMIT 0,1';
    8276      } else {
    83         $query .= ' parent = '.$parentNode->index.' ORDER BY id';
     77        $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 ';
     78        $query .= ' dev.id = '.$parentNode->index.' ORDER BY id';
    8479        $query .= ' LIMIT '.count($parentNode->children).',1';
    8580      }
    8681      $DbResult = $Database->query($query);
    8782      $item = $DbResult->fetch_array();
    88       if($item) {
    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;
     83      if ($item) {
     84//        echo $item['id'].'<br/>';
     85//        flush();
     86        if (!isset($mark[$item['id']])) {
     87          $mark[$item['id']] = 1;
     88          $currentNode = new TreeItem();
     89          $currentNode->index = $item['id'];
     90          $currentNode->level = $level;
     91          $currentNode->parentItem = $parentNode;
     92          if ($level==0) {
     93            $this->rootNode = $currentNode;
     94          } else {
     95            if ($level>1 && count($parentNode->children)==0) $parentNode->parentItem->forkcnt++;
     96            array_push($parentNode->children,$currentNode);
     97          }
     98          $parentNode = $currentNode;
     99          $level++;
     100          $this->border[$level] = 0;
     101        }
    102102      } else {
    103103        $currentNode = $parentNode;
     
    109109
    110110  function calc_pos($node) {
    111     if ($this->mode) {
     111    if ($this->mode > 1) {
    112112      return 1.5 + $this->maxborder-$node->rpos+$node->pos;
    113113    } else return $node->pos;
    114114  }
    115115
     116  /** Store specific tree node to DB */
    116117  function store_node($node) {
    117118      global $Database;
     
    126127  }
    127128
     129  /** Store all nodes of tree to DB */
    128130  function store() {
    129131    global $Database;
     
    132134  }
    133135
     136  /** Build most left tree on node and all subnodes on given border */
    134137  function left_align($node) {
    135138    $node->pos = $this->border[$node->level];
     
    155158  }
    156159
     160  /** Build most right tree on node and all subnodes on given border */
    157161  function right_align($node) {
    158     $this->mode = 1;
     162    $this->mode = 2;
    159163    $node->rpos = $this->border[$node->level];
    160164    $this->border[$node->level]++;
     
    183187  }
    184188
     189
     190  /** Reset construction border **/
    185191  function reset_border() {
    186192    foreach($this->border as $key => $value) $this->border[$key] = 0;
     
    188194  }
    189195
    190   function reorder($node) {
     196  /** Heuristic reordering of fork nodes */
     197  function reorder_heur($node) {
    191198    global $debug;
    192199    $node->pos = $this->border[$node->level];
     
    277284  }
    278285
     286  /** Build most left tree on node and all subnodes on given border without leafs */
     287  function left_stub($node) {
     288    $node->pos = $this->border[$node->level];
     289    $this->border[$node->level]++;
     290    if (count($node->children)>0) {
     291      $stubborder = $this->border[$node->level +1] + count($node->children);
     292      if ($this->border[$node->level +1]>=$this->border[$node->level]) {
     293        $node->pos = $this->border[$node->level+1];
     294        $this->setborder($node->level, $this->border[$node->level+1]+1);
     295      }
     296      $forkcnt = 0; // Fork counter
     297      foreach($node->children as $key => $value) {
     298        if ($forkcnt == count($node->children)-1) {
     299          if($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
     300        }
     301        if (count($value->children)>0) {
     302          $this->left_stub($value);
     303          if ($forkcnt == 0) {
     304            if($this->border[$node->level] <= $this->border[$node->level+1]) {
     305              $node->pos = $this->border[$node->level+1]-1;
     306              $this->setborder($node->level, $this->border[$node->level+1]);
     307            }
     308          }
     309          $forkcnt++;
     310        }
     311      }
     312      if ($stubborder > $this->border[$node->level +1]) $this->setborder($node->level+1,$stubborder);
     313    }
     314  }
     315
     316  /** Full single level reordering */
     317  function reorder($node) {
     318    global $debug;
     319    $node->pos = $this->border[$node->level];
     320    $this->border[$node->level]++;
     321    $order = array(); // Seznam změněných indexů
     322    if ($node->forkcnt>1) {
     323      $preborder = $this->border;
     324      $premax = $this->maxborder;
     325      $bestmax = 0; // Nejmenší rozměr
     326      $bestfit = 0; // Index nejvhodnějšího kandidáta
     327      $forkmap = array(); // Seznam indexů vydličkových potomků
     328      $target = 0; // Index cílového uzlu
     329      $lastindex = 0; // Index poslední vydličky
     330      $fact = 1; // Faktoriál kombinací vydliček
     331      foreach($node->children as $key => $value) {
     332        if (count($value->children)>0) {
     333          if ($key>0) $fact = $fact * ($key+1);
     334          array_push($forkmap,$value);
     335          $order[$value->index]=0;
     336          $lastindex = $value->index;
     337        }
     338      }
     339      for($i=0;$i<$node->forkcnt-1;$i++) {
     340        for($j=0;$j<count($forkmap);$j++) {
     341          $this->border = $preborder;
     342          $this->maxborder = $premax;
     343          $k = 0; // index zpracovávané vydličky
     344          foreach($node->children as $key => $value) {
     345            if (count($value->children)>0) {
     346              if ($order[$value->index]) {
     347                $value = $order[$value->index];
     348              } else {
     349                if ($k > 0) {
     350                  if ($k < $j) { $value = $forkmap[$k-1]; } else  $value = $forkmap[$k];
     351                } else {
     352                  $target = $value->index;
     353                  $value = $forkmap[$j];
     354                }
     355                $k++;
     356              }
     357            }
     358            if ($key == count($node->children)-1) {
     359              if($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
     360            }
     361            $this->left_align($value);
     362            if ($key == 0) {
     363              if($this->border[$node->level] <= $this->border[$node->level+1]) {
     364                $node->pos = $this->border[$node->level+1]-1;
     365                $this->setborder($node->level, $this->border[$node->level+1]);
     366              }
     367            }
     368          }
     369          if (($j==0) || ($this->maxborder < $bestmax)) {
     370            $bestmax = $this->maxborder;
     371            $bestfit = $j;
     372          }
     373        }
     374        $order[$target]=$forkmap[$bestfit];
     375        if ($debug) echo 'ORDER: '.$target.' > '.$forkmap[$bestfit]->index."\n";
     376        array_splice($forkmap, $bestfit, 1);
     377      }
     378      $order[$lastindex]=$forkmap[0];
     379      if ($debug) echo 'ORDER: '.$lastindex.' > '.$forkmap[0]->index."\n";
     380      if ($debug) echo 'ORDERSTORE: '.$node->index."\n";
     381      $node->order = $order;
     382      $this->border = $preborder;
     383      $this->maxborder = $premax;
     384    }
     385    // Missing stub stuffing
     386    if (count($node->children)>0) {
     387      if ($this->border[$node->level +1]>=$this->border[$node->level]) {
     388        $node->pos = $this->border[$node->level+1];
     389        $this->setborder($node->level, $this->border[$node->level+1]+1);
     390      }
     391      foreach($node->children as $key => $value) {
     392        if ((count($value->children)>0) && count($order)>0) {
     393          $value = $order[$value->index];
     394        }
     395        if ($key == count($node->children)-1) {
     396          if($this->border[$node->level] > $this->border[$node->level+1]) $this->setborder($node->level+1, $this->border[$node->level]-1);
     397        }
     398        $this->reorder($value);
     399        if ($key == 0) {
     400          if($this->border[$node->level] <= $this->border[$node->level+1]) {
     401            $node->pos = $this->border[$node->level+1]-1;
     402            $this->setborder($node->level, $this->border[$node->level+1]);
     403          }
     404        }
     405      }
     406    }
     407  }
     408
    279409  function setborder($level, $value) {
    280410    if ($value > $this->maxborder) $this->maxborder = $value;
     
    283413}
    284414
    285 // Hlavní smyčka programu
    286 $mytree = new treegen();
     415// Generator Main Procedure
     416$mytree = new TreeGen();
    287417$mytree->populate();
    288 //$mytree->left_align($mytree->rootNode);
    289 $mytree->reorder($mytree->rootNode);
     418$mytree->left_align($mytree->rootNode);
     419//$mytree->reorder($mytree->rootNode);
     420//$mytree->left_stub($mytree->rootNode);
    290421$mytree->reset_border();
    291422$mytree->right_align($mytree->rootNode);
Note: See TracChangeset for help on using the changeset viewer.