How to identify unrelated siblings in a graph?

Question

I have a directed acyclic graph, as shown in the image below.

I want to identify the entire group of nodes on this graph that satisfy the following conditions:

• None of the nodes in the group are connected to each other.

• Nodes in a group have exactly the same set of parent and child nodes

For example, the following group of nodes will be obtained from the above graph:

Group 1: {3, 4, 5, 6, 7, 8}

Group 2: {16, 17}

Group 3: {19, 20}

Group 4: {21, 22}

I have thousands of such graphs (some with 10k nodes). I am looking for an efficient algorithm for this in Python using networkx.

thank

Answer 1

, , . . node node .

, . 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 . , networkx Python 3.5

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!