未接続の兄弟をグラフで識別する方法は？

Question

私は下図のような有向非循環グラフを持っています。

Iは、以下の条件を満たし、このグラフのノードの全てのこのようなグループを識別する：グループ内のノードの

• どれがAで互いに

• ノードに接続されていませんグループは厳密に同じ親ノードと子ノードのセットを有する

たとえば、次のノードのグループ上のグラフから得られるであろう。

グループ1：{3、4、5、6、7、8}

グループ2：{16、17}

グループ3：{19、 20}

グループ4：{21、22}

私はそのようなグラフの数千（10Kノードと同じ大きさを有するいくつかの）を有します。私は、ネットワークxを使ってPythonでこれを行うための効率的なアルゴリズムを探しています。第2の要求がそれを覆っているので、最初の要求が冗長であること

おかげ

Answer 1

注意。接続された2つのノードには、同じペアの親と子を持つことはできません。接続されたノードの場合、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

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 

ありがとうもう一度スタックオーバーフロー！