crm.fsf.org/20131203/files/sites/all/modules-new/civicrm/packages/Structures/Graph/Manipulator/TopologicalSorter.php

   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 ?>