I have a recursive function to validate tree graph and need a return condition

I have a tree graph. Each node has attribute 'amount'. The rule governing the attribute value of root is this,

The root 'amount' value is the sum of the 'amount' attribute of each of it's children.

This continues to the last node with children. In other words this tree's attributes are unlike a sum tree, because the root node is not the sum of each node in the tree.

Here is a toy example as graph G:

nodedict = 'apples': 'amount': 5.0,
'bananas': 'amount': 10.0,
'tomato': 'amount': 50.0,
'total_fruits': 'amount': 15.0,
'total_vegetables': 'amount': 9.0,
'carrot': 'amount': 3.0,
'squash': 'amount': 6.0,
'total_fruits_and_vegetables': 'amount': 74.0

edgelist = [('total_fruits', 'apples'),
('total_fruits', 'bananas'),
('total_fruits_and_vegetables', 'tomato'),
('total_fruits_and_vegetables', 'total_fruits'),
('total_fruits_and_vegetables', 'total_vegetables'),
('total_vegetables', 'carrot'),
('total_vegetables', 'squash')]

G = nx.DiGraph(edgelist)
nx.set_node_attributes(G, nodedict)


I've written a recursive function to validate the tree's sum rule. The output indicates all nodes in the tree are reached by the function; However, I can't think of how to exit the function with a final return statement.

def isLeaf(G, node):
return G.out_degree(node)==0 and G.in_degree(node)==1


def testParentSumChildren(M, node):
children = list(G.successors(node))
vals =
for child in children:
vals.append(G.nodes[child]['amount'])

sumchildrenval = round(sum(vals), 2)
parentval = round(G.nodes[node]['amount'], 2)

# Valid difference between -1 and 1
if -1.0 <= round(parentval - sumchildrenval, 2) <= 1.0:
return True
else:
print("Not Valid Sum.")


def _validateTree(G, node):
children = list(G.successors(node))
if children:
vals =
for child in children:
if isLeaf(G, child):
# Prevents recursion on child without children
print("is leaf %s" % (child, ))
else:
# Test parent nodes
if testParentSumChildren(G, child):
print("Valid Sum.")
_validateTree(G, child)
else:
print("Not Valid Sum.")

def validateTree(G, root):
if _validateTree(G, root):
return True
else:
print("Not Valid Tree.")


validateTree(G, root='total_fruits_and_vegetables')


Running the function, you get these results:

is leaf tomato
Valid Sum.
is leaf apples
is leaf bananas
Valid Sum.
is leaf carrot
is leaf squash
Not Valid


If you run the function on a valid tree, validateTree() should return True.

validateTree()

1 Answer
1

To report the final result, you could combine the validate results of subtrees and current node, so the recursive procedure will look like:

How to collect and record results depends on the situation, there are some options:

Example 1

And example for constructing result recursively, here the function return a boolean value and combines result of children by logical and:

def validate(G, node):
if isLeaf(G, node): # This is the base case
return True
else:
# step 1
validate_results_of_children = [validate(G, child) for child in G.successors(node)]

# step 2
is_current_node_valid = check_current_node_sum(G, node)

# step 3
final_result = all(validate_results_of_children) and is_current_node_valid

return final_result


Example 2

Use a global dict to record invalid results and add some extra info about tree level:

def validate(G, node, record_dict, tree_level):
if isLeaf(G, node): # This is the base case
pass
else:
# step 1
for child in G.successors(node):
validate(G, child, record_dict, tree_level + 1)

# step 2
is_current_node_valid = check_current_node_sum(G, node)

# step 3
record_dict.setdefault(tree_level, )
record_dict[tree_level][node] = is_current_node_valid

record_dict =
validate(G, root, record_dict, tree_level=0)


Example 3

Define a custom exception class and raise it when tree is not valid:
class TreeNotValidException(Exception):
pass

def validate(G, node):
if isLeaf(G, node): # This is the base case
pass
else:
# step 1
for child in G.successors(node):
validate(G, child, tree_level + 1)

# step 2
is_current_node_valid = check_current_node_sum(G, node)

# step 3
if not is_current_node_valid:
raise TreeNotValidException("Invalid sum for node : " + node)


isLeaf()

for()

Balsamiq

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.