| Index: trunk/extensions/Validator/TopologicalSort.php |
| — | — | @@ -0,0 +1,147 @@ |
| | 2 | +<?php |
| | 3 | + |
| | 4 | +/** |
| | 5 | + * Sorts a series of dependency pairs in linear order. |
| | 6 | + * |
| | 7 | + * Based on http://blog.metafoundry.com/2007/09/topological-sort-in-php.html |
| | 8 | + * |
| | 9 | + * usage: |
| | 10 | + * $t = new TopologicalSort($dependency_pairs); |
| | 11 | + * $load_order = $t->tsort(); |
| | 12 | + * |
| | 13 | + * where dependency_pairs is in the form: |
| | 14 | + * $name => (depends on) $value |
| | 15 | + * |
| | 16 | + * @author Eddie Haber |
| | 17 | + * @author Jeroen De Dauw |
| | 18 | + * |
| | 19 | + * TODO: fix conventions further |
| | 20 | + * TODO: include/load class |
| | 21 | + * TODO: Use in revised version of Validator class |
| | 22 | + */ |
| | 23 | +class TopologicalSort { |
| | 24 | + var $nodes = array (); |
| | 25 | + |
| | 26 | + /** |
| | 27 | + * Dependency pairs are a list of arrays in the form |
| | 28 | + * $name => $val where $key must come before $val in load order. |
| | 29 | + */ |
| | 30 | + function TopologicalSort($dependencies = array(), $parse = false) { |
| | 31 | + if ($parse) { |
| | 32 | + $dependencies = $this->parseDependencyList ( $dependencies ); |
| | 33 | + } |
| | 34 | + |
| | 35 | + // turn pairs into double-linked node tree |
| | 36 | + foreach ( $dependencies as $key => $dpair ) { |
| | 37 | + list ( $module, $dependency ) = each ( $dpair ); |
| | 38 | + if ( !isset ( $this->nodes [$module] )) $this->nodes [$module] = new TSNode ( $module ); |
| | 39 | + if ( !isset ( $this->nodes [$dependency] )) $this->nodes [$dependency] = new TSNode ( $dependency ); |
| | 40 | + if ( !in_array ( $dependency, $this->nodes [$module]->children )) $this->nodes [$module]->children [] = $dependency; |
| | 41 | + if ( !in_array ( $module, $this->nodes [$dependency]->parents )) $this->nodes [$dependency]->parents [] = $module; |
| | 42 | + } |
| | 43 | + } |
| | 44 | + |
| | 45 | + /** |
| | 46 | + * Perform Topological Sort |
| | 47 | + * |
| | 48 | + * @param array $nodes optional array of node objects may be passed. |
| | 49 | + * Default is $this->nodes created in constructor. |
| | 50 | + * |
| | 51 | + * @return sorted array |
| | 52 | + */ |
| | 53 | + function tsort($nodes = array()) { |
| | 54 | + // use this->nodes if it is populated and no param passed |
| | 55 | + if (! @count ( $nodes ) && count ( $this->nodes )) { |
| | 56 | + $nodes = $this->nodes; |
| | 57 | + } |
| | 58 | + |
| | 59 | + |
| | 60 | + // get nodes without parents |
| | 61 | + $root_nodes = array_values ( $this->getRootNodes ( $nodes ) ); |
| | 62 | + |
| | 63 | + // begin algorithm |
| | 64 | + $sorted = array (); |
| | 65 | + while ( count ( $nodes ) > 0 ) { |
| | 66 | + // check for circular reference |
| | 67 | + if (count ( $root_nodes ) == 0) |
| | 68 | + return false; |
| | 69 | + |
| | 70 | + // remove this node from root_nodes |
| | 71 | + // and add it to the output |
| | 72 | + $n = array_pop ( $root_nodes ); |
| | 73 | + $sorted [] = $n->name; |
| | 74 | + |
| | 75 | + // for each of its children |
| | 76 | + // queue the new node finally remove the original |
| | 77 | + for($i = (count ( $n->children ) - 1); $i >= 0; $i --) { |
| | 78 | + $childnode = $n->children [$i]; |
| | 79 | + // remove the link from this node to its |
| | 80 | + // children ($nodes[$n->name]->children[$i]) AND |
| | 81 | + // remove the link from each child to this |
| | 82 | + // parent ($nodes[$childnode]->parents[?]) THEN |
| | 83 | + // remove this child from this node |
| | 84 | + unset ( $nodes [$n->name]->children [$i] ); |
| | 85 | + $parent_position = array_search ( $n->name, $nodes [$childnode]->parents ); |
| | 86 | + unset ( $nodes [$childnode]->parents [$parent_position] ); |
| | 87 | + // check if this child has other parents |
| | 88 | + // if not, add it to the root nodes list |
| | 89 | + if (! count ( $nodes [$childnode]->parents )) |
| | 90 | + array_push ( $root_nodes, $nodes [$childnode] ); |
| | 91 | + } |
| | 92 | + |
| | 93 | + // nodes.Remove(n); |
| | 94 | + unset ( $nodes [$n->name] ); |
| | 95 | + } |
| | 96 | + return $sorted; |
| | 97 | + } |
| | 98 | + |
| | 99 | + /** |
| | 100 | + * Returns a list of node objects that do not have parents |
| | 101 | + * |
| | 102 | + * @param array $nodes array of node objects |
| | 103 | + * |
| | 104 | + * @return array of node objects |
| | 105 | + */ |
| | 106 | + function getRootNodes($nodes) { |
| | 107 | + $output = array (); |
| | 108 | + foreach ( $nodes as $name => $node ) |
| | 109 | + if (! count ( $node->parents )) |
| | 110 | + $output [$name] = $node; |
| | 111 | + return $output; |
| | 112 | + } |
| | 113 | + |
| | 114 | + /** |
| | 115 | + * Parses an array of dependencies into an array of dependency pairs |
| | 116 | + * |
| | 117 | + * The array of dependencies would be in the form: |
| | 118 | + * $dependency_list = array( |
| | 119 | + * "name" => array("dependency1","dependency2","dependency3"), |
| | 120 | + * "name2" => array("dependencyA","dependencyB","dependencyC"), |
| | 121 | + * ...etc |
| | 122 | + * ); |
| | 123 | + * |
| | 124 | + * @param array $dlist Array of dependency pairs for use as parameter in tsort method |
| | 125 | + * @return array |
| | 126 | + */ |
| | 127 | + function parseDependencyList($dlist = array()) { |
| | 128 | + $output = array (); |
| | 129 | + foreach ( $dlist as $name => $dependencies ) |
| | 130 | + foreach ( $dependencies as $d ) |
| | 131 | + array_push ( $output, array ($d => $name ) ); |
| | 132 | + return $output; |
| | 133 | + } |
| | 134 | +} |
| | 135 | + |
| | 136 | +/** |
| | 137 | + * Node class for Topological Sort Class |
| | 138 | + * |
| | 139 | + */ |
| | 140 | +class TSNode { |
| | 141 | + var $name; |
| | 142 | + var $children = array(); |
| | 143 | + var $parents = array(); |
| | 144 | + |
| | 145 | + function TSNode($name = '') { |
| | 146 | + $this->name = $name; |
| | 147 | + } |
| | 148 | +} |
| \ No newline at end of file |
| Property changes on: trunk/extensions/Validator/TopologicalSort.php |
| ___________________________________________________________________ |
| Name: svn:eol-style |
| 1 | 149 | + native |