Topological Sort in PHP

I recently had the need to put together a dependency sort routine, also known as a topological sort, and assumed there were millions available in PHP. I did not immediately find a stand-alone class (i'm sure there are many, but after searching I decided I liked the challenge of putting together my own). So nothing super glitzy or flashy here, but maybe something handy to you in a pinch. The Wikipedia entry was clear and helpful for breaking down the logical steps and after a few variations I arrived at the following class (and helper Node class). If you find it helpful please use it in your code. This code was written in PHP5 but should be compatible with PHP4.

A topological sort is useful when you want to load a bunch of libraries or modules some of which may be dependent upon each other. And it has many applications in graphing and plotting, especially with regard to vertices on a graph.

I want to also thank Jacob Good for his blog entry on Topological Sorting in C# which really helped get me started.

<?php
/**
* Sorts a series of dependency pairs in linear order
*
* usage:
* $t = new TopologicalSort($dependency_pairs);
* $load_order = $t->tsort();
*
* where dependency_pairs is in the form:
* $name => (depends on) $value
*
*/
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;
}
}
?>

Here is an example implementation for a series of modules which much be loaded based on pre-defined dependencies:

<?php

// define dependencies
// these definitions might be loaded from various modules at runtime
$module_dependencies['user'] = array('database','system','network','admin');
$module_dependencies['database'] = array('system','network');
$module_dependencies['network'] = array('system');
$module_dependencies['admin'] = array('system','network','database');
// in this example, the module called "system" has no dependencies

// pass this dependency tree to the constructor
// If the second parameter is true, it signals the passed array
// must first be converted internally into dependency pairs
$t = new TopologicalSort($module_dependencies, true);

$safe_load_order = $t->tsort();

// if tsort returns false, there was a dependency loop
if (! $safe_load_order)
 die("There was a loop in dependency requirements.");

print_r($safe_load_order);

?>

As I wrote above, I did find some implementations in other languages. And within some larger code libraries in PHP. But I just wanted a stand-alone class. Here is a topological sort in Perl. And here is one in Java. And here is one in Ruby. And here is one even built into Unix.