Aggregate Code Coverage for all tests
1 : <?php 2 : /** 3 : * PEAR2_Pyrus_DirectedGraph 4 : * 5 : * PHP version 5 6 : * 7 : * @category PEAR2 8 : * @package PEAR2_Pyrus 9 : * @author Greg Beaver <cellog@php.net> 10 : * @copyright 2008 The PEAR Group 11 : * @license http://www.opensource.org/licenses/bsd-license.php New BSD License 12 : * @version SVN: $Id$ 13 : * @link http://svn.pear.php.net/wsvn/PEARSVN/Pyrus/ 14 : */ 15 : 16 : /** 17 : * Implements a graph data type, used for topological sorting of packages. 18 : * 19 : * This structure allows us to sort dependencies into the correct order for installation. 20 : * Iteration uses a depth-first search to perform a topological sort. 21 : * 22 : * @category PEAR2 23 : * @package PEAR2_Pyrus 24 : * @author Greg Beaver <cellog@php.net> 25 : * @copyright 2008 The PEAR Group 26 : * @license http://www.opensource.org/licenses/bsd-license.php New BSD License 27 : * @link http://svn.pear.php.net/wsvn/PEARSVN/Pyrus/ 28 : */ 29 1 : class PEAR2_Pyrus_DirectedGraph implements Iterator 30 : { 31 : const WHITE = 0; 32 : const GRAY = 1; 33 : const BLACK = 2; 34 : protected $vertices = array(); 35 : /** 36 : * Map data to abstract vertex 37 : * 38 : * @var array 39 : */ 40 : protected $map = array(); 41 : /** 42 : * Topologically sorted vertices 43 : * @var array 44 : */ 45 : protected $blackVertices = array(); 46 : 47 : /** 48 : * Add a data vertex 49 : * 50 : * @param object $data 51 : * @return PEAR2_Pyrus_DirectedGraph_Vertex 52 : */ 53 : function add($data) 54 : { 55 1 : $vertex = new PEAR2_Pyrus_DirectedGraph_Vertex($data); 56 1 : $this->vertices[spl_object_hash($vertex)] = $vertex; 57 1 : $this->map[spl_object_hash($data)] = spl_object_hash($vertex); 58 1 : return $vertex; 59 : } 60 : 61 : /** 62 : * Connect two vertices in a directed graph 63 : * 64 : * This can be used with a fluent interface 65 : * @param object|PEAR2_Pyrus_DirectedGraph_Vertex $from 66 : * @param object|PEAR2_Pyrus_DirectedGraph_Vertex $to 67 : * @return PEAR2_Pyrus_DirectedGraph 68 : */ 69 : function connect($from, $to) 70 : { 71 : if ($from instanceof PEAR2_Pyrus_DirectedGraph_Vertex) { 72 : $a = spl_object_hash($from); 73 : } else { 74 : if (!isset($this->map[spl_object_hash($from)])) { 75 : $a = $this->add($from); 76 : } else { 77 : $a = $this->vertices[$this->map[spl_object_hash($from)]]; 78 : } 79 : } 80 : if ($to instanceof PEAR2_Pyrus_DirectedGraph_Vertex) { 81 : $b = spl_object_hash($to); 82 : } else { 83 : if (!isset($this->map[spl_object_hash($to)])) { 84 : $b = $this->add($to); 85 : } else { 86 : $b = $this->vertices[$this->map[spl_object_hash($to)]]; 87 : } 88 : } 89 : $this->vertices[spl_object_hash($a)]->connect($b); 90 : return $this; 91 : } 92 : 93 : function current() 94 : { 95 1 : return current($this->blackVertices)->data; 96 : } 97 : 98 : function next() 99 : { 100 1 : return next($this->blackVertices); 101 : } 102 : 103 : function key() 104 : { 105 : return key($this->blackVertices); 106 : } 107 : 108 : function valid() 109 : { 110 1 : return current($this->blackVertices); 111 : } 112 : 113 : function rewind() 114 : { 115 1 : $this->topologicalSort(); 116 1 : } 117 : 118 : /** 119 : * Sort the vertices by their connections 120 : */ 121 : function topologicalSort() 122 : { 123 1 : $this->blackVertices = array(); 124 1 : if (!count($this->vertices)) { 125 : return; 126 : } 127 1 : foreach ($this->vertices as $vertex) { 128 1 : $vertex->color(self::WHITE); 129 1 : } 130 1 : while (count($this->blackVertices) < count($this->vertices)) { 131 : // select a vertex to start 132 1 : foreach ($this->vertices as $vertex) { 133 1 : if ($vertex->color() == self::BLACK) { 134 : // already sorted 135 : continue; 136 : } 137 1 : break; 138 1 : } 139 : do { 140 : // this vertex has been discovered 141 1 : $vertex->color(self::GRAY); 142 1 : if (!count($vertex)) { 143 : // no adjacent edges 144 1 : $this->blackVertices[] = $vertex; 145 1 : $vertex->color(self::BLACK); 146 1 : continue 2; 147 : } 148 : $black = true; 149 : // iterate over adjacent vertices to find a white vertex 150 : foreach ($vertex as $edge) { 151 : if ($edge->color() == self::BLACK) { 152 : continue; 153 : } 154 : if (!count($edge)) { 155 : // no adjacent undiscovered vertices, we found a black one 156 : $edge->color(self::BLACK); 157 : $this->blackVertices[] = $edge; 158 : continue; 159 : } 160 : $black = false; 161 : $edge->color(self::GRAY); 162 : } 163 : if ($black) { 164 : // found a new vertex 165 : $this->blackVertices[] = $vertex; 166 : $vertex->color(self::BLACK); 167 : } else { 168 : foreach ($vertex as $edge) { 169 : if ($edge->color() == self::BLACK) { 170 : continue; 171 : } 172 : $vertex = $edge; 173 : break; 174 : } 175 : } 176 : } while (!$black); 177 : } 178 1 : } 179 1 : }