home *** CD-ROM | disk | FTP | other *** search
/ Enter 2004 June / ENTER.ISO / files / xampp-win32-1.4.5-installer.exe / xampp / TopologicalSorter.php < prev    next >
Encoding:
PHP Script  |  2004-03-24  |  6.6 KB  |  158 lines
  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.         return $result;
  118.     }
  119.     /* }}} */
  120.  
  121.     /* sort {{{ */
  122.     /**
  123.     *
  124.     * sort returns the graph's nodes, sorted by topological order. 
  125.     * 
  126.     * The result is an array with 
  127.     * as many entries as topological levels. Each entry in this array is an array of nodes within
  128.     * the given topological level.
  129.     *
  130.     * @return    array     The graph's nodes, sorted by topological order.
  131.     * @access    public
  132.     */
  133.     function sort(&$graph) {
  134.         // We only sort graphs
  135.         if (!is_a($graph, 'Structures_Graph')) 
  136.             Pear::raiseError('Structures_Graph_Manipulator_TopologicalSorter::sort received an object that is not a Structures_Graph', STRUCTURES_GRAPH_ERROR_GENERIC);
  137.         if (!Structures_Graph_Manipulator_AcyclicTest::isAcyclic($graph))
  138.             Pear::raiseError('Structures_Graph_Manipulator_TopologicalSorter::sort received an graph that has cycles', STRUCTURES_GRAPH_ERROR_GENERIC);
  139.  
  140.         Structures_Graph_Manipulator_TopologicalSorter::_sort($graph);
  141.         $result = array();
  142.  
  143.         // Fill out result array
  144.         $nodes =& $graph->getNodes();
  145.         $nodeKeys = array_keys($nodes);
  146.         foreach($nodeKeys as $key) {
  147.             if (!array_key_exists($nodes[$key]->getMetadata('topological-sort-level'), $result)) $result[$nodes[$key]->getMetadata('topological-sort-level')] = array();
  148.             $result[$nodes[$key]->getMetadata('topological-sort-level')][] =& $nodes[$key];
  149.             $nodes[$key]->unsetMetadata('topological-sort-level');
  150.         }
  151.  
  152.         return $result;
  153.     }
  154.     /* }}} */
  155. }
  156. /* }}} */
  157. ?>
  158.