Tree seemingly building incorrectly in Python

Question

data = {'murtaza':('arnav', 'ohjun'),
        'ohjun':('arnav', 'murtaza'),
        'arnav':('ohjun', 'murtaza')}

class node:
    predecessors=[]
    nexts=[]
    student=''
    def __init__(self, student='', predecessors=[]):
        self.student=student
        self.predecessors=predecessors
    def grow(self, max=6, depth=0):
        if not self.student in self.predecessors:
            self.predecessors.append(self.student)
            for pref in data[self.student]:
                next=node(pref, self.predecessors)
                print(depth, self.predecessors, self.student, pref)
                next.grow(max, depth=depth+1)
                self.nexts.append(next)
        else:
            return

So, here is my data and class definition for node. What i expect to happen when I call the grow() method on a node object is the following: it looks up the student name in the data, then for each of the names associated with that student (i.e. their preferences, hence for pref in data[self.student]) creates a new node, adds it to the nodes branching off from the current node, then call grow() on that new node. That method will then continue building the tree unless a student appears twice in the sequence, hence checking if not self.student in self.predecessors.

The problem seems to be that predecessors are not being remembered correctly in the tree. For some reason, sibling node suddenly get all the predecessors of their children. Here is the program's output:

0 ['murtaza'] murtaza arnav
1 ['murtaza', 'arnav'] arnav ohjun
2 ['murtaza', 'arnav', 'ohjun'] ohjun arnav
2 ['murtaza', 'arnav', 'ohjun'] ohjun murtaza #as expected up to here
1 ['murtaza', 'arnav', 'ohjun'] arnav murtaza
0 ['murtaza', 'arnav', 'ohjun'] murtaza ohjun

I'd expect that to read:

0 ['murtaza'] murtaza arnav
1 ['murtaza', 'arnav'] arnav ohjun
2 ['murtaza', 'arnav', 'ohjun'] ohjun arnav
2 ['murtaza', 'arnav', 'ohjun'] ohjun murtaza 
1 ['murtaza', 'arnav'] arnav murtaza
0 ['murtaza'] murtaza ohjun
1 ['murtaza', 'ohjun'] ohjun arnav
2 ['murtaza', 'ohjun', 'arnav'] arnav ohjun
2 ['murtaza', 'ohjun', 'arnav'] arnav murtaza
1 ['murtaza', 'ohjun'] ohjun murtaza

Am I understanding the code I've written wrong, or is my understanding of the algorithm wrong? Or is my implementation wrong? I really thought I understood how to make a tree but this doesn't seem to be working the way I think it should.

Edit: I should add that the main body looks like this:

mort = node()
mort.student='murtaza'
mort.grow()

score 2 · Accepted Answer · edited May 23 '17 at 12:23

2

This line:

next=node(pref, self.predecessors)

does not make a copy of self.predecessors, instead it passes a reference to the named list object. Similarly, this line:

    self.predecessors=predecessors

does not make a copy of predecessors. Consequently, all of your node objects operate on precisely the same list; when one object calls .append(), all objects' predecessor lists are updated.

A solution is to replace one of those calls with copy.deepcopy(), like so:

    self.predecessors = copy.deepcopy(predecessors)

Depending upong your precise data structure, you may need copy.copy() instead.

Additionally, and probably unrelated to your question, your provision of a default value for predecessors in __init__() will not work the way you expect. (See here). Try this instead:

def __init__(self, student='', predecessors=None):
    self.student=student
    if predecessors is None:
        self.predecessors = []
    else:
        self.predecessors=copy.deepcopy(predecessors)

edited May 23 '17 at 12:23

Community

1
1

answered May 10 '16 at 18:36

Robᵩ

163,533
20
239
308

Thanks a lot, output is exactly as I expected now. Can't believe I forgot that. Python should have more clarity for when something is passed by copy by default, and sometimes I forget that objects are passed by reference, but I guess I'll get used to it. – murtaza64 May 10 '16 at 18:42
1

@murtaza64 There is all the clarity there can be: something *NEVER* is copied. Your problem is mutability of objects passed by reference. There is a very simple rule to follow to prevent at least some of your problems: never declare class-level attributes (predecessor, next). This is *NOT* java or C++ where this kind of syntax works – deets May 10 '16 at 18:53
@deets how should I go about this then? I need to be able to build the tree keeping in mind the lineage (ancestry? is there a programming word for this?) of each node so that I can 1) easily track the different possible arrangements and 2) quickly find out if the tree has hit a dead end at a specific node. Is there a better way to build this tree? – murtaza64 May 10 '16 at 19:01
I don't see what the one has to do with the other. My point is strictly about only creating (data) attributes in `__init__.py`. And - as Rob pointed out - not use mutable default arguments. Your lineage is orthogonal to this. I personally would create a parent-relationship though, and simply walk that. So pass in the parent, and add a predecessors-method or property which computes the predecessors as `[self.parent] + self.parent.predecessors if self.parent is not None else []` – deets May 10 '16 at 19:29

Tree seemingly building incorrectly in Python

1 Answers1