findcycle.py

from itertools import chain, izip_longest


__all__ = ('detect_cycle',)


def detect_cycle(graph):
    """
    Detect a cycle in a directed graph by removing
    nodes with no leaf nodes. If there are nodes
    left which cannot be removed the graph is cyclic.

    `graph` is a dict representating a directed graph
    in adjacency list format eg.
        {'a': ['b', 'c'], 'b': ['c']}

    Algorithm from:
        http://www.cs.hmc.edu/~keller/courses/cs60/s98/examples/acyclic/

    Note: This is not a performant implementation.
    """
    # Normalize the graph.
    new_keys = set(
        chain.from_iterable(graph.itervalues())
    ).difference(graph.iterkeys())
    graph.update(izip_longest(new_keys, (), fillvalue=()))

    while graph:
        to_remove = [k for k, v in graph.iteritems() if not v]
        if not to_remove:
            # Or return the graph here containing the cycle.
            raise ValueError('Cyclic graph detected')

        # Prune leaf nodes.
        for node, edges in graph.items():
            if node in to_remove and not graph[node]:
                # We could yield these nodes that get removed
                # per iteration for a reverse topological sort.
                del graph[node]
            else:
                graph[node] = set(edges).difference(to_remove)


def test():
    """
    Simple test suite for `find_cycles`.

    All graphs flow from left to right
    and top to bottom. `*` signifies a
    two way relationship in contrast to
    above rule.

    Note these tests should probably be
    improved to be more encompassing.
    """
    # a - b
    #   \ |
    #     c
    graph = {
        'a': ['b', 'c'],
        'b': ['c'],
    }
    try:
        detect_cycle(graph)
    except ValueError:
        print 'cycle found: ', graph
    else:
        print 'Graph is a DAG.'

    # a - b
    #   * |
    #     c
    graph = {
        'a': ['b', 'c'],
        'b': ['c'],
        'c': ['a'],
    }

    try:
        detect_cycle(graph)
    except ValueError:
        print 'cycle found: ', graph
    else:
        assert False, 'Cyclic graph not detected.'

    # a - b - d
    #   \   /
    #     c
    graph = {
        'a': ['b', 'c'],
        'b': ['d'],
        'd': ['c'],
    }
    try:
        detect_cycle(graph)
    except ValueError:
        print 'cycle found: ', graph
    else:
        print 'Graph is a DAG.'


if __name__ == "__main__":
    test()