Reverse Dependency Resolver

gistfile1.txt

#!/usr/bin/env python

# Credit for DependencyResolver goes to: http://code.activestate.com/recipes/576570-dependency-resolver/
class DependencyResolver:
    def __init__(self):
        self.dependency_dict = {}

    def insertDependency(self, key, values):
        self.dependency_dict[key] = values

    def getDictSets(self):
        return dict((k, set(self.dependency_dict[k])) for k in self.dependency_dict)

    def getSortedValuesSets(self):
        d = dict((k, set(self.dependency_dict[k])) for k in self.dependency_dict)
        r = []
        while d:
            # values not in keys (items without dep)
            t = set(i for v in d.values() for i in v) - set(d.keys())
            # and keys without value (items without dep)
            t.update(k for k, v in d.items() if not v)

            if len(t) == 0 and len(d) > 0:
                raise Exception("Cyclic or Invalid Dependency Detected! %s" % d)

            # can be done right away
            r.append(t)
            # and cleaned up
            d = dict(((k, v-t) for k, v in d.items() if v))
        return r

# lines 33 - 76 Thank you Andrew Slaughter @ https://github.com/aeslaughter
class Node(object):
    def __init__(self, name):
        self.name = name
        self.required_by = []

    def _getRequiredBy(self):
        out = self.required_by
        for n in self.required_by:
            out += n._getRequiredBy()
        return out

    def getDeps(self):
        return set([r.name for r in self._getRequiredBy()])

class ReverseDependencyResolver:
    def __init__(self):
        self.dependency_dict = {}

    def insertDependency(self, key, values):
        self.dependency_dict[key] = values

    def getDictSets(self):
        sorted_dict = self.getSortedValuesSets()
        # re-use DependencyResolver!
        d = DependencyResolver()
        for key, value in sorted_dict.iteritems():
            d.insertDependency(key, value)
        return d.getSortedValuesSets()

    def getSortedValuesSets(self):
        nodes = {}
        for key in self.dependency_dict.keys():
            nodes[key] = Node(key)

        for k, v in self.dependency_dict.iteritems():
            n0 = nodes[k]
            for r in v:
                n1 = nodes[r]
                n1.required_by.append(n0)

        for key in nodes.keys():
            nodes[key] = nodes[key].getDeps()

        return nodes

if __name__ == '__main__':
    # Example Dependency
    deps = {'A' : [],
            'B' : ['A'],
            'C' : ['B'],
            'D' : ['B'],
            'E' : ['D'],
            'F' : ['D'],
            'G' : ['B', 'E']}

    d = DependencyResolver()
    r = ReverseDependencyResolver()
    for key, value in deps.iteritems():
        d.insertDependency(key, value)
        r.insertDependency(key, value)

    print '\nApplied Dependency problem:', deps, '\n'
    print '\tForward Dependency:', d.getDictSets()
    print '\t\t Run Order:', d.getSortedValuesSets(), '\n'
    print '\tReverse Dependency:', r.getSortedValuesSets()
    print '\t\t Run Order:', r.getDictSets(), '\n'