Ordinamento topologico, ma con un certo tipo di raggruppamento

Question

Sembra che questo debba essere un problema di pianificazione comune, ma non vedo la soluzione o nemmeno come chiamare il problema. È come un ordinamento topologico, ma diverso ...

Date alcune dipendenze, ad esempio

A -> B -> D -- that is, A must come before B, which must come before D
A -> C -> D

potrebbero esserci più soluzioni a un ordinamento topologico:

    A, B, C, D
and A, C, B, D

sono entrambe le soluzioni.

Ho bisogno di un algoritmo che restituisca questo:

(A) -> (B,C) -> (D)

Cioè, fai A, poi tutto B e C, poi puoi fare D. Tutte le ambiguità o le preoccupazioni sono raggruppate.

Penso che algoritmi come quelli in Ordinamento topologico con raggruppamento non gestiscano correttamente i casi come il seguente.

A -> B -> C -> D -> E
A - - - > M - - - > E

Per questo, l'algoritmo dovrebbe restituire

(A) -> (B, C, D, M) -> (E)

Questo

A -> B -> D -> F
A -> C -> E -> F

dovrebbe tornare

(A) -> (B, D, C, E) -> (F)

Mentre questo

A -> B -> D -> F
A -> C -> E -> F
     C -> D
     B -> E

dovrebbe tornare

(A) -> (B, C) -> (D, E) -> (F)    

E questo

A -> B -> D -> F
A -> C -> E -> F
A -> L -> M -> F
     C -> D
     C -> M
     B -> E
     B -> M
     L -> D
     L -> E

dovrebbe tornare

(A) -> (B, C, L) -> (D, E, M) -> (F)    

C'è un nome e una soluzione convenzionale a questo problema? (E gli algoritmi pubblicati su Ordinamento topologico con raggruppamento lo gestiscono correttamente?)

Modifica per rispondere alle richieste di ulteriori esempi:

A->B->C
A->C 

dovrebbe tornare

(A) -> (B) -> (C). That would be a straight topological sort.

e

A->B->D
A->C->D
A->D

dovrebbe tornare

(A) -> (B, C) -> (D)

e

A->B->C
A->C
A->D

dovrebbe tornare

(A) -> (B,C,D)

Answer 1

Sia G la chiusura transitiva del grafo.Sia G 'il grafo non orientato che risulta dalla rimozione dell'orientamento da G e dall'assunzione del complemento.I componenti collegati di G 'sono i set che stai cercando.