Function depth_first_search

pattern/graph/__init__.py:687–704

Visits all the nodes connected to the given root node, depth-first. The visit function is called on each node. Recursion will stop if it returns True, and subsequently dfs() will return True. The traversable function takes the current node and edge, and returns True

(node, visit=lambda node: False, traversable=lambda node, edge: True, _visited=None)

#--- GRAPH TRAVERSAL -------------------------------------------------------------------------------

def depth_first_search(node, visit=lambda node: False, traversable=lambda node, edge: True, _visited=None):
    """ Visits all the nodes connected to the given root node, depth-first.
        The visit function is called on each node.
        Recursion will stop if it returns True, and subsequently dfs() will return True.
        The traversable function takes the current node and edge,
        and returns True if we are allowed to follow this connection to the next node.
        For example, the traversable for directed edges is follows:
         lambda node, edge: node == edge.node1
    """
    stop = visit(node)
    _visited = _visited or {}
    _visited[node.id] = True
    for n in node.links:
        if stop: return True
        if traversable(node, node.links.edge(n)) is False: continue
        if not n.id in _visited:
            stop = depth_first_search(n, visit, traversable, _visited)
    return stop
    
dfs = depth_first_search;