manage dependencies by topological sort

DependenciesManager.php

<?php
class DependenciesManager
{
    const NOT_VISITED = 1;
    const IN_PROGRESS = 2;
    const VISITED = 3;

    private $_nodeStates = array();
    private $_names = array();
    private $_relatedNames = array();
    private $_sorted = array();

    public function __construct($callback)
    {
        if (!is_callable($callback)) {
            throw new Exception('Invalid callback');
        }
        $r = new ReflectionFunction($callback);
        if ($r->getNumberOfParameters() != 1) {
            throw new Exception('Invalid callback prototype');
        }
        $this->callback = $callback;
    }

    public function clear()
    {
        $this->_names = $this->_relatedNames = array();
    }

    public function sort()
    {
        $nodeCount = count($this->_names);
        if ($nodeCount == 0) {
            return array();
        } else if ($nodeCount == 1) {
            return array_values($this->_names);
        }

        foreach ($this->_names as $node) {
            $this->_nodeStates[$node] = self::NOT_VISITED;
        }

        foreach ($this->_names as $node) {
            if ($this->_nodeStates[$node] == self::NOT_VISITED) {
                $this->_visitNode($node);
            }
        }

        $sorted = array_reverse($this->_sorted);

        $this->_sorted = $this->_nodeStates = array();

        return $sorted;
    }

    private function _visitNode($node)
    {
        $this->_nodeStates[$node] = self::IN_PROGRESS;

        if (isset($this->_relatedNames[$node])) {
            foreach ($this->_relatedNames[$node] as $relatedNode) {
                if ($this->_nodeStates[$relatedNode] == self::NOT_VISITED) {
                    $this->_visitNode($relatedNode);
                }
            }
        }

        $this->_nodeStates[$node] = self::VISITED;
        $this->_sorted[] = $node;
    }

    public function addDependency($fromClass, $toClass)
    {
        if (isset($this->_relatedNames[$fromClass]) && in_array($toClass, $this->_relatedNames[$fromClass]))
            return;
        $this->_relatedNames[$fromClass][] = $toClass;
    }

    public function add($name)
    {
        if (!isset($this->_names[$name])) {
            $this->_names[$name] = $name;
        }
    }

    public function load($name)
    {
        $dependencies = call_user_func($this->callback, $name);
        $this->add($name);
        foreach ($dependencies as $dependency) {
            $this->add($dependency);
            $this->addDependency($dependency, $name);
            $this->load($dependency);
        }

        return $this;
    }
}

function my_cb($table) {
    switch ($table) {
        case 'classes_matieres_professeurs':
            return array('classes', 'matieres', 'professeurs');
        case 'eleves_matieres':
            return array('eleves', 'matieres');
        case 'eleves':
            return array('classes', 'matieres');
        case 'reponses':
            return array('eleves', 'matieres', 'questions');
        case 'questions':
            return array('categories');
        default:
            return array();
    }
}

$dm = new DependenciesManager(
    /*function ($value) {
        return array('eleves', 'matieres');
    }*/
    'my_cb'
);

$dm->load('classes_matieres_professeurs');
$dm->load('eleves_matieres');
$dm->load('reponses');

echo '<pre>', print_r($dm->sort(), TRUE), '</pre>';
/*
Array
(
    [0] => categories
    [1] => questions
    [2] => professeurs
    [3] => matieres
    [4] => classes
    [5] => eleves
    [6] => reponses
    [7] => eleves_matieres
    [8] => classes_matieres_professeurs
)
*/

DependenciesManager.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-

class DependenciesManager:
    _VISITED     = 1 << 0
    _NOT_VISITED = 1 << 1
    _IN_PROGRESS = 1 << 2

    def __init__(self, callback):
        self._data = {}
        self._callback = callback

    def load(self, name):
        dependencies = self._callback(name)
        self.add(name)
        for dependency in dependencies:
            self.add(dependency)
            self.addDependency(dependency, name)
            self.load(dependency)

    def add(self, name):
        if name not in self._data:
            self._data[name] = set()

    def addDependency(self, f, t):
        self._data[f].add(t)

    def _visitNode(self, node, states, result):
        states[node] = self.__class__._IN_PROGRESS
        if node in self._data:
            for dependency in self._data[node]:
                if states[dependency] is self.__class__._NOT_VISITED:
                    self._visitNode(dependency, states, result)
        states[node] = self.__class__._VISITED
        result.append(node)

    def sort(self):
        if len(self._data.keys()) < 2:
            return self._data.keys()
        result = []
        states = {k:self.__class__._NOT_VISITED for k in self._data.iterkeys()}
        for node in self._data.iterkeys():
            if states[node] is self.__class__._NOT_VISITED:
                self._visitNode(node, states, result)
        result.reverse()
        return result

def my_cb(name):
    DATA = {
        'classes_matieres_professeurs': ['classes', 'matieres', 'professeurs'],
        'eleves_matieres': ['eleves', 'matieres'],
        'eleves': ['classes', 'matieres'],
        'reponses': ['eleves', 'matieres', 'questions'],
        'questions': ['categories']
    }
    if name in DATA:
        return DATA[name]
    else:
        return []

dm = DependenciesManager(my_cb)
dm.load('classes_matieres_professeurs')
dm.load('eleves_matieres')
dm.load('reponses')
print dm.sort()