How to identify unconnected siblings in a graph?
<p>I have a directed acyclic graph as shown in the figure below.
<a href="http://i.stack.imgur.com/6NuA5.png" rel="nofollow"><img src="http://i.stack.imgur.com/6NuA5.png" alt="GRAPH WITH SIBLING NODES"></a></p>

<p>I want to identify all such group of nodes in this graph that satisfy following conditions:</p>

<ul>
<li><p>None of the nodes in a group are connected to each other</p></li>
<li><p>Nodes in a group have exactly same set of parent and children nodes</p></li>
</ul>

<p>For example, following group of nodes will be obtained from the above graph:</p>

<p>Group 1: {3, 4, 5, 6, 7, 8}</p>

<p>Group 2: {16, 17}</p>

<p>Group 3: {19, 20}</p>

<p>Group 4: {21, 22}</p>

<p>I have thousands of such graphs (some with as large as 10k nodes). I'm looking for an efficient algorithm for doing this in Python using networkx.</p>

<p>Thanks</p>

<p>Note that first request is redundant because second request covers it. It is not possible to have same set of parents and children for two connected nodes. For connected nodes, one node has other node in parent set and vice verse in children set.</p>

<p>So nodes in same group have same set of parent and children nodes. In python there is a simple solution implemented with dict indexing by pair of parent and children sets. I am not sure how efficient it is, but it is worth a try.</p>

<pre><code>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) &gt; 1:
        print s
</code></pre>

<p>From image, group {11, 12} is not a result. 11 is not connected to 13.</p>

python nodes graph-theory graph-algorithm networkx