Python在边缘列表上迭代，对于具有特定属性的节点，查找具有不同特定属性的所有连接节点？

Question

我有一个边缘列表，其中包含产品之间的24000个不同边缘。如果产品B是A的子组件，则在A和B之间创建一条边

边缘列表采用以下格式：

 Parent | Child | Root | Child Meta
  AA1      BB1    AA1      ...  
  AA1      BB2    AA1      ...
  BB2      CC1    AA1      ...  
  AA2      BB3    AA2
  AA2      BB4    AA2
  BB4      CC1    AA2      ... 
  BB4      DD1    AA2      ...
  DD1      EE1    AA2
  DD1      EE2    AA2
  BB4      FF1    AA2
  FF1      GG1    AA2      ...
  GG1      EE3    AA2

因此，通过按Root分组，我希望，对于表DD*和FF*上的所有家长，在表EE*上找到与他们有直接联系的孩子。在上面的示例中，我希望输出数据帧如下所示

 Parent | Child | Root | Child Meta
   DD1     EE1    AA2      ... 
   DD1     EE2    AA2      ...
   FF1     EE3    AA2      ...

我知道如何做到这一点的唯一方法是在pandas数据帧上迭代，并使用递归函数在子项上迭代，直到我找到一个EE*子项。这需要永远。 有没有一种聪明的方法可以在这里使用networkx？或者，有没有其他方法可以让我用熊猫更快地做到这一点

Answer 1

如果我正确理解了这个问题，那么如果从底部开始，发现节点向上移动，速度可能会更快

由于您知道要查找的子项的子集（E*），因此如果从目标子项开始，根据定义，所有父项都是结果的一部分，您不必进行筛选

在一种简单的迭代Python方法中，类似这样的方法可以找到“E*”子节点的所有父节点：

（请注意，我添加了一行额外的“BB3 DD1 AA2”以获得另一个副本。）

data = """AA1      BB1    AA1
  AA1      BB2    AA1 
  BB2      CC1    AA1 
  AA2      BB3    AA2
  AA2      BB4    AA2
  BB4      CC1    AA2 
  BB3      DD1    AA2
  BB4      DD1    AA2
  DD1      EE1    AA2
  DD1      EE2    AA2
  BB4      FF1    AA2
  FF1      GG1    AA2
  GG1      EE3    AA2"""

# tuple (parent, child, root)
tuples = {tuple(l.split()) for l in data.split("\n")}

parentsByChild = {}
for node in tuples:
    p = set(parentsByChild.get(node[1], frozenset()))
    p.add(node)
    parentsByChild[node[1]] = frozenset(p)
# alternatively:
# from itertools import groupby
# parentsByChild = {c:frozenset(nodes) for c, nodes in groupby(sorted(tuples, key=lambda n: n[1]), lambda n: n[1])}

def expand(nodes):
    todo, found = set(nodes), set() 
    while todo:
        node = todo.pop()        
        if not node in found:
            found.add(node)
            todo.update((p for p in parentsByChild.get(node[0], set()) if p not in found))
    return found

leaves = {n for n in tuples if n[1].startswith("E")}
for t in expand(leaves):
    print(t)

这在边的数量上应该是线性的：我们对它们迭代一次以收集元组，第二次对父级进行分组。expand调用迭代所有“感兴趣”的子节点及其父节点，仅为新节点扩展父节点，因此我们不会对同一节点执行两次操作