Comparator Topologische Sortierung

Java-Forum Allgemeine Themen
1

Ich möchte einen gerichteten Graphen in eine Eindimensionale Liste bekommen.

Angenommen ich habe 6 Elemente die ich sortieren möchte.

Dafür verwende ich in JAVA einen Comparator, bzw. Comparable. Soweit so klar.

Die Elemente sind wie folgt:

A, B, C, D, E, X

Es gibt einen Pfad von A nach E. Es bestehen genügend Informationen um dass Sortieren zu können. (A => B => C => D => E)
Es gibt einen weiteren Pfad von A über X nach E.

Ich wäre also mit jeder Kombination

A, x, B, C, D, E
A, B, x, C, D, E
A, B, C, x, D, E
A, B, C, D,x, E

zufrieden.

Für Vergleiche zwischen B, C, D mit X gebe ich 0 zurück.

Jetzt habe ich folgenden Effekt, wenn die Reihenfolge des Hinzufügens/Sortierens so aussieht.
+C => C
+D => C,D
+E => C,D,E
+X => D.compareTo(X) == 0 => C,X,D,E // Wäre noch in Ordnung.
+B => B.compareTo(X) == 0 => C,B,X,D,E // Problem, da B nach C einsortiert wird.
+A => A,C,B,X,D,E

Das Problem beim Comparator ist, dass ich 0 zurückgebe, wenn mangelnde Informationen vorliegen. 0 wird als Gleichheit interpretiert, statt Ungewissheit. Null kann ich allerdings nicht zurückgeben.

Hat jemand eine Idee?

Besten Dank

2

Wenn es einen Weg A-B-C-D-E gibt und einen Weg A-X-E, warum ist dann A,X,B,C,D,E überhaupt gültig?

Allgemein: Ein Comparator sollte nur dann 0 zurückgeben, wenn die verglichenen Objekte auch equal sind (zumindest wenn man konsistent mit equals bleiben will, was in den meisten Fällen Sinn macht).

3

gib hier -1 zurück oder was auch immer,
E zu X musst du ja anscheinend eh gesondert behandeln, X kleiner als E,
aber alles andere (außer zu X äquivalentes) kleiner als X, so dass X immer knapp vor E landet

4

Danke SlaterB und Firephoenix,

habe in Wikipedia etwas passendes zu dem Thema gefunden.

Das Beispiel mit dem Anziehen trifft es mMn. recht gut, was ich tun möchte.
Und „nein, ich sitze hier nicht nackt rum und weiß nicht womit ich anfangen soll“ :wink:

Es geht darum genau das zu tun, was in dem Wikipediaartikel beschrieben ist.

@FP, das Ergebnis ist in Ordnung, da es eine Reihenfolge über alle Elemente darstellt und zudem alle Abhängigkeiten die in dem Graphen beschrieben sind erfüllt sind.

@SlaterB , dass -1 funktioniert nicht wirklich. Das ganze soll für verschiedene gerichtete azyklische Graphen funktionieren und das tut es damit nicht.

Angenommen Quicksort wird verwendet. Dann kann ich leider nicht unterscheiden ob X.compareTo(B) oder B.compareTo(X) aufgerufen wird.

X vor B (1) ist genauso valide wie B vor X (2)
X vor C (3) ist genauso valide wie C vor X (4)

Hier gehts gut:
Wenn X einsortiert ist, dann kommt Vergleich 2 und danach Vergleich 3, was zu B X C führt. B mit C zu vergleichen macht keinen Sinn.

Hier gibts Problem:
Wenn X einsortiert ist, dann kommt Vergleich 1 und danach Vergleich 4, was zu C X B führt. B mit C zu vergleichen macht keinen Sinn, da laut Transitivität das ganze ja passen muss. Allerdings steht C vor B im Widerspruch.

Mit einem Comparator alleine scheint das ganze nicht wirklich Lösbar. Dies wäre allerdings eine sehr einfache und schnelle Implementierung gewesen.

5

?
du hast doch zwei Parameter bzw. ein this-Objekt und einen Parameter, je nachdem gibts du -1 oder +1 zurück,
wie hast du es im Moment denn für X vs. E implementiert?

ok, vielleicht mit allgemeinen Informationen, X vs E steht irgendwo, D vs. E steht irgendwo, usw.

eine allgemeine Idee noch, falls du dazu experimentieren willst, wohl nicht einfacher als sonstige Algorithmen…:

+C => C
+D => C,D
+E => C,D,E
+X => D.compareTo(X) == 0 => nun nicht C,X,D,E, sondern C,(X,D),E
wobei durchaus wie bisher 4 Elemente in der Liste,

aber bei X sowie D (im Comparator bei Rückgabe 0) wechselseitig hinterlegen,
dass diese eine Art ‚Einheit‘ bilden mit der ‚Kraft‘ nicht der zwei Herzen, aber sowohl des Wertes X als auch D

kommt nun B zum Vergleich mit X, wird intern mit beiden verglichen und deswegen kleiner zurückgegeben

ein echtes Problem hättest du falls X zu D undefiniert ist, zufällig X vor D sortiert, aber noch ein Wert Y kommt der zu X kleiner, aber zu D größer ist,
wobei du ganz strenggenommen mit der ‚Einheit‘ noch die Macht hättest, die beiden Elemente schnell zu vertauschen :wink:
alle Informationen vorhanden, nicht die Objekte in der Liste vertauschen, aber deren Inhalt, (*)

durch solche Aktionen können dann Einheiten aufgesprengt werden,

allgemein können Einheiten auch mehr als zwei Elemente enthalten

(*) edit: keine Chance aber mehr, falls A, (X, B), C, D vorliegt und Y immer noch mit Y < X sowie Y > D hereingeschneit kommt

6

@SlaterB , hab jetzt eine Lösung gefunden, die zudem auch noch halbwegs Elegant ist.

Ich schaue mir an, wie groß die Anzahl (Tiefe) der Nachfolger ist.

E hat 0 Nachfolger
D = 1
C = 2
B = 3
A = 4

E = 0
X = 1
A = 4, (Normalerweise 2, aber da bereits mit 4 oben vorbelegt)

Das kann ich nun vergleichen und muss wie FP bereits weiter oben erwähnte, nur noch für X vs D, da hier beide 1 besitzen ein weiteres Kriterium heranziehen.

Folglich ergibt sich dann:

A, B, C, D, X, E

Andererseits, passt auch die Geschichte, dass X und D eine Einheit bilden, in dem Sinne da hier die gleiche Anzahl an Knoten folgen kann.

7

Die Topologische Sortierung sollte eigentlich unmittelbar aus deinem DAG hervorgehen. Mit einem Comparator wirst du da kein Ergebnis bekommen, weil einige Elemente (in parallelen Pfaden) gar nicht direkt vergleichbar sind - dort existiert schlicht keine Ordnung auf den Knoten.
Eine korrekte topologische Sortierung bekommst du wie folgt.
Praktisch wäre es, wenn du einen Pseudoknoten einführst, der als Wurzel dient. Dieser Pseudoknoten enthält dann Kanten zu allen Knoten, die ansonsten von keiner Kante referenziert werden.
Das Ergebnis speichert man am besten in einer mittels Hashmap indizierten, verketteten Liste. (Die Hashmap als Inhaltsverzeichnis mit den Knoten als Schlüssel und dem Eintrag in der verketteten Liste als Wert.)
Nun traversierst du mittels Backtracking alle Pfade des DAG. Du beginnst dabei bei dem Pseudoknoten (der “Wurzel”) und gehst den DAG durch, bis der erreichte Knoten keine weiteren Kanten mehr enthält. Dann gehst du zurück und gehst den nächsten, noch nicht besuchten Pfad entlang.
Beim Einfügen eines neuen Eintrags in die Ergebnisliste musst du prüfen, ob der Knoten bereits existiert (dann brauchst du nichts mehr machen, weil der Knoten schon abgearbeitet ist). Wenn er nicht existiert, dann fügst du den Knoten in die Ergebnisliste direkt hinter den Knoten ein, von dem du gerade kommst (vor alle anderen Ergebnisse, die schon in der Liste sind).
Solange der Graph zyklenfrei ist, funktioniert der Algorithmus und du hast eine topologische Sortierung.

Nebenbemerkung: die topologische Sortierung bekommst du in O(n). Die Platzkomplexität sollte auch bei O(n) liegen.

8

Wie willst du denn einen einfachen Kreis aus immer gleich gerichteten Kanten sortieren? Stell dir ein Dreieck A–>B–>C–>A vor. Dann wäre keine Sortierung korrekt.

Oder zwei Ecken, die durch zwei gegenläufige Kanten miteinander verbunden sind: A<—>B

9

Das wäre aber auch kein azyklischer Graph (DAG). Diese Voraussetzung ist gemäß #4 gegeben.

10

@Crian
also cmrudolph hat Kreise explizit ausgeschlossen, “Solange der Graph zyklenfrei ist, funktioniert der Algorithmus”
und im ganzen Thread sowie im anschaulichen “Anziehreihenfolge von Kleidungsstücken”-Beispiel im Wiki-Artikel gibt es das auch nicht,

mit Kreisen gibt es keine Reihenfolge und Sortierung, logisch,
aber wozu das so explizit reinbringen außer vielleicht nur in einer Fußnote der Vollständigkeit halber zu erwähnen?
ohne Raumanzug kann man auch nicht auf den Mars

11

Ah! Danach hatte ich in #1 gesucht, aber den Punkt in #4 überlesen. Dann ist mein Einwand hinfällig. Für azyklische Graphen sollte es möglich sein, eine solche lineare Sortierung der Knoten hinzubekommen.