[Sommaire] [Imprimer]

   1  <?php
   2  /* vim: set expandtab tabstop=4 shiftwidth=4 foldmethod=marker: */
   3  // +-----------------------------------------------------------------------------+
   4  // | Copyright (c) 2003 Sérgio Gonçalves Carvalho                                |
   5  // +-----------------------------------------------------------------------------+
   6  // | This file is part of Structures_Graph.                                      |
   7  // |                                                                             |
   8  // | Structures_Graph is free software; you can redistribute it and/or modify    |
   9  // | it under the terms of the GNU Lesser General Public License as published by |
  10  // | the Free Software Foundation; either version 2.1 of the License, or         |
  11  // | (at your option) any later version.                                         |
  12  // |                                                                             |
  13  // | Structures_Graph is distributed in the hope that it will be useful,         |
  14  // | but WITHOUT ANY WARRANTY; without even the implied warranty of              |
  15  // | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the               |
  16  // | GNU Lesser General Public License for more details.                         |
  17  // |                                                                             |
  18  // | You should have received a copy of the GNU Lesser General Public License    |
  19  // | along with Structures_Graph; if not, write to the Free Software             |
  20  // | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA                    |
  21  // | 02111-1307 USA                                                              |
  22  // +-----------------------------------------------------------------------------+
  23  // | Author: Sérgio Carvalho <sergio.carvalho@portugalmail.com>                  |
  24  // +-----------------------------------------------------------------------------+
  25  //
  26  /**
  27   * This file contains the definition of the Structures_Graph_Manipulator_TopologicalSorter class.
  28   * 
  29   * @see Structures_Graph_Manipulator_TopologicalSorter
  30   * @package Structures_Graph
  31   */
  32  
  33  /* dependencies {{{ */
  34  /** */
  35  require_once  'PEAR.php';
  36  /** */
  37  require_once  'Structures/Graph.php';
  38  /** */
  39  require_once  'Structures/Graph/Node.php';
  40  /** */
  41  require_once  'Structures/Graph/Manipulator/AcyclicTest.php';
  42  /* }}} */
  43  
  44  /* class Structures_Graph_Manipulator_TopologicalSorter {{{ */
  45  /**
  46   * The Structures_Graph_Manipulator_TopologicalSorter is a manipulator 
  47   * which is able to return the set of nodes in a graph, sorted by topological 
  48   * order.
  49   *
  50   * A graph may only be sorted topologically iff it's a DAG. You can test it
  51   * with the Structures_Graph_Manipulator_AcyclicTest.
  52   * 
  53   * @author        Sérgio Carvalho <sergio.carvalho@portugalmail.com> 
  54   * @copyright    (c) 2004 by Sérgio Carvalho
  55   * @see     Structures_Graph_Manipulator_AcyclicTest
  56   * @package Structures_Graph
  57   */
  58  class Structures_Graph_Manipulator_TopologicalSorter {
  59      /* _nonVisitedInDegree {{{ */
  60      /**
  61      *
  62      * This is a variant of Structures_Graph::inDegree which does 
  63      * not count nodes marked as visited.
  64      *
  65      * @access   private
  66      * @return    integer     Number of non-visited nodes that link to this one
  67      */
  68      function _nonVisitedInDegree(&$node) {
  69          $result = 0;
  70          $graphNodes =& $node->_graph->getNodes();
  71          foreach (array_keys($graphNodes) as $key) {
  72              if ((!$graphNodes[$key]->getMetadata('topological-sort-visited')) && $graphNodes[$key]->connectsTo($node)) $result++;
  73          }
  74          return $result;
  75          
  76      }
  77      /* }}} */
  78  
  79      /* _sort {{{ */
  80      /**
  81      * @access   private
  82      */
  83      function _sort(&$graph) {
  84          // Mark every node as not visited
  85          $nodes =& $graph->getNodes();
  86          $nodeKeys = array_keys($nodes);
  87          $refGenerator = array();
  88          foreach($nodeKeys as $key) {
  89              $refGenerator[] = false;
  90              $nodes[$key]->setMetadata('topological-sort-visited', $refGenerator[sizeof($refGenerator) - 1]);
  91          }
  92  
  93          // Iteratively peel off leaf nodes
  94          $topologicalLevel = 0;
  95          do {
  96              // Find out which nodes are leafs (excluding visited nodes)
  97              $leafNodes = array();
  98              foreach($nodeKeys as $key) {
  99                  if ((!$nodes[$key]->getMetadata('topological-sort-visited')) && Structures_Graph_Manipulator_TopologicalSorter::_nonVisitedInDegree($nodes[$key]) == 0) {
 100                      $leafNodes[] =& $nodes[$key];
 101                  }
 102              }
 103              // Mark leafs as visited
 104              $refGenerator[] = $topologicalLevel;
 105              for ($i=sizeof($leafNodes) - 1; $i>=0; $i--) {
 106                  $visited =& $leafNodes[$i]->getMetadata('topological-sort-visited');
 107                  $visited = true;
 108                  $leafNodes[$i]->setMetadata('topological-sort-visited', $visited);
 109                  $leafNodes[$i]->setMetadata('topological-sort-level', $refGenerator[sizeof($refGenerator) - 1]);
 110              }
 111              $topologicalLevel++;
 112          } while (sizeof($leafNodes) > 0);
 113  
 114          // Cleanup visited marks
 115          foreach($nodeKeys as $key) $nodes[$key]->unsetMetadata('topological-sort-visited');
 116      }
 117      /* }}} */
 118  
 119      /* sort {{{ */
 120      /**
 121      *
 122      * sort returns the graph's nodes, sorted by topological order. 
 123      * 
 124      * The result is an array with 
 125      * as many entries as topological levels. Each entry in this array is an array of nodes within
 126      * the given topological level.
 127      *
 128      * @return    array     The graph's nodes, sorted by topological order.
 129      * @access    public
 130      */
 131      function sort(&$graph) {
 132          // We only sort graphs
 133          if (!is_a($graph, 'Structures_Graph')) return Pear::raiseError('Structures_Graph_Manipulator_TopologicalSorter::sort received an object that is not a Structures_Graph', STRUCTURES_GRAPH_ERROR_GENERIC);
 134          if (!Structures_Graph_Manipulator_AcyclicTest::isAcyclic($graph)) return Pear::raiseError('Structures_Graph_Manipulator_TopologicalSorter::sort received an graph that has cycles', STRUCTURES_GRAPH_ERROR_GENERIC);
 135  
 136          Structures_Graph_Manipulator_TopologicalSorter::_sort($graph);
 137          $result = array();
 138  
 139          // Fill out result array
 140          $nodes =& $graph->getNodes();
 141          $nodeKeys = array_keys($nodes);
 142          foreach($nodeKeys as $key) {
 143              if (!array_key_exists($nodes[$key]->getMetadata('topological-sort-level'), $result)) $result[$nodes[$key]->getMetadata('topological-sort-level')] = array();
 144              $result[$nodes[$key]->getMetadata('topological-sort-level')][] =& $nodes[$key];
 145              $nodes[$key]->unsetMetadata('topological-sort-level');
 146          }
 147  
 148          return $result;
 149      }
 150      /* }}} */
 151  }
 152  /* }}} */
 153  ?>