Tipo topológico, pero con cierto tipo de agrupación

Question

Parece que este debe ser un problema de programación común, pero no veo la solución ni cómo llamar al problema. Es como un tipo topológico, pero diferente ...

Dadas algunas dependencias, digamos

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

Puede haber varias soluciones para una clasificación topológica:

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

son ambas soluciones.

Necesito un algoritmo que devuelva esto:

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

Es decir, haz A, luego todo B y C, luego puedes hacer D. Todas las ambigüedades o no importa están agrupadas.

Creo que algoritmos como los de Orden topológico con agrupación no manejarán correctamente los casos como el siguiente.

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

Para esto, el algoritmo debería regresar

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

Esto

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

debería volver

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

Mientras esto

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

debería volver

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

Y esto

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

debería volver

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

¿Existe un nombre y una solución convencional para este problema? (¿Y los algoritmos publicados en Topological Sort with Grouping manejan esto correctamente?)

Edite para responder a solicitudes de más ejemplos:

A->B->C
A->C 

debería volver

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

Y

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

debería volver

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

Y

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

debería volver

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

Answer 1

Sea G el cierre transitivo del gráfico.Sea G 'el gráfico no dirigido que resulta de quitar la orientación de G y tomar el complemento.Los componentes conectados del G 'son los conjuntos que está buscando.