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>Ante has provided an elegant solution to my question.
I have modified his code a little to be used with networkx graphs in Python 3.5</p>

<p>Given a  directed acyclic graph <code>G</code>.</p>

<pre><code>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) &gt; 1:
        print (i)  # a list containing the groups defined in the question
</code></pre>

<p>Thank you again Stack Overflow!</p>

python nodes graph-theory graph-algorithm networkx