Как идентифицировать несвязанных братьев и сестер в графе?

Question

У меня есть ориентированный ациклический график, как показано на рисунке ниже.

Я хочу, чтобы идентифицировать все такие группы узлов в этом графике, которые удовлетворяют следующим условиям:

• Ни один из узлов в группе не будут соединены друг с другом

• узлов в группа имеет точно такой же набор родительских и детских узлов

Например, следующая группа узлов будут получены из приведенного выше графика:

Группа 1: {3, 4, 5, 6, 7, 8}

Группа 2: {16, 17}

Группа 3: {19, 20}

Группа 4: {21, 22}

у меня тысячи таких графиков (некоторые с такого размера, как 10k узлов). Я ищу эффективный алгоритм для этого в Python с помощью networkx.

Благодаря

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

Ante предоставил изящное решение моего вопроса. Я изменил код, который будет мало использовать для использования с сетевыми графиками в Python 3.5

0 Адаптивный ациклический граф 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 

Еще раз спасибо переполнение стека!