CODEWITHSUNDEEP
pythonpython-3.xdata-structurestreenodes
murtaza64
murtaza64

Reputation: 129

Tree seemingly building incorrectly in Python

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()

Upvotes: 1

Views: 46

Answers (1)

Robᵩ
Robᵩ

Reputation: 168626

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)

Upvotes: 2

Related Questions