D
Daniel Oberski
Hello all,
I wrote this function to recurse through a tree structure of Nodes
connected by Branches.
I use a local variable seen_nodes to mark off Nodes already seen by the
function (i.e. add them to a list).
What is puzzling me is that the local variable seen_nodes seems to be
made global by Python. That is, Nodes from function calls 'lower' in the
recursion order are still there after return. Even Nodes added by
completely unrelated function calls on a different graph in the same
program are in seen_nodes. This can only mean the variable is global, but
I absolutely did not expect it nor do I understand why that should be.
The solution was to delete seen Nodes before return, so I do not have a
problem with the program. I am just very surprised by this behaviour!
I was wondering if anybody can explain to me why the interpreter should
behave in this way and where this is documented. The complete program
with usage examples as a doctest is listed below.
Thank you very much in advance,
Daniel
----------------- graph.py -------------------
"""
# The null graph:
.... # n1 --> n2 --|
.... # --> n4 --> n5
.... n1 = Node('Start')
"""
# Total number of times the recursive function is_terminal has been
called:
num_calls = 0
class Node:
def __init__(self, name):
self.name = name
self.branches = []
def add(self, branch):
"""Adds a branch to this node."""
self.branches.append(branch)
def is_terminal(self, seen_nodes = []):
"""Recurses from this node to see if *all* its branches eventually
end up in a terminal node. Calling this on the source node of
a
graph establishes that the graph is terminal.
Returns 1 if yes, 0 if no. """
global num_calls # For debugging
num_calls += 1
if self in seen_nodes: # deja vu, we are going in circles
return 0
seen_nodes.append(self)
# unfortunately seen_nodes is automatically made global by the
Python
# interpreter :-(. Instead of using black scoping magic I just
delete self
# from seen_nodes later on.
num_terminal = 0
for branch in self.branches:
if branch.next: # Recurse through this branch
num_terminal += branch.next.is_terminal(seen_nodes)
else: # Found the terminal node ('sink')
num_terminal += 1
# necessary because of Python's weird scoping rules (see above):
seen_nodes.remove(self)
if num_terminal == len(self.branches): # all branches are terminal
return 1
else: # at least one branch is not terminal or no branches
return 0
class Branch:
"""A branch is an edge. It is found in a Node and points to what we
can only
hope is another Node."""
next = False
def __init__(self, next = False):
self.next = next
if __name__ == "__main__":
import doctest
doctest.testmod()
print "is_terminal() was called a total of %d times." % num_calls
I wrote this function to recurse through a tree structure of Nodes
connected by Branches.
I use a local variable seen_nodes to mark off Nodes already seen by the
function (i.e. add them to a list).
What is puzzling me is that the local variable seen_nodes seems to be
made global by Python. That is, Nodes from function calls 'lower' in the
recursion order are still there after return. Even Nodes added by
completely unrelated function calls on a different graph in the same
program are in seen_nodes. This can only mean the variable is global, but
I absolutely did not expect it nor do I understand why that should be.
The solution was to delete seen Nodes before return, so I do not have a
problem with the program. I am just very surprised by this behaviour!
I was wondering if anybody can explain to me why the interpreter should
behave in this way and where this is documented. The complete program
with usage examples as a doctest is listed below.
Thank you very much in advance,
Daniel
----------------- graph.py -------------------
"""
# The null graph:
.... # --> n3
.... # n1 --> n2 --|
.... # --> n4 --> n5
.... n1 = Node('Start')
1
"""
# Total number of times the recursive function is_terminal has been
called:
num_calls = 0
class Node:
def __init__(self, name):
self.name = name
self.branches = []
def add(self, branch):
"""Adds a branch to this node."""
self.branches.append(branch)
def is_terminal(self, seen_nodes = []):
"""Recurses from this node to see if *all* its branches eventually
end up in a terminal node. Calling this on the source node of
a
graph establishes that the graph is terminal.
Returns 1 if yes, 0 if no. """
global num_calls # For debugging
num_calls += 1
if self in seen_nodes: # deja vu, we are going in circles
return 0
seen_nodes.append(self)
# unfortunately seen_nodes is automatically made global by the
Python
# interpreter :-(. Instead of using black scoping magic I just
delete self
# from seen_nodes later on.
num_terminal = 0
for branch in self.branches:
if branch.next: # Recurse through this branch
num_terminal += branch.next.is_terminal(seen_nodes)
else: # Found the terminal node ('sink')
num_terminal += 1
# necessary because of Python's weird scoping rules (see above):
seen_nodes.remove(self)
if num_terminal == len(self.branches): # all branches are terminal
return 1
else: # at least one branch is not terminal or no branches
return 0
class Branch:
"""A branch is an edge. It is found in a Node and points to what we
can only
hope is another Node."""
next = False
def __init__(self, next = False):
self.next = next
if __name__ == "__main__":
import doctest
doctest.testmod()
print "is_terminal() was called a total of %d times." % num_calls
