그래프에서 연결되지 않은 형제를 식별하는 방법은 무엇입니까?

Question

다음 그림과 같이 방향 비순환 그래프가 있습니다.

나는 다음과 같은 조건을 만족이 그래프의 모든 노드와 같은 그룹을 식별 할 : 그룹의 노드의

• 없음은 서로

• 노드에 연결되어 있지를 그룹에는 정확히 동일한 부모 및 자식 노드 집합이 있습니다.

예를 들어 다음 노드 그룹

그룹 1 : 상기 그래프로부터 얻어진다 {3, 4, 5, 6, 7, 8}

그룹 2 : {16, 17}

그룹 3 : {19, 20}

그룹 4 : {21, 22}

나는 그런 그래프 수천 (큰 10,000 개의 노드 일부)가 있습니다. 파이썬에서 networkx를 사용하여 이것을 수행하는 효율적인 알고리즘을 찾고있다.

감사합니다.

Answer 1

두 번째 요청에서 다루기 때문에 첫 번째 요청은 중복됩니다. 두 개의 연결된 노드에 대해 동일한 부모 및 자식 집합을 가질 수 없습니다. 연결된 노드의 경우 한 노드는 상위 노드 집합에 다른 노드가 있고 하위 노드 집합에는 다른 노드가 있습니다.

그래서 같은 그룹의 노드는 동일한 상위 노드와 하위 노드 집합을 갖습니다. 파이썬에서는 부모와 자식 세트의 쌍으로 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 

다시 한 번 감사드립니다. 스택 오버플로!