代码之家 › 专栏 › 技术社区 › xtian

我有一个递归函数来验证树图,需要一个返回条件

networkx recursion python

xtian · 技术社区 · 8 年前

根“amount”值是其每个子级的“amount”属性的总和。

下面是一个玩具示例,如图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)

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')

运行该函数,将得到以下结果:

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

如果在有效树上运行该函数, validateTree()

1 回复 | 直到 8 年前

CtheSky 8 年前

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

递归构造结果
使用全局变量记录
结果引发异常

以及递归构造结果的示例,这里,函数返回一个布尔值,并按逻辑和组合子级的结果:

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

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

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)

定义自定义异常类,并在树无效时引发该类: 类TreeNotValidException(异常): 通过

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)