Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Python (yield): all paths from leaves to root in a tree

Tags:

python

yield

I want to generate all paths from every leaf to root in a tree. I'd like to do that with generators, to save memory (tree can be big). Here's my code:

def paths(self, acc=[]):
    if self.is_leaf():
        yield [self.node]+acc

    for child in self.children:
        child.paths([self.node]+acc)

But it doesn't work. Why? Invoked at root, it traverses the tree from top to bottom, collecting nodes in "acc". "acc" should be returned in every leaf...

is_leaf() is true if self.children is empty.

like image 774
jsmith Avatar asked Aug 20 '11 21:08

jsmith


2 Answers

This code only yields leaves that are (immediate) children of the root. The other ones get visited, they yield to the upper function, but the upper function does nothing with them. What you need is to yield them from the lower function to the upper one:

def paths(self, acc=[]):
    if self.is_leaf():
        yield [self.node]+acc

    for child in self.children:
        for leaf_path in child.paths([self.node]+acc): # these two
            yield leaf_path                            # lines do that

This should do the trick.

like image 192
Gabi Purcaru Avatar answered Sep 28 '22 08:09

Gabi Purcaru


At the moment the for loop doesn't yield anything. It should instead yield all the elements that are generated by the recursive call:

for child in self.children:
    for path in child.paths([self.node]+acc):
        yield path
like image 38
sth Avatar answered Sep 28 '22 07:09

sth