LexBFS.py

"""LexBFS.py

Lexicographic breadth-first-search traversal of a graph, as described
in Habib, McConnell, Paul, and Viennot, "Lex-BFS and Partition Refinement,
with Applications to Transitive Orientation, Interval Graph Recognition,
and Consecutive Ones Testing", Theor. Comput. Sci. 234:59-84 (2000),
http://www.cs.colostate.edu/~rmm/lexbfs.ps

D. Eppstein, November 2003.
"""

from PartitionRefinement import PartitionRefinement
from Sequence import Sequence
from Util import arbitrary_item

def LexBFS(G):
    """Find lexicographic breadth-first-search traversal order of a graph.
    G should be represented in such a way that "for v in G" loops through
    the vertices, and "G[v]" produces a sequence of the neighbors of v; for
    instance, G may be a dictionary mapping each vertex to its neighbor set.
    Running time is O(n+m) and additional space usage over G is O(n).
    """
    P = PartitionRefinement(G)
    S = Sequence(P, key=id)
    while S:
        set = S[0]
        v = arbitrary_item(set)
        yield v
        P.remove(v)
        if not set:
            S.remove(set)
        for new,old in P.refine(G[v]):
            S.insertBefore(old,new)