Topologische Sortierung, jedoch mit einer bestimmten Gruppierung

Question

Es scheint, dass dies ein häufiges Planungsproblem sein muss, aber ich sehe keine Lösung oder gar keine Bezeichnung für das Problem. Es ist wie eine topologische Art, aber anders ...

Bei einigen Abhängigkeiten sagen wir

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

Für eine topologische Sortierung gibt es möglicherweise mehrere Lösungen:

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

sind beide Lösungen.

Ich benötige einen Algorithmus, der Folgendes zurückgibt:

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

Das heißt, machen Sie A, dann alle B und C, dann können Sie D. Alle Ambiguitäten oder Nicht-Sorgen sind gruppiert.

Ich denke, dass Algorithmen wie die unter Topologische Sortierung mit Gruppierung Fälle nicht korrekt behandeln wie folgt.

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

Dazu sollte der Algorithmus zurückgeben

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

Dies

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

sollte zurückgeben

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

Währenddessen

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

sollte zurückgeben

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

Und das

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

sollte zurückgeben

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

Gibt es einen Namen und eine herkömmliche Lösung für dieses Problem? (Und behandeln die unter Topologische Sortierung mit Gruppierung veröffentlichten Algorithmen dies korrekt?)

Bearbeiten, um Anfragen nach weiteren Beispielen zu beantworten:

A->B->C
A->C 

sollte zurückgeben

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

Und

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

sollte zurückgeben

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

Und

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

sollte zurückgeben

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

Answer 1

Sei G der transitive Abschluss des Graphen.Sei G 'der ungerichtete Graph, der sich aus dem Entfernen der Orientierung von G und dem Nehmen des Komplements ergibt.Die verbundenen Komponenten des G 'sind die Sets, nach denen Sie suchen.