It seems that this should be a general planning problem, but I do not see a solution or even what can be called a problem. This is similar to topological sorting, but different ....
Given some dependencies, let's say
A -> B -> D -- that is, A must come before B, which must come before D A -> C -> D
there can be several solutions of topological type:
A, B, C, D and A, C, B, D
- both solutions.
I need an algorithm that returns this:
(A) -> (B,C) -> (D)
That is, do A, then all B and C, then you can do D. All ambiguities or immutable are grouped.
I think that algorithms such as Grouped Topological Sort will not correctly handle cases like the following.
A -> B -> C -> D -> E A - - - > M - - - > E
To do this, the algorithm must return
(A) -> (B, C, D, M) -> (E)
it
A -> B -> D -> F A -> C -> E -> F
must return
(A) -> (B, D, C, E) -> (F)
So far this
A -> B -> D -> F A -> C -> E -> F C -> D B -> E
must return
(A) -> (B, C) -> (D, E) -> (F)
And this one
A -> B -> D -> F A -> C -> E -> F A -> L -> M -> F C -> D C -> M B -> E B -> M L -> D L -> E
must return
(A) -> (B, C, L) -> (D, E, M) -> (F)
Is there a name and a usual solution to this problem? (And execute the algorithms placed in Topological sorting with grouping , will you handle this correctly?)
Modify the responses to requests for additional examples:
A->B->C A->C
must return
(A) -> (B) -> (C). That would be a straight topological sort.
AND
A->B->D A->C->D A->D
must return
(A) -> (B, C) -> (D)
and
A->B->C A->C A->D
must return
(A) -> (B,C,D)