[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_AcyclicTest graph manipulator.
  28   * 
  29   * @see Structures_Graph_Manipulator_AcyclicTest
  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  
  42  /* class Structures_Graph_Manipulator_AcyclicTest {{{ */
  43  /**
  44   * The Structures_Graph_Manipulator_AcyclicTest is a graph manipulator
  45   * which tests whether a graph contains a cycle. 
  46   * 
  47   * The definition of an acyclic graph used in this manipulator is that of a 
  48   * DAG. The graph must be directed, or else it is considered cyclic, even when 
  49   * there are no arcs.
  50   *
  51   * @author        Sérgio Carvalho <sergio.carvalho@portugalmail.com> 
  52   * @copyright    (c) 2004 by Sérgio Carvalho
  53   * @package Structures_Graph
  54   */
  55  class Structures_Graph_Manipulator_AcyclicTest {
  56      /* _nonVisitedInDegree {{{ */
  57      /**
  58      *
  59      * This is a variant of Structures_Graph::inDegree which does 
  60      * not count nodes marked as visited.
  61      *
  62      * @access   private
  63      * @return    integer     Number of non-visited nodes that link to this one
  64      */
  65      function _nonVisitedInDegree(&$node) {
  66          $result = 0;
  67          $graphNodes =& $node->_graph->getNodes();
  68          foreach (array_keys($graphNodes) as $key) {
  69              if ((!$graphNodes[$key]->getMetadata('acyclic-test-visited')) && $graphNodes[$key]->connectsTo($node)) $result++;
  70          }
  71          return $result;
  72          
  73      }
  74      /* }}} */
  75  
  76      /* _isAcyclic {{{ */
  77      /**
  78      * @access   private
  79      */
  80      function _isAcyclic(&$graph) {
  81          // Mark every node as not visited
  82          $nodes =& $graph->getNodes();
  83          $nodeKeys = array_keys($nodes);
  84          $refGenerator = array();
  85          foreach($nodeKeys as $key) {
  86              $refGenerator[] = false;
  87              $nodes[$key]->setMetadata('acyclic-test-visited', $refGenerator[sizeof($refGenerator) - 1]);
  88          }
  89  
  90          // Iteratively peel off leaf nodes
  91          do {
  92              // Find out which nodes are leafs (excluding visited nodes)
  93              $leafNodes = array();
  94              foreach($nodeKeys as $key) {
  95                  if ((!$nodes[$key]->getMetadata('acyclic-test-visited')) && Structures_Graph_Manipulator_AcyclicTest::_nonVisitedInDegree($nodes[$key]) == 0) {
  96                      $leafNodes[] =& $nodes[$key];
  97                  }
  98              }
  99              // Mark leafs as visited
 100              for ($i=sizeof($leafNodes) - 1; $i>=0; $i--) {
 101                  $visited =& $leafNodes[$i]->getMetadata('acyclic-test-visited');
 102                  $visited = true;
 103                  $leafNodes[$i]->setMetadata('acyclic-test-visited', $visited);
 104              }
 105          } while (sizeof($leafNodes) > 0);
 106  
 107          // If graph is a DAG, there should be no non-visited nodes. Let's try to prove otherwise
 108          $result = true;
 109          foreach($nodeKeys as $key) if (!$nodes[$key]->getMetadata('acyclic-test-visited')) $result = false;
 110          
 111          // Cleanup visited marks
 112          foreach($nodeKeys as $key) $nodes[$key]->unsetMetadata('acyclic-test-visited');
 113  
 114          return $result;
 115      }
 116      /* }}} */
 117  
 118      /* isAcyclic {{{ */
 119      /**
 120      *
 121      * isAcyclic returns true if a graph contains no cycles, false otherwise.
 122      *
 123      * @return    boolean     true iff graph is acyclic
 124      * @access    public
 125      */
 126      function isAcyclic(&$graph) {
 127          // We only test graphs
 128          if (!is_a($graph, 'Structures_Graph')) return Pear::raiseError('Structures_Graph_Manipulator_AcyclicTest::isAcyclic received an object that is not a Structures_Graph', STRUCTURES_GRAPH_ERROR_GENERIC);
 129          if (!$graph->isDirected()) return false; // Only directed graphs may be acyclic
 130  
 131          return Structures_Graph_Manipulator_AcyclicTest::_isAcyclic($graph);
 132      }
 133      /* }}} */
 134  }
 135  /* }}} */
 136  ?>