Finding the (guaranteed unique) path between two nodes in a tree

Question

I have a (likely) simple graph traversal question. I'm a graph newbie using networkx as my graph data structures. My graphs always look like this:

             0
      1              8
   2     3       9      10
 4  5   6 7    11 12  13  14

I need to return the path from the root node to a given node (eg., path(0, 11) should return [0, 8, 9, 11]).

I have a solution that works by passing along a list which grows and shrinks to keep track of what the path looks like as you traverse the tree, ultimately getting returned when the target node is found:

def VisitNode(self, node, target, path):
    path.append(node)
    # Base case. If we found the target, then notify the stack that we're done.
    if node == target:
        return True
    else:
        # If we're at a leaf and it isn't the target, then pop the leaf off
        # our path (backtrack) and notify the stack that we're still looking
        if len(self.neighbors(node)) == 0:
            path.pop()
            return False
        else:
            # Sniff down the next available neighboring node
            for i in self.neighbors_iter(node):
                # If this next node is the target, then return the path 
                # we've constructed so far
                if self.VisitNode(i, target, path):
                    return path
            # If we've gotten this far without finding the target, 
            # then this whole branch is a dud. Backtrack
            path.pop()

I feel in my bones that there is no need for passing around this "path" list... I should be able to keep track of that information using the call stack, but I can't figure out how... Could someone enlighten me on how you would solve this problem recursively using the stack to keep track of the path?

Mandatory reading for implementing graphs in python http://www.python.org/doc/essays/graphs/ — Fredrik Pihl, Sep 28 '13 at 21:10
Answer is probably here: http://stackoverflow.com/questions/6061744/how-to-get-value-of-arguments-in-functions-at-stack — GL770, Sep 28 '13 at 21:26
@GL770 Directly looking up the stack using the `inspect` module for such a simple graph algorithm seems not really elegant to me. — Bas Swinckels, Sep 28 '13 at 21:44
@GL770 - It's kind of a nice idea, but not terribly elegant. Generally I'd like the stack contents to fall out through a cascade of 'return' statements, not by direct inspection. — paradiso, Sep 28 '13 at 22:41

Bas Swinckels · Accepted Answer · 2013-10-03T12:58:26.513

You could avoid passing around the path by returning None on failure, and a partial path on success. In this way, you do not keep some sort of 'breadcrumb trail' from the root to the current node, but you only construct a path from the target back to the root if you find it. Untested code:

def VisitNode(self, node, target):
    # Base case. If we found the target, return target in a list
    if node == target:
        return [node]

    # If we're at a leaf and it isn't the target, return None 
    if len(self.neighbors(node)) == 0:
        return None

    # recursively iterate over children
    for i in self.neighbors_iter(node):
        tail = self.VisitNode(i, target)
        if tail: # is not None
            return [node] + tail # prepend node to path back from target
    return None #none of the children contains target

I don't know the graph library you are using, but I assume that even leafs contain a neighbours_iter method, which obviously shouldn't yield any children for a leaf. In this case, you can leave out the explicit check for a leaf, making it a bit shorter:

def VisitNode(self, node, target):
    # Base case. If we found the target, return target in a list
    if node == target:
        return [node]
    # recursively iterate over children
    for i in self.neighbors_iter(node):
        tail = self.VisitNode(i, target)
        if tail: # is not None
            return [node] + tail # prepend node to path back from target
    return None # leaf node or none of the child contains target

I also removed some of the else statements, since inside the true-part of the if you are returning from the function. This is common refactering pattern (which some old-school people don't like). This removes some unnecessary indentation.

Exactly what I was hoping for. Thanks for your help... I had played with this idea, but it didn't come together for me. (P.S. I tested it and it works as described, although you have a trailing ":" on line 5 that needs to be deleted) — paradiso, Sep 28 '13 at 22:39

score 1 · Answer 2 · answered Sep 28 '13 at 22:13

You can avoid your path argument at all having path initialized in the method's body. If method returns before finding a full path, it may return an empty list.

But your question is also about using a stack instead of a list in Depth-First-search implementation, right? You get a flavor here: http://en.literateprograms.org/Depth-first_search_%28Python%29.

In a nutshell, you

def depthFirstSearch(start, isGoal, result):
    ###ensure we're not stuck in a cycle

    result.append(start)

    ###check if we've found the goal
    ###expand each child node in order, returning if we find the goal

    # No path was found
    result.pop()
    return False

with

###<<expand each child node in order, returning if we find the goal>>=
for v in start.successors:
    if depthFirstSearch(v, isGoal, result):
        return True

and

###<<check if we've found the goal>>=
if isGoal(start):
    return True

Thanks for your response. This is a nice explanation of the accepted answer (the two are basically equivalent). Always good to have more angles. +1 — paradiso, Sep 28 '13 at 22:43

score 0 · Answer 3 · answered Oct 06 '13 at 11:18

0

Use networkx directly:

all_simple_paths(G, source, target, cutoff=None)

answered Oct 06 '13 at 11:18

denfromufa

5,610
13
81
138

Could you provide a sample code with a hardcoded graph and testcase? – Tanishq Vyas Apr 06 '20 at 12:19

Finding the (guaranteed unique) path between two nodes in a tree

3 Answers3