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

Question

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

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

None 一组中的节点相互连接
组中的节点具有完全相同的父子节点集

例如，将从上图中得到以下节点组：

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

第 2 组：{16、17}

第 3 组：{19, 20}

第 4 组：{21, 22}

我有成千上万个这样的图（有些有 10k 个节点）。我在 Python 中使用 networkx.

寻找一种有效的算法来执行此操作

谢谢

Answer 1

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

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

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

Ante 为我的问题提供了一个优雅的解决方案。我稍微修改了他的代码，以便在 Python 3.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

再次感谢 Stack Overflow！

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

How to identify unconnected siblings in a graph?

python

graph-theory

nodes

networkx

graph-algorithm