python - 如何识别图中未连接的 sibling ？

Question

我有一个有向无环图，如下图所示。

我想识别此图中满足以下条件的所有此类节点组:

• 一个组中的所有节点都没有相互连接

• 组中的节点具有完全相同的父子节点集

例如，将从上图中获得以下一组节点:

第 1 组:{3、4、5、6、7、8}

第 2 组:{16、17}

第 3 组:{19、20}

第 4 组:{21、22}

我有成千上万个这样的图(有些有 10k 个节点)。我正在寻找一种使用 networkx 在 Python 中执行此操作的有效算法。

谢谢

Answer 1

请注意，第一个请求是多余的，因为第二个请求涵盖了它。两个连接的节点不可能有同一组 parent 和 child 。对于连接的节点，一个节点在父集中有另一个节点，在子集中反之亦然。

因此同一组中的节点具有相同的父子节点集。在 python 中，有一个简单的解决方案，通过一对父子集的字典索引实现。我不确定它的效率如何，但值得一试。

from collections import defaultdict
children = {
    1: [2, 3, 4, 5, 6, 7, 8],
    2: [3, 4, 5, 6, 7, 8, 9],
    3: [9, 10],
    4: [9, 10],
    5: [9, 10],
    6: [9, 10],
    7: [9, 10],
    8: [9, 10],
    9: [10],
    10: [11, 12, 13],
    11: [14, 15],
    12: [13, 14, 15],
    13: [16, 17],
    14: [16, 17],
    15: [16, 17],
    16: [18],
    17: [18],
    18: [19, 20],
    19: [21, 22],
    20: [21, 22],
    21: [],
    22: [],
}
# Collect parents
parents = defaultdict(list)
for a, bs in children.iteritems():
    for b in bs:
        parents[b].append(a)
# Use default dict to collect nodes that have same parents and children
store = defaultdict(list)
for node in children.iterkeys():
    store[(tuple(sorted(children[node])), tuple(sorted(parents[node])))].append(node)
# Result
for s in store.itervalues():
    if len(s) > 1:
        print s

从图像来看，组 {11, 12} 不是结果。 11 没有连接到 13。