http://www.mediawiki.org/wiki/Special:Code/MediaWiki/65557
Revision: 65557 Author: jeroendedauw Date: 2010-04-26 21:39:02 +0000 (Mon, 26 Apr 2010) Log Message: ----------- Changes for 0.3 - Added class for dependency solving Added Paths: ----------- trunk/extensions/Validator/TopologicalSort.php Added: trunk/extensions/Validator/TopologicalSort.php =================================================================== --- trunk/extensions/Validator/TopologicalSort.php (rev 0) +++ trunk/extensions/Validator/TopologicalSort.php 2010-04-26 21:39:02 UTC (rev 65557) @@ -0,0 +1,147 @@ +<?php + +/** + * Sorts a series of dependency pairs in linear order. + * + * Based on http://blog.metafoundry.com/2007/09/topological-sort-in-php.html + * + * usage: + * $t = new TopologicalSort($dependency_pairs); + * $load_order = $t->tsort(); + * + * where dependency_pairs is in the form: + * $name => (depends on) $value + * + * @author Eddie Haber + * @author Jeroen De Dauw + * + * TODO: fix conventions further + * TODO: include/load class + * TODO: Use in revised version of Validator class + */ +class TopologicalSort { + var $nodes = array (); + + /** + * Dependency pairs are a list of arrays in the form + * $name => $val where $key must come before $val in load order. + */ + function TopologicalSort($dependencies = array(), $parse = false) { + if ($parse) { + $dependencies = $this->parseDependencyList ( $dependencies ); + } + + // turn pairs into double-linked node tree + foreach ( $dependencies as $key => $dpair ) { + list ( $module, $dependency ) = each ( $dpair ); + if ( !isset ( $this->nodes [$module] )) $this->nodes [$module] = new TSNode ( $module ); + if ( !isset ( $this->nodes [$dependency] )) $this->nodes [$dependency] = new TSNode ( $dependency ); + if ( !in_array ( $dependency, $this->nodes [$module]->children )) $this->nodes [$module]->children [] = $dependency; + if ( !in_array ( $module, $this->nodes [$dependency]->parents )) $this->nodes [$dependency]->parents [] = $module; + } + } + + /** + * Perform Topological Sort + * + * @param array $nodes optional array of node objects may be passed. + * Default is $this->nodes created in constructor. + * + * @return sorted array + */ + function tsort($nodes = array()) { + // use this->nodes if it is populated and no param passed + if (! @count ( $nodes ) && count ( $this->nodes )) { + $nodes = $this->nodes; + } + + + // get nodes without parents + $root_nodes = array_values ( $this->getRootNodes ( $nodes ) ); + + // begin algorithm + $sorted = array (); + while ( count ( $nodes ) > 0 ) { + // check for circular reference + if (count ( $root_nodes ) == 0) + return false; + + // remove this node from root_nodes + // and add it to the output + $n = array_pop ( $root_nodes ); + $sorted [] = $n->name; + + // for each of its children + // queue the new node finally remove the original + for($i = (count ( $n->children ) - 1); $i >= 0; $i --) { + $childnode = $n->children [$i]; + // remove the link from this node to its + // children ($nodes[$n->name]->children[$i]) AND + // remove the link from each child to this + // parent ($nodes[$childnode]->parents[?]) THEN + // remove this child from this node + unset ( $nodes [$n->name]->children [$i] ); + $parent_position = array_search ( $n->name, $nodes [$childnode]->parents ); + unset ( $nodes [$childnode]->parents [$parent_position] ); + // check if this child has other parents + // if not, add it to the root nodes list + if (! count ( $nodes [$childnode]->parents )) + array_push ( $root_nodes, $nodes [$childnode] ); + } + + // nodes.Remove(n); + unset ( $nodes [$n->name] ); + } + return $sorted; + } + + /** + * Returns a list of node objects that do not have parents + * + * @param array $nodes array of node objects + * + * @return array of node objects + */ + function getRootNodes($nodes) { + $output = array (); + foreach ( $nodes as $name => $node ) + if (! count ( $node->parents )) + $output [$name] = $node; + return $output; + } + + /** + * Parses an array of dependencies into an array of dependency pairs + * + * The array of dependencies would be in the form: + * $dependency_list = array( + * "name" => array("dependency1","dependency2","dependency3"), + * "name2" => array("dependencyA","dependencyB","dependencyC"), + * ...etc + * ); + * + * @param array $dlist Array of dependency pairs for use as parameter in tsort method + * @return array + */ + function parseDependencyList($dlist = array()) { + $output = array (); + foreach ( $dlist as $name => $dependencies ) + foreach ( $dependencies as $d ) + array_push ( $output, array ($d => $name ) ); + return $output; + } +} + +/** + * Node class for Topological Sort Class + * + */ +class TSNode { + var $name; + var $children = array(); + var $parents = array(); + + function TSNode($name = '') { + $this->name = $name; + } +} \ No newline at end of file Property changes on: trunk/extensions/Validator/TopologicalSort.php ___________________________________________________________________ Added: svn:eol-style + native _______________________________________________ MediaWiki-CVS mailing list MediaWiki-CVS@lists.wikimedia.org https://lists.wikimedia.org/mailman/listinfo/mediawiki-cvs