CODEWITHSUNDEEP
pythonnetworkxgraph-traversal
paradiso
paradiso

Reputation: 379

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

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?

Upvotes: 3

Views: 3383

Answers (3)

den.run.ai
den.run.ai

Reputation: 5943

Use networkx directly:

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

Upvotes: 0

Bas Swinckels
Bas Swinckels

Reputation: 18498

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.

Upvotes: 3

kiriloff
kiriloff

Reputation: 26333

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

Upvotes: 1

Related Questions