Simple utility to resolve dependencies between arbitrary (but hashable) objects.

depgraph.py

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

class DependencyGraph(object):
    """
        Handle a dependency graph. Using :py:meth:`insert`, you add objects
        to the graph and connect them with their dependencies, and the
        :py:meth:`resolve` function will yield them back so that any object
        comes after all its dependencies.
    """
    class Node(object):
        def __init__(self, obj):
            self.obj = obj
            # Keep ordering for reproducibility, but use an underlying set
            # for uniqueness checks, in case the list gets big
            # ( x in s is O(1) for set, but O(n) for lists )
            self.dependencies = []
            self.depsset = set()
        def get_obj(self):
            return self.obj
        def add_dependency(self, dep):
            if dep not in self.depsset:
                self.dependencies.append(dep)
                self.depsset.add(dep)
        def get_dependencies(self):
            return self.dependencies
    
    def __init__(self):
        # The root of the tree is a special node that depends on all nodes
        # of the graph and serves as bootstrap for the DFS
        self.root = self.Node(None)
        self.nodes = {None: self.root}
    
    def _get_node(self, obj):
        # Get a node based on its obj. If the node doesn't exist, it is
        # created and added to the graph.
        if not obj in self.nodes:
            node = self.nodes[obj] = self.Node(obj)
            self.root.add_dependency(node)
        else:
            node = self.nodes[obj]
        return node
    
    def insert(self, obj, parent=None):
        """
            Insert a relation in the graph. If `obj` doesn't depend on
            anything, `parent` can be left to `None`. Both `obj` and
            `parent` are inserted in the graph if they do not exist, but they
            will not be duplicated. Both `obj` and `parent` must be hashable.
        """
        pnode = self._get_node(parent)
        node = self._get_node(obj)
        if pnode is not self.root:
            node.add_dependency(pnode)
    
    def resolve(self):
        """
            Yield all objects in the graph so that any object comes after its
            dependencies. Raises :py:class:`RuntimeError` if a cyclic dependency
            is found.
        """
        already_raised = set()
        already_visited = set()
        def dep_resolve(node):
            already_visited.add(node)
            for dep in node.get_dependencies():
                if not dep in already_raised:
                    if dep in already_visited:
                        raise RuntimeError(
                            "Cyclic dependency detected: {!r} and {!r}".format(
                                node.get_obj(), dep.get_obj()
                            )
                        )
                    # yield from is only available from python 3.3
                    for obj in dep_resolve(dep):
                        yield obj
            if node not in already_raised:
                already_raised.add(node)
                if node is not self.root:
                    yield node.get_obj()
        for obj in dep_resolve(self.root):
            yield obj

def test():
    graph = DependencyGraph()
    graph.insert("A", "B")
    graph.insert("C", "D")
    graph.insert("A", "C")
    graph.insert("B", "C")
    graph.insert("D", None)
    graph.insert("E", "F")
    graph.insert("F", "G")
    graph.insert("H", "I")
    graph.insert("E", "I")
    graph.insert("F", "J")
    
    for pkg in graph.resolve():
        print(pkg)
    
    try:
        graph.insert("J", "F")
        list(graph.resolve())
    except RuntimeError as e:
        print("Cyclic dependency detection OK")
    else:
        raise RuntimeError("Cyclic dependency was not detected !")
    return 0

if __name__ == '__main__':
    test()