How to define instantiation of object class as global variable in Python?

Question

I am a starter & want to integrate dfs code with Fibonacci series generating code. The Fibonacci code too runs as dfs, with calls made from left to right. The integration is incomplete still.

I have two issues :
(i) Unable to update 'path' correctly in fib(), as the output is not correctly depicting that.

(ii) Stated in fib() function below, as comment.

P.S.

Have one more issue that is concerned with program's working:

(iii) On modifying line #16 to: stack = root = stack[1:]; get the same output as before.

import sys
count = 0
root_counter = 0
#path=1
inf = -1
node_counter = 0
root =0

def get_depth_first_nodes(root):
    nodes = []
    stack = [root]
    while stack:
        cur_node = stack[0]
        stack = stack[1:]
        nodes.append(cur_node)        
        for child in cur_node.get_rev_children():
            stack.insert(0, child)
    return nodes

def node_counter_inc():
     global node_counter
     node_counter = node_counter + 1

class Node(object):
    def __init__(self, id_,path):
        self.id = node_counter_inc() 
        self.children = []
        self.val = inf #On instantiation, val = -1, filled bottom up; 
                       #except for leaf nodes
        self.path = path                
    def __repr__(self):
        return "Node: [%s]" % self.id     
    def add_child(self, node):
        self.children.append(node)     
    def get_children(self):
        return self.children        
    def get_rev_children(self):
        children = self.children[:]
        children.reverse()
        return children        

def fib(n, level, val, path):
    global count, root_counter, root
    print('count :', count, 'n:', n, 'dfs-path:', path)
    count += 1
    if n == 0 or n == 1:
        path = path+1
        root.add_child(Node(n, path))
        return n
    if root_counter == 0:
        root = Node(n, path)
        root_counter = 1
    else:
        #cur_node.add_child(Node(n, path)) -- discarded for next(new) line
        root.add_child(Node(n, path))   
    tmp = fib(n-1, level + 1,inf, path) + fib(n-2, level + 1,inf,path+1)
    #Issue 2: Need update node's val field with tmp.  
    #So, need suitable functions in Node() class for that.
    print('tmp:', tmp, 'level', level)
    return tmp

def test_depth_first_nodes():
     fib(n,0,-1,1)  
     node_list = get_depth_first_nodes(root)
     for node in node_list:
         print(str(node))

if __name__ == "__main__":
     n = int(input("Enter value of 'n': ")) 
     test_depth_first_nodes()

Want to add that took idea for code from here.

Siong Thye Goh · Accepted Answer · 2018-12-29 19:40:04Z

1

Answer to the first question:

Path in this particular question is an int. It is a numbering of path from the root to a leaf in a greedy dfs manner.

This can be achieved by letting path be a global variable rather than an input to fib function. We increment the path count whenever we reach a leaf.

I have also modified the fib function to returns a node rather than a number.

import sys
count = 0
root_counter = 0
path=1
inf = -1
node_counter = 0
root = None

def node_counter_inc():
     global node_counter
     node_counter = node_counter + 1
     print("node_counter:", node_counter)
     return node_counter   

class Node(object):
    def __init__(self, id__,path):
        print("calling node_counter_inc() for node:", n )
        try:
            self.id = int(node_counter_inc())
        except TypeError:
            self.id = 0  # or whatever you want to do

        #self.id = int(node_counter_inc())
        self.val = inf #On instantiation, val = -1, filled bottom up; 
                       #except for leaf nodes
        self.path = path
        self.left = None
        self.right = None

    def __repr__(self):
        return "Node" + str(self.id) + ":"+ str(self.val)          


def fib(n, level, val):
    # make fib returns a node rather than a value
    global count, root_counter, root, path
    print('count :', count, 'n:', n, 'dfs-path:', path)
    count += 1
    if n == 0 or n == 1:
        path = path+1
        new_Node = Node(n, path)
        new_Node.val = n
        return new_Node
        #root.add_child(new_Node)
    #    return new_node
    #if root_counter == 0:
    #   root = Node(n, path)
    #   root_counter = 1
    #else:
        #cur_node.add_child(Node(n, path)) -- discarded for next(new) line
    #    root.add_child(Node(n, path))   
    #tmp = fib(n-1, level + 1,inf) + fib(n-2, level + 1,inf)

    #Issue 2: Need update node's val field with tmp.  
    #So, need suitable functions in Node() class for that.
    #print('tmp:', tmp, 'level', level)
    #return tmp
    ans = Node(n, path)
    ans.left = fib(n-1, level + 1, inf)
    ans.right = fib(n-2, level + 1, inf)
    ans.val = ans.left.val + ans.right.val
    print("the node is", ans.id, "with left child", ans.left.id, "and right child", ans.right.id)
    print("the corresponding values are",  ans.val, ans.left.val, ans.right.val)
    return ans

def test_depth_first_nodes():
     ans = fib(n,0,-1)
     print("The answer is", ans.val)
     #node_list = get_depth_first_nodes(root)
     #for node in node_list:
     #    print(str(node))

if __name__ == "__main__":
     n = int(input("Enter value of 'n': ")) 
     test_depth_first_nodes()

edited Dec 29, 2018 at 19:40

answered Dec 28, 2018 at 7:05

Siong Thye Goh

3,58410 gold badges27 silver badges33 bronze badges

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

10 Comments

jiten Over a year ago

Thanks a lot for telling the correct terminology (greedy dfs) to determine path's definition. Thanks for detecting that except root there is no child for any other node, even though it is obvious that tree is traversed. I took a modified version of your program to confirm this at: py3.codeskulptor.org/#user303_ICGby3gUhO_0.py. But not clear as how to have children without either having a separate array for child for each node, or a multi-dimensional array. Request impl. for the same too.

jiten Over a year ago

Sorry, for wrong multi-line commenting in above code, the correct code is : py3.codeskulptor.org/#user303_ICGby3gUhO_1.py. Thanks a lot for changing fib() to retturn node. This hopefully will help in filling up lists/dictionary for each node's children (a deficiency in my code design, where based on traversal, only one list of chidren attached to root was filled during dfs traversal) for help in searching by keyword (chosen simply as node-id, or better node-id+level; which I hope should be enough to uniquely identify, but could not prove that).

jiten Over a year ago

A crispy version of my earlier stated file (no unnecessary print() used) is at: codeskulptor.org/#user45_QH07Txnu6p_3.py.

jiten Over a year ago

I have copied your code, and tried to modify it as at: py3.codeskulptor.org/#user303_uGbYL5xufK_17.py, but unable to get proper output. Please join the old chatroom: chat.stackexchange.com/rooms/89042/….

jiten Over a year ago

Even better version of my code: py3.codeskulptor.org/#user303_uGbYL5xufK_26.py, that also explains as comment in > def get_depth_first_nodes(cur_node). Please join chatroom. Even discussion helps me to think better.

|

Collectives™ on Stack Overflow

How to define instantiation of object class as global variable in Python?

1 Answer 1

10 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

10 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related