在python中查找顶级父母的所有孩子 [英] Find all children of top parent in python

问题描述

我有一个父子关系列表，其中结构不是真正的树.有些父母可以有很多孩子，也有些孩子可以有不止一个父母.

I have a list of parent-child relations where the structure isn't a true tree. Some parents can have many children and also some children can have more than one parent.

import pandas as pd    
df = pd.DataFrame([[123,234],[123,235],[123,236],[124,236],[234,345],[236,346]], columns=['Parent','Child'])*

我想将所有孩子分组为特定祖先.来自数据:

I would like to group all children for specific ancestors. From the data:

123,234,235,236,345,346
124,235,346

应该是正确的组.

我尝试过:

parents = set()
children = {}
for p, c in df.to_records(index=False).tolist():
    parents.add(p)
    children[c] = p


def getAncestors(p):
    return (getAncestors(children[p]) if p in children else []) + [p]

但是在 346 上它只返回一组.

But on 346 it only returns one group.

另外，如何找到 123 和 124 的所有孩子?

Also, how to then find all children for 123 and 124?

谢谢！

推荐答案

正如你所说，它并不是真正的树，而更像是一个有向无环图，所以你不能将每个孩子映射到一个父母；它必须是父母的名单.另外，考虑到您的用例，我建议将父项映射到他们的子项列表.

As you said, it's not really a tree, but more like a directed acyclic graph, so you can't map each child to just one parent; it'd have to be a list of parents. Also, given your use case, I'd suggest mapping parents to their lists of children instead.

relations = [[123,234],[234,345],[123,235],[123,236],[124,236],[236,346]]

children = {}
for p, c in relations:
    children.setdefault(p, []).append(c)
roots = set(children) - set(c for cc in children.values() for c in cc)

然后您可以使用类似于您已经拥有的递归函数将所有子节点带到给定的根节点(或任何父节点).根目录本身不在列表中，但可以轻松添加.

You can then use a recursive function similar to the one you already have to get all the children to a given root node (or any parent node). The root itself is not in the list, but can easily be added.

def all_children(p):
    if p not in children:
        return set()
    return set(children[p] + [b for a in children[p] for b in all_children(a)])

print({p: all_children(p) for p in roots})
# {123: {234, 235, 236, 345, 346}, 124: {346, 236}}

这篇关于在python中查找顶级父母的所有孩子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！