Simple Python Topological Sorting

topological_sort.py

from collections import deque

def topological_sort(dependency_graph):
    """ Topological sorting algorithm.

    Args:
        dependency_graph: A mapping type whose keys represent graph nodes.
            Dependencies are indicated by the values which are sets containing
            keys for other nodes.
            Note: a node with no dependencies is a key indexing an empty set.
    
    Returns:
        A deque containing a topological order of node-keys in the graph.

    Raises:
        ValueError if the graph has at least one cycle.

    Example:
        The mapping {'A': set(['B', 'C']), 'B': set([]), 'C': set(['B'])}
        Means A depends on B and C, B depends on nothing, C depends on B.
        This algorithm would return a deque(['B', 'C', 'A'])

    Source:
        http://en.wikipedia.org/wiki/Topological_sorting#Algorithms
    """
    graph = dependency_graph.copy()
    L = deque()
    S = deque(node for node, deps in graph.iteritems() if not deps)
    while S:
        n = S.pop()
        L.append(n)
        for m, m_deps in graph.iteritems():
            try:
                m_deps.remove(n)
            except KeyError:
                pass
            else:
                if not m_deps:
                    S.appendleft(m)
    if any(graph.itervalues()):
        return ValueError, 'Graph has at least one cycle.'
    else:
        return L