python naive topological sort

topological-sort.py

#!/usr/bin/env python

import logging


class TopologicalSort(object):
    def __init__(self, dependencies=None):
        self.dependencies = dependencies if dependencies else {}

    def set_dependencies(self, package_id, package_ids):
        self.dependencies[package_id] = set(package_ids)

    def _get_dependencies(self, package_id, root=None, already_visited=None):
        if not root:
            root = package_id
        elif root == package_id:
            logging.warn("circular dependency detected in '{}'".format(package_id))
            raise StopIteration()

        if already_visited is None:
            already_visited = set()

        for dependency in self.dependencies.get(package_id, []):
            if dependency in already_visited:
                continue

            already_visited.add(dependency)

            for sub_dependency in self._get_dependencies(dependency, root=root, already_visited=already_visited):
                yield sub_dependency
            yield dependency

    def get_sorted_dependencies(self):
        # Reduction, connect all nodes to a dummy node and re-calculate
        special_package_id = 'topological-sort-special-node'
        self.dependencies[special_package_id] = self.dependencies.keys()
        sorted_dependencies = self._get_dependencies(special_package_id)
        sorted_dependencies = list(sorted_dependencies)
        del self.dependencies[special_package_id]

        return sorted_dependencies


def main():
    dependencies = {
        '3': ['5', '6'],
        '2': ['6'],
        '1': ['2', '3', '4'],
        '4': ['5'],
        '5': [],
        '6': [],
        '7': ['5', 'does-not-exists'],
        'b': ['c'],
        'a': ['b'],
        'c': [],
        'x': ['1', '6'],
        'z': ['3', 'a'],
    }

    t = TopologicalSort(dependencies)
    print t.get_sorted_dependencies()


if __name__ == '__main__':
    main()