我有一个递归函数来验证树图并需要一个返回条件 [英] I have a recursive function to validate tree graph and need a return condition

问题描述

我有一个树形图.每个节点都具有数量"属性.控制root属性值的规则是这样

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.

以下是一个玩具示例，如图G:

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)

我编写了一个递归函数来验证树的求和规则.输出表明该功能已到达树中的所有节点.但是，我无法考虑如何使用最终的return语句退出该函数.

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

如果在有效树上运行该函数，则validateTree()应该返回True.

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

推荐答案

要报告最终结果，可以合并子树和当前节点的验证结果，因此递归过程将如下所示: 如何收集和记录结果取决于情况，有一些选择:

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:

1. 以递归方式构造结果
2. 使用全局变量进行记录
3. 结果引发异常

示例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

示例2

使用全局dict记录无效结果并添加有关树级别的一些额外信息:

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)

示例3

定义一个自定义异常类，并在tree无效时引发它: 类TreeNotValidException(Exception): 通过

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)

这篇关于我有一个递归函数来验证树图并需要一个返回条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！