Depth first search algorithm in python

Question

(This question is followed up in more detail here: python-search-algorithm-from-implied-graphs)

Suppose I have a function that takes an input ($x_i$) and then goes through a loop and yields a series of outputs ($x_{i, j}$). Then each output can be an input again to the same function yielding further outputs ($x_{i, j, k}$). And I'm trying to find a set of steps via this function to a particular end state.

This is a general problem, and my question is what is a good code structure within python to handle this.

Here's some meta code as an example (though it might be more complicated in practice):

def f(x):
  for i in range(n):
    if some_condition:
      yield g(x,i) 
  yield false

Then for some $x_0$ and some $y$, we're looking for a sequence $x_0,x_1,\ldots,x_k$, such that $x_k=y$, and $x_{j+1}=g(x_j,i_j)$ for $j\in{0,\ldots,k-1}$.

To do this with a depth first search where you would calculate $f(f(\ldots f(x) \ldots))$ first until it yields the targeted result or a false. Then back up one step and yield the second result from $f$ and repeat (a rough description, but you get the idea: a depth first search, basically).

It seems to me that the yield keyword is going to be inefficient to handle this. You've also got to handle the stack (I think this is the right terminology) of $(x, f(x), f(f(x)),\ldots)$ in a way that allows you to back track when you hit a dead end.

This general problem is something I come across now and then, and I kind of solve it ad hoc, but I wondered if there was a good general structure for solving this, which naturally and efficiently handles the stack and exploring the tree of possible solutions in python.

I hope this question is sufficiently clear. I welcome any thoughts, comments, clarifications or answers.

What specifically makes you think that the problem can be done more efficiently than brute-forcing? Do you sometimes hit a point that you've already been before (maybe look at dynamic programming/memoizing in that case), or is each path unique? You probably need to provide a specific example and point out where your existing solution is inefficient. — Marius
– Marius, Commented Oct 12, 2015 at 5:52
I'm not expecting it to be faster than brute force. I'm just trying to find an efficient way to do the brute force in python — Dr Xorile
– Dr Xorile, Commented Oct 12, 2015 at 14:26

6502 · Accepted Answer · 2015-10-12 14:57:00Z

2

I think that just using an explicit stack for the current path and recursion is simpler:

def search(start_state, neighbors, goal):
    path = [start_state]

    class PathFound(RuntimeError):
        pass

    def rsearch(x):
        if goal(x):
            raise PathFound
        for y in neighbors(x):
            path.append(y)
            rsearch(y)
            path.pop()

    try:
        rsearch(start_state)
    except PathFound:
        return path

    return None # No path exists

Python has a low recursion limit but for a depth-first search this is normally not an issue (and it can be extended anyway by sys.setrecursionlimit).

edited Oct 12, 2015 at 14:57

answered Oct 12, 2015 at 7:00

6502

115k17 gold badges177 silver badges277 bronze badges

Sign up to request clarification or add additional context in comments.

10 Comments

Dr Xorile Over a year ago

Is the indenting correct? I've not seen classes and functions be part of a function before?

6502 Over a year ago

@DrXorile: Yes. In Python you can declare classes and function inside functions. They will simply be local to the function.

Dr Xorile Over a year ago

Okay, I see. Thanks very much. +1 now, and a tick after I've tested it!

Dr Xorile Over a year ago

So goal and neighbors are functions of any given state, right. And then you just call search to solve the problem

6502 Over a year ago

@DrXorile: exactly. The exception trick is used to bail out of all the nested calls when (if) we get to the goal.

|

saikumarm · Accepted Answer · 2015-10-12 06:43:50Z

2

class Tree:
def __init__(self, value, children = None):
    self.value = value
    self.children = []
    if children:
        self.children = list(children)

def get_children(self):
    return list(self.children)

def get_value(self):
    return self.value

def has_children(self):
    if self.children:
        return True

node9 = Tree(9)
node5 = Tree(5, [node9])
node6 = Tree(6)
node3 = Tree(3, [node5, node6])
node7 = Tree(7)
node8 = Tree(8)
node4 = Tree(4, [node7, node8])
node2 = Tree(2)
node1 = Tree(1, [node2, node4, node3])

def iterate_child(child):
    global level
    print ' ' * level * 2, child.get_value()
    if child.has_children():
        level += 1
        for s_child in child.get_children():
            iterate_child(s_child)
        level -= 1

level = 1
print node1.get_value()
for child in node1.get_children():
    iterate_child(child)

as you can see in the above image, I have iterated through the children of the node1 and recursively iterated over the children of the children node, first, and then processed the second child of the parent node.

answered Oct 12, 2015 at 6:43

saikumarm

1,5751 gold badge16 silver badges30 bronze badges

2 Comments

Dr Xorile Over a year ago

Does this require that the whole tree is known up front?

saikumarm Over a year ago

No you can start from, any node and do the depth first from that node.

Collectives™ on Stack Overflow

Depth first search algorithm in python

2 Answers 2

10 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

10 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related