Ordinamento topologico, ma con un certo tipo di raggruppamento
-
27-10-2019 - |
Domanda
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)
Soluzione
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.