I have a large directed graph with cycles (a control-flow-graph from a large program). I want to group the nodes such that each group would contain nodes independent to each other. Two nodes A and B are independent to each other if there is no path from node A to node B or node B to node A. That is, once A has been executed, it guarantees that B will not be. Similarly, once B has been executed, A can not be executed. Is there an efficient algorithm to do this?
The trivial algorithm here is to start by picking a node A, remove all nodes reachable from it, then transpose the graph, and remove all nodes that are again reachable from A, pick one from the remaining. Remove nodes reachable from it, transpose, and remove everything reachable from it. Continue until all nodes are exhausted. Start over again with remaining nodes (with suitable caching of reachability).
If this question is off-topic here, I would also be glad to be pointed to the right SO community.
I found this question related, but in my case, existence of a path from A to B does not mean a B to A path exists. Hence, they need not be strongly connected. This question is also similar, but talks about having nodes without edge connection rather than path connection.
Example abs_value()
The groups here are (1),(2), (3,5), (6), (7)
Example factorial()
The groups here are: (1), (2), (3,5), (3,6,8), (3,6,9,11), (3,6,9,12),(3,6,9,13), (3,6,9,14), (3,6,9,16), (17)
You may end to the up with a great many "groups", with each node present in multiple groups.
Example, a graph with three nodes A, B and C.
Links: B -> C and C -> B
The "groups" are ( A,B ) and ( A, C )
Is this really what you want? It is hard to imagine what purpose this might serve.
In the case of a larger graph that happens to be bipartite, you will need a group for every distinct pair where one node is in one part and the other in the other part.
Since this is a control flow graph, every node is independent of every node higher in the call hierarchy, and every node in a different calling tree.