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

对树求和,叶节点中有值,父节点中有小计,直到根

graph-theory python

-5

xtian · 技术社区 · 6 年前

是否有一个现成的解决方案来对n元树的所有叶节点求和,并将求和一直分配给它们的父节点直到根节点?

让我解释一下。我每周收到几份报告。它是一个财务文档,本质上是一个不平衡的分层数据集,多达九个层次。值仅在最后一级分配,但每个父级都有其子级的总和(即仅相隔1个边)。

它看起来像:

root:
    sectionA:
        sectionB:
            sectionC:
                sectionD:
                    subtotal sectionE = sum of x 
                        leaf-1 = x_1
                        leaf-2 = x_2
                        leaf-n = x_n

我正在自动验证这个数据集。我需要把每片叶子加起来,确定它是否匹配 父小计 一直到 根总计 .

另外,我还有一个表,列出了所有叶元素及其父关系。像这样的:

root:sectionA:sectionB:sectionC:sectionD:sectionE:leaf

我认为k元树可以表示从表2生成的正确报告结构。然后使用树与周报进行比较。我喜欢这个方向,因为第二个表在这个表单中有结构数据(完整的父路径)。接下来,当我的脚本完成时,我需要概括解决方案。

有没有一个Python模块或通用算法来解决这个问题?

下面是一个示例解决方案, Sum of all elements of N-ary Tree . 但是这个解决方案假设每个节点都有一个唯一的值,而边只是关系。

1 回复 | 直到 6 年前

xtian 6 年前

在这激动人心的反应之后鼓励我在 NetworkX .

通过研究文档和其他各种来源,我了解到 和树问题 ( 根“amount”值是其每个子级的“amount”属性的总和 )在野外并不常见——对其他人来说很明显。

对于以后发现这一点的人,这里有一个概要的解决方案。我用熊猫做了如下的图表。

创建查询结果的DF。
Munge DF(删除未使用的行、列)。
标题和DF列的基本文本规范化
显式编辑DF行中的节点标签异常。
父、子标签发现的条件DF。
在与根的水平距离增加的情况下,将DF分成块。
创建基图。
更新基图;使用#6添加父边和子边
使用节点值更新图形。
与每个父节点的子节点值之和相比,验证每个父节点的分配值, recursively with a little help from my friends .

使用NetworkX从不同输入创建树的两个有用提示

为什么G不是树?几种推荐的图形检查方法( nx.is_connected(G) , nx.connected_component_subgraphs(G) )导致此错误: NetworkXNotImplemented: not implemented for directed type . (步骤10需要有向图)。一种附加方法( list(nx.isolates(G)) )不产生错误,但总是产生空列表。

此树的最终图形生成解决方案使用了两种技术来确保图形是树:

通过向公共静态定义的基图添加节点来构建图。

利用更多的列数据将输入DF分块,从根开始增加级别。

最后一点不是从该数据创建树的要求,因为输入数据已经具有树结构。但是,调试结果卷中的节点标签是必要的。更新DF对于图是不必要的,但是对于以后的调试和识别标签异常值是有用的。

所有异常情况都是源数据中名称不一致的。源数据更改,因此这将继续是一个问题,在寻找未来的解决方案。