sorte topologiques, mais avec un certain type de groupement

Question

Il semble que cela doit être un problème de planification commune, mais je ne vois pas la solution ou même ce qu'il faut appeler le problème. Il est comme une sorte topologique, mais différent ....

Compte tenu de certaines dépendances, par exemple

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

il peut y avoir plusieurs solutions à une sorte topologique:

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

sont les deux solutions.

je besoin d'un algorithme qui renvoie cette:

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

C'est, faire A, tous B et C, vous pouvez le faire D. Toutes les ambiguïtés ou ne-soins sont regroupés.

Je pense que des algorithmes tels que ceux topologiques Trier avec le regroupement ne sera pas gérer correctement les cas comme ce qui suit.

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

Pour cela, l'algorithme doit retourner

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

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

devrait revenir

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

Bien que cela

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

devrait revenir

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

Ce

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

devrait revenir

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

Y at-il un nom et une solution classique à ce problème? (Et ne les algorithmes affichés topologiques Trier avec le regroupement gérer correctement ce?)

Modifier les demandes de réponse pour d'autres exemples:

A->B->C
A->C 

devrait revenir

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

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

devrait revenir

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

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

devrait revenir

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

Answer 1

Soit G la fermeture transitive du graphe. Soit G » le graphe non orienté qui résulte de la suppression de l'orientation de G et en prenant le complément. Les composantes connexes du G » sont les jeux que vous recherchez.