Python tree implementation - node reference

Question

I have this code to implement a tree in Python. One of the functions is to find the sum of the values of all nodes below (including itself), but this is not working.

I think the reason is because, once I create a node, I can't go back and access it with Node (name, value) - that would create a new node with that name and value, rather than referring to the one in the tree with that name and value, that has children linked to it.

Therefore, the sum_below function is just returning the value of the node. How I can reference the nodes in the tree:

class Node(object):
    def __init__(self, name, value):
        self.name = name
        self.value = value
        self.children = []

    def add_child(self, obj):
        self.children.append(obj)

    def sum_below(self):
        if self.children == []:
            return self.value
        else:
            ret = self.value
            for child in self.children:
                ret += child.sum_below()
            return ret
    def __str__(self, level = 0):
        ret = "\t"*level+repr(self.value)+"\n"
        for child in self.children:
            ret += child.__str__(level+1)
        return ret

[Edit] My problem is that once I create a node I can't reference it:

#In [2]:

Node(1,100)
parent = Node(1,100)
child = Node(2, 200)
parent.add_child(child)

#In [5]:

print parent

#Out [5]:

100
    200

#In [6]:

print Node(1,100)

#Out [6]:

100

So you see, parent, and Node(1,100) are not referencing the same things.

[EDIT]

#In [5]:
parent.sum_below()
#Out[5]:
300
#In [6]:
Node(1,100).sum_below()
#Out[6]:
100

In the code above, Node(1,100).sum_below() should be equal to parent.sum_below(), because they should be referring to the same node, but they're not.

Your code will raise a NameError because there is nothing called sum_below. You need to do child.sum_below(). — BrenBarn
– BrenBarn, Commented Nov 22, 2015 at 7:48
thanks. I changed it, but for some reason I think that part was working fine before... — md1630
– md1630, Commented Nov 22, 2015 at 7:51
Can you show an example with sample data demonstrating the problem? — BrenBarn
– BrenBarn, Commented Nov 22, 2015 at 7:52
What exactly does not work? Do you only get the value of the root element? It seems to me that you are not setting the list of children anywhere? (i.e. self.children is always []) Showing how you actually test your class would be helpful. — plamut
– plamut, Commented Nov 22, 2015 at 7:54
Your code is correct and works fine. And, what's more important, your deduction (parent and Node(1,100) are not referencing the same things) is the real lesson here (as already pointed out by Animesh Kumar): whenever you call the object class (e.g. by writing Node(1, 100)) you are creating a new instance of Node which happens to share the same name and value (and class), but which are not related each other in any other way. — davidedb
– davidedb, Commented Nov 25, 2015 at 15:36

6502 · Accepted Answer · 2015-11-22 07:57:47Z

2

The code seems ok. The only "imprefection" I see is that the special case:

if self.children == []: ...

is not needed at all. The simplified version:

def sum_below(self):
    ret = self.value
    for child in self.children:
        ret += child.sum_below()
    return ret

would work too. It could also be simplified further a bit by using sum:

def sum_below(self):
    return (self.value +
            sum(child.sum_below() for child in self.children))

answered Nov 22, 2015 at 7:57

6502

115k17 gold badges177 silver badges277 bronze badges

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

Comments

Animesh Kumar · Accepted Answer · 2015-11-23 13:33:03Z

The problem why you are not getting same output with parent.sum_below() and Node(1, 100).sum_below() is that 'parent' is an object of Node class and has a child attribute containing another node object 'child' so it works the way it should but when you write Node(1, 100).sum_below() you are creating a new object with name attribute = 1 and value attribute = 100 and calling sub_below() method on it so, it will return the value of itself as it has no child added yet.

Moreover, you can't even access this newly created node later because you are not assigning it to any variable. To to that you should do something like this:

 >>>parent2 = Node(1, 100)
 >>>parent2.sum_below()
 100
 >>>parent2.add_child(parent1)
 >>>parent2.sum_below()
 400

bergerg · Accepted Answer · 2016-12-04 09:35:10Z

This answer refers only to the part where you need a reference to a previous instance by specifying the name (assuming there is at most one node with the same name).

My suggestion is that you try out metaclasses. I know it's a controversial issue in Python but I think is worth knowing. Also I think there is a better and more pythonic way of doing this but nonetheless here is my solution.. The next code snippet will probably work. (not checked! I'm writing from my phone. Maybe small adjustments are required).

Class Metanode(object):
    __nodes = {}

def __new__(cls,name,val):
    if name not in Metanode.__nodes.keys():
        Metanode.__nodes[name] = object.__new__(cls,name,val)
    return Metanode.__nodes[name]

Then you add this as metaclasses:

class Node(metaclass=Metanode,object):
    ''' put rest of your def here '''
    pass

Now your metaclass hold a dictionary of instances. Whenever you create a new instance with the name 'x' you will get the last instance named with that name. Of course you also need to handle the destruction of these instances in the metaclass too (so the dictionary won't have keys to non-existing instances).

EDIT: After reviewing the code properly in my computer, this code doesn't work. However the next piece of code, not involving metaclasses at all will work (checked on my Ubuntu machine with python3):

class Node(object):
    nodes={}

    def new_init(self,name,val):
        self.name = name
        self.val = val
        self.children = [ ]

    def __new__(cls,name,val,*args,**kwds):
        if name not in Node.nodes.keys():
            Node.nodes[name] = super(Node,cls).__new__(cls,*args,**kwds)
            Node.nodes[name].new_init(name,val)
        return Node.nodes[name]

    def __init__(self,name,val):
        pass

    def sum_below(self):
        return self.val + sum(child.sum_below() for child in self.children)

    def add_child(self,node):
        if not isinstance(node,Node):
            '''raise-some-exception-or-whatnot'''
        self.children.append(node)

Collectives™ on Stack Overflow

Python tree implementation - node reference

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related