In the meantime I came up with some heuristic solutions. My algorithm goes as follows:

• First find all of the trivial nodes in the graph. This is kind of a simplification step. With trivial nodes I mean the group of nodes with the same type/colour that can be trivially grouped together without problem. These can be found using Strongly Connected Components (https://en.wikipedia.org/wiki/Strongly_connected_component). So first we group all the nodes together of the same type. Then we find the Strongly Connected Components in that grouped graph. Now we can see that alle the Strongly Connected Components with only 1 node inside correspond to the trivial nodes of the original graph

• Next we still have to solve the non-trivial groups. Here I tried a couple of approaches

Approach 1:

• This the same approach as in the original suggestion

• Start from the topologically sorted graph. Where the trivial nodes are already grouped

• Iterate over all the nodes starting from the root node

  • Try to add the node to the last subgraph of that colour

  • Check if that node has any connection to nodes outside the current subgraph. If so, check that we don't introduce any cycle. If we don't create any cycle, merge the node together with the subgraph. The cycle detection can probably be optimised with some incremental cycle detection algorithm

  • If we can't add the node to the current subgraph, we create a new subgraph for that type/colour of node

This approach is heuristic but runs rather quick and gave good enough results

Approach 2:

• Recursive approach:

• Try to find a worst node or collection of bad nodes in the Strongly Connected Components that should be split of first. This can be done with some metrics appropriate for you problem or graph layout

• Split the node with the worst metric into its own group

• Perform another run of Strongly Connected Components detected on the reduced graph and find the new trivial nodes

• Do these steps recursively

This approach is also heuristic and also runs quick. It may be difficult to find a good metric for finding the worst node to cut

Approach 3:

• Travers all the options of the branches that you can take

• Perform smart cutting of the branches to prune most options

This approach will guarantee the correct solution but was cumbersome to get all the pruning conditions correct. In the end I gave up on this approach since the other approaches were much quicker and the results were good enough