Tipo topológico, mas com um certo tipo de agrupamento

Question

Parece que este deve ser um problema comum de agendamento, mas não vejo a solução ou mesmo como chamar o problema. É como um tipo topológico, mas diferente ...

Dadas algumas dependências, digamos

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

pode haver várias soluções para uma classificação topológica:

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

são as duas soluções.

Preciso de um algoritmo que retorne isso:

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

Ou seja, faça A, depois todos B e C e, então, você pode fazer D. Todas as ambigüidades ou desatenção são agrupadas.

Acho que algoritmos como aqueles em Topological Sort with Grouping não tratam casos corretamente como o seguinte.

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

Para isso, o algoritmo deve retornar

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

Este

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

deve retornar

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

Enquanto isso

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

deve retornar

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

E isso

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

deve retornar

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

Existe um nome e uma solução convencional para este problema? (E os algoritmos postados em Topological Sort with Grouping lidam com isso corretamente?)

Edite para responder a solicitações de mais exemplos:

A->B->C
A->C 

deve retornar

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

E

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

deve retornar

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

E

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

deve retornar

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

Answer 1

Seja G o fechamento transitivo do gráfico.Seja G 'o gráfico não direcionado que resulta da remoção da orientação de G e da obtenção do complemento.Os componentes conectados do G 'são os conjuntos que você está procurando.