如何识别图形中未连接的兄弟姐妹？

Question

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

​

我想识别这个图中满足以下条件的所有这样的节点组：

• 组中没有一个节点彼此连接。
• 组中的节点具有完全相同的父节点和子节点集。

例如，下面的一组节点将从上面的图中获得：

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

第2组：{16，17}

第3组：{19，20}

第4组：{21，22}

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

谢谢

Answer 1

注意，第一个请求是多余的，因为第二个请求包含它。对于两个连接节点，不可能有相同的父母和子集合。对于连接节点，一个节点在父集中具有另一个节点，在子集合中具有相反的节点。

因此，同一组中的节点具有相同的父节点和子节点集。在python中，有一个简单的解决方案，通过对父集和子集来实现dict索引。我不知道它有多有效，但值得一试。

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无关。

Answer 2

为我的问题提供了一个优雅的解决方案。我稍微修改了他的代码，以便在Python3.5中与networkx图一起使用

给出了有向无圈图G.

lineage = defaultdict(list)
for node in G.nodes():
    lineage[frozenset(G.predecessors(node)), frozenset(G.successors(node))].append(node)
for i in lineage.values():
    if len(i) > 1:
        print (i)  # a list containing the groups defined in the question

再次感谢堆栈溢出！