I have this problem, not sure there is a name for it, wherein a Directed Acyclic Graph has different colored nodes. The idea is to partition it into minimum number of subgraphs with the following 2 constraints:-
- A sub-graph should have nodes of similar color
- A sub-graph cannot directly or indirectly depend on it’s own output
Example:- In the attached picture, the sub-graph with yellow nodes is invalid since input from the red node breaks rule#2 : 4th node from top has an input which depends on output of 2nd node – via the red node (outside the subgraph) Hence the algorithm should partition it after #2 or #3 so that 2 and 4 are on different nodes
Am sure this is a pretty common problem in Graph theory and must have a name and a standard algorithm for it. Thanks in advance for any pointers to it!