I have a directed graph, $G = (V,E)$ (a dependency graph actually) and I want to find groups of nodes that can be considered as a single unit.

I define a group as a set of nodes, $A$, such that any node outside of the group, $v \in A^c$, that has an edge to a node inside, must have an edge to every other member of the group:

if $\exists u \in A: (u,v) \in E$ then $|\{\ (v,w)\ |\ \forall w \in A\ \wedge\ (v,w) \in E\ \}| = |A|$

Once groups are found, then a merge can be made, i.e. add a node $u'$ in G and for all edges from $v \in A^c$ to $u \in A,$ make an edge from $v$ to $u'$. Finally, remove all original nodes and corresponding edges in G, thus constructing a reduced graph.

This is similar to reducing a state machine.


closed as unclear what you're asking by D.W. Feb 2 '18 at 17:24

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ The set $V$ satisfies this condition. $\endgroup$ – Yuval Filmus Feb 2 '18 at 15:07
  • $\begingroup$ Sounds like you want a modular decomposition. $\endgroup$ – András Salamon Feb 2 '18 at 16:53
  • $\begingroup$ Given Yuval Filmus's comment, I suspect there is some additional requirement you haven't told us. Can you specify the problem more precisely? The input is a directed graph $G$. What is the desired output? Is the desired output a group, any group? Is it a list of all possible groups? Is it a partition of the nodes into groups? Something else? Please edit the question to clarify the problem statement, then this can be considered for re-opening at that time. Thank you! $\endgroup$ – D.W. Feb 2 '18 at 17:24
  • $\begingroup$ @D.W. Added a clarification on what i want to achieve. But the gist is basically a reduced graph $\endgroup$ – Artog Feb 5 '18 at 11:22
  • $\begingroup$ I don't see how this addresses the feedback. As Yuval says, the set $A=V$ satisfies the condition. And your edits don't answer my questions about what you want if there are multiple possible ways to choose a set $A$ (any arbitrary solution? all of them? the smallest? something else?). Incidentally, I notice that the mathematical condition doesn't seem to match the English statement, because the direction of the edge is swapped. Instead of $(u,v)\in E$ did you mean $(v,u) \in E$? $\endgroup$ – D.W. Feb 5 '18 at 16:45