DFS.py

"""DFS.py

Algorithms for depth first search in Python.
We need to search iteratively rather than recursively in
order to avoid Python's low recursion limit.

D. Eppstein, July 2004.
"""

# Types of edges in DFS traversal.
# The numerical values are used in DepthFirstSearcher, change with care.
forward = 1     # traversing edge (v,w) from v to w
reverse = -1    # returning backwards on (v,w) from w to v
nontree = 0     # edge (v,w) is not part of the DFS tree

whole_graph = object()  # special flag object, do not use as a graph vertex

def search(G,initial_vertex = whole_graph):
    """
    Generate sequence of triples (v,w,edgetype) for DFS of graph G.
    The subsequence for each root of each tree in the DFS forest starts
    with (root,root,forward) and ends with (root,root,reverse).
    If the initial vertex is given, it is used as the root and vertices
    not reachable from it are not searched.
    """
    visited = set()
    if initial_vertex == whole_graph:
        initials = G
    else:
        initials = [initial_vertex]
    for v in initials:
        if v not in visited:
            yield v,v,forward
            visited.add(v)
            stack = [(v,iter(G[v]))]
            while stack:
                parent,children = stack[-1]
                try:
                    child = next(children)
                    if child in visited:
                        yield parent,child,nontree
                    else:
                        yield parent,child,forward
                        visited.add(child)
                        stack.append((child,iter(G[child])))
                except StopIteration:
                    stack.pop()
                    if stack:
                        yield stack[-1][0],parent,reverse
            yield v,v,reverse

def preorder(G,initial_vertex = whole_graph):
    """Generate all vertices of graph G in depth-first preorder."""
    for v,w,edgetype in search(G,initial_vertex):
        if edgetype is forward:
            yield w

def postorder(G,initial_vertex = whole_graph):
    """Generate all vertices of graph G in depth-first postorder."""
    for v,w,edgetype in search(G,initial_vertex):
        if edgetype is reverse:
            yield w

def reachable(G,v,w):
    """Can we get from v to w in graph G?"""
    return w in preorder(G,v)

class Searcher:
    """
    Handler for performing general depth first searches of graphs.
    Some or all of the routines preorder, postorder, and backedge
    should be shadowed in order to make the search do something useful.
    """

    def preorder(self,parent,child):
        """
        Called when DFS visits child, before visiting all grandchildren.
        Parent==child when child is the root of each DFS tree.
        """
        pass

    def postorder(self,parent,child):
        """
        Called when DFS visits child, after visiting all grandchildren.
        Parent==child when child is the root of each DFS tree.
        """
        pass

    def backedge(self,source,destination):
        """Called when DFS discovers an edge to a non-child."""
        pass

    def __init__(self,G):
        """Perform a depth first search of graph G."""
        dispatch = [self.backedge,self.preorder,self.postorder]
        for v,w,edgetype in search(G):
            dispatch[edgetype](v,w)