topological sorting methods

topological_sort.py

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

"""
`Topological sort by Kahn (1962) on Wikipedia
<http://en.wikipedia.org/wiki/Topological_sorting>`_
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    insert n into L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)
"""

class CircularDependencyError(Exception):
    def __init__(self, keys):
        self.args = keys
        self.message = self.__str__
    def __str__(self):
        return 'Not a DAG. These keys are cyclic:\n\t%s' % str(self.args)

def topological_sort(DAG):
    """
    Kahn ('62) topological sort.

    :param DAG: directed acyclic graph
    :type DAG: dict
    """
    L = []
    S = [k for k, v in DAG.iteritems() if not v]
    while S:
        n = S.pop(0)
        L.append(n)
        for m in (k for k, v in DAG.iteritems() if n in v):
            # idx = DAG[m].index(n); DAG[m].pop(idx)  # Python < 2.7 alternative
            DAG[m] = list(set(DAG[m]).difference([n]))
            if not DAG[m]:
                S.append(m)
    if any([bool(v) for v in DAG.itervalues()]):
        raise CircularDependencyError([k for k, v in DAG.iteritems() if v])
    return L

if __name__ == "__main__":
    # test DAG
    DAG = {'7': [], '5': [], '3': [], '11': ['7', '5'], '8': ['7', '3'],
           '2': ['11'], '9': ['11', '8'], '10': ['11', '3']}
    print topological_sort(DAG.copy())
    
    # test 10->9->8 circular dependency
    notDAG = {'7': [], '5': [], '3': [], '11': ['7', '5'], '8': ['7', '3', '10'],
              '2': ['11'], '9': ['11', '8'], '10': ['11', '3', '9']}
    print topological_sort(notDAG.copy())