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
