Python recursive object refrence in Tree datastructure

Question

I am somehow new to python. I needed to use tree to store some data (file paths), The problem is when I generate the tree it seems that all objects after the root reference the same object, although step by step debugging showed the opposite. Here is my (minimized) code: first the node class:

class PathElement:  

  Element = ""
  IsStatic = True
  Children = []
  ChildrenCount = 0 

  def __init__(self, Element, IsStatic=True):
      self.Element = Element
      self.IsStatic = IsStatic
      if not IsStatic:
          self.Element = [] 

  def AddChild(self, Child):
      print(self, "    ", Child)
      self.Children.append(Child)
      self.ChildrenCount = len(self.Children)
      return Child

The Children is list of PathElement nodes. The code that build the tree:

def UnFoldAndCheck(self):
    Path = PathElement("root")
    Handler = Path
    Index = 0
    Count = len(self.Path)
    while Index < Count:

        element = self.Path[Index]

        if something:
            Child = None
            Child = PathElement(element)
            Handler.AddChild(Child)
            Handler = None #Those added to debug the problem
            Handler = Child
        elif other_thing:
            if condition:
                if some_large_condition:
                    ChildExec = None
                    ChildExec = PathElement(element, False)
                    for i in range(0, 5):
                        ChildExec.Element.append(self.Path[Index + i])
                    Handler.AddChild(ChildExec)
                    Handler = None
                    Handler = ChildExec
                    Index += 4
            elif another_condition:
                ChildOp = None
                ChildOp = PathElement(element, False)
                Handler.AddChild(ChildOp)
                Handler = None
                Handler = ChildOp
            elif some_else_condition:
                 if condition:
                    ChildExec = None
                    ChildExec = PathElement(element, False)
                    for i in range(0, 3):
                        ChildExec.Element.append(self.Path[Index + i])
                    Handler.AddChild(ChildExec)
                    Handler = None
                    Handler = ChildExec
                    Index += 2

                elif different_condition:
                    ChildExec = None
                    ChildExec = PathElement(element, False)
                    for i in range(0, 3):
                        ChildExec.Element.append(self.Path[Index + i])
                    Handler.AddChild(ChildExec)
                    Handler = None
                    Handler = ChildExec
                    Index += 1
        Index += 1
    return Path

My problem is that after the tree is built when I use it it will have always same structure: root -> object with 3 exact nodes -> same object -> same object to infinity while the expected is: root -> object -> first children -> second children -> third children -> etc I'm sure the problem is related to how python handle object references but I can't see where the problem exactly. Any help?

Update:

I reproduced the problem with smaller code (same class PathElement):

from PathElement import PathElement
Path = PathElement("root")
Handler = Path
for i in range(1,6):
   Child = PathElement("child"+str(i))
   Handler.AddChild(Child)
   Handler = Child
Tree = Path
while True:
   print(Tree.Element)
   if len(Tree.Children) > 0:
      Tree = Tree.Children[0]
   else:
       break

This code will make infinite loop

First of all, why not use a for loop instead of the while Index < Count loop? Also take a look at the python naming convention for changing your variable names. — Jakob Sachs
– Jakob Sachs, Commented May 25, 2018 at 9:58
I used for loop, but then I realized that I need while since (as you can see) I need to make forward jumps by increment the Index by more than 1. — Ahmad Issa
– Ahmad Issa, Commented May 25, 2018 at 10:39
I made some additions to run your code, and it does not give the result you say. Can you give the real code or a MCVE? In addition to Jakob comment: do not store the children_count but use len(children) and use a loop while path: ... path.pop(0) (on a copy of path if you don't want to consume it). You can then remove the index. — jferard
– jferard, Commented May 25, 2018 at 20:33
@jferard I added minimized code that reproduce the problem. And thank you, path.pop(0) look cleaner I'll will consider it. — Ahmad Issa
– Ahmad Issa, Commented May 26, 2018 at 12:56

jferard · Accepted Answer · 2018-05-26 20:03:22Z

I guess you come from Java or a similar language. It's important to stick with Python's conventions (Jakob Sachs gave you va link to the Style Guide for Python Code) because that makes your mistakes are easier to identify.

Now, what's wrong here? When you wrote:

class PathElement():  
  Children = []
  Element = ""
  IsStatic = True
  ChildrenCount = 0

You don't give the initial value of instance fields. You create an initialize class (static) fields. Hence, Children is a static field of the class PathElement. Here's a illustration of that:

class A():
    i = []

a = A()
b = A()

a.i.append(1) 
b.i.append(2) 
assert a.i == b.i == [1,2]

What happens when you try to make read the leftmost part of the tree (child 0, child 0 of child 0, ...)?

while True:
   print(Tree.Element)
   if len(Tree.Children) > 0:
      Tree = Tree.Children[0]
   else:
       break

Just replace Tree.Children by what it is really: PathElement.Children, that is the static field Children of the class PathElement:

while True:
   print(Tree.Element)
   if len(PathElement.Children) > 0:
      Tree = PathElement.Children[0] # Tree has always the same value.
   else:
       break

Now, a example of what you can write:

class PathElement:  
    def __init__(self, element):
        self.__element = element
        self.__children = []

    def add_child(self, child):
        self.__children.append(child)

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

    def element(self):
        return self.__element

path = ["a", "b", "c", "d", "e", "f"]

root = PathElement("root")
handler = root
while path:
    child = PathElement(path.pop(0)) # you can put some conditions here, take more elements of path, ...
    handler.add_child(child)
    handler = child

def dfs(node):
    for c in node.children():
        yield c.element()
        yield from dfs(c)

print (list(dfs(root)))
# a b c d e f

Wow! great answer, actually I managed to solve the problem using "dirty" hack by adding to addChild method this line before appending : self.Children = list(self.Children) . However now I understand what was going on, and yes when I was writing the code I thought "Why doesn't this work like C trees" :) Thank you so much for the informative answer.

Collectives™ on Stack Overflow

Python recursive object refrence in Tree datastructure

Update:

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Update:

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related