Problem 2 - Topologische Ordnung der starken Zusammenhangsk.

Benutzeravatar
Puppetmaster
Mausschubser
Mausschubser
Beiträge: 92
Registriert: 8. Okt 2008 10:02
Kontaktdaten:

Re: Problem 2 - Topologische Ordnung der starken Zusammenhangsk.

Beitrag von Puppetmaster »

es wird aber gesagt, dass die eingabe keine zyklen enthalten darf -.-

Benutzeravatar
tonyp
Mausschubser
Mausschubser
Beiträge: 48
Registriert: 18. Dez 2008 15:41

Re: Problem 2 - Topologische Ordnung der starken Zusammenhangsk.

Beitrag von tonyp »

Conny-Cidius hat geschrieben:edit: ok beim schreiben ist mir eine sehr lustige idee gekommen, die die tests zu 90% durchlaufen lassen...es wäre EVENTUELL ziemlich klug gewesen zu erwähnen, dass die Knoten der Komponenten nicht Teil einer anderen Komponente sein dürfen. Aber darauf kommt man mit der Logik, die man uns einstampft, ja von ganz selbst drauf, nich?

DANKE!
Genau diese Passage hat mich auch auf die richtige Fährte geführt.
Es macht natürlich eigentlich Sinn, dass die Knoten nurin je einer Komponente vorkommen dürfen, aber die Beschreibung des 3. Schrittest ist schon echt schlecht! Mit einer contains-Abfrage funktionieren jetzt auf jeden Fall auch die letzten 3 Tests! Mannmannmann.

phm
Neuling
Neuling
Beiträge: 8
Registriert: 6. Mai 2009 18:55

Re: Problem 2 - Topologische Ordnung der starken Zusammenhangsk.

Beitrag von phm »

linn hat geschrieben:doch, es wird ja nirgends gesagt was die funktion in falle eines zyklischen graphen ausgeben soll.
Ich habe auch topologicalSort() geändert, damit sie Graphen mit Zyklen bearbeiten kann. Anstatt von den Knoten mit Eingangsgrad 0 zu starten, starte ich von beliebigen Knoten, bis alle besucht wurden. Es ist egal, dass es Zyklen gibt. Wenn wir eine Kante finden, die zu einem schon besuchten Knoten führt, machen wir als ob diese Kante nicht exisitierte.

Hier eine Erklärung, warum es (meiner Meinung nach!) funktionnert. Die Tests für Schritt 3 sind alle erfolgreich. Aber Schritte 4 & 5 habe ich noch nicht gemacht.

A, B, C, D sind die stark-zusammenhängenden Komponenten von einem Graph G, mit B -> C -> D, d.h. es existiert b in B, c und c' in C, d in D so dass (b,c) und (c', d) Kanten sind.

Wir nehmen einen beliebigen Anfangsknoten s, und führen eine Tiefsuche aus. Falls s in A ist, kriegen wir nur die Knoten von A. Dann führen wir nochmal eine TS mit s' in B. Irgendwann kommen wir zu den Knoten von C, und dann von D. Egal in welcher Reihenfolge die Knoten besucht werden, finishOrder enthält zuerst die Knoten von D, dann die von C, und endlich die von B. Wir kehren finishOrder um, und kriegen: {Knoten von B, Knoten von C, Knoten von D, Knoten von A}, was eine "pseudo-topologische Sortierung" ist.

Was wenn s in C ist? Dann enthält finishOrder nach der ersten DFS Suche {Knoten von D, Knoten von C}. Wir gehen weiter mit s' in B, und s" in A. Am Ende kriegen wir: {Knoten von A, Knoten von B, Knoten von C, Knoten von D}. Oder mit s' in A und s" in B: {Knoten von B, Knoten von A, Knoten von C, Knoten von D}. In beiden Fällen haben wir noch eine "pseudo-topologische Sortierung".

Wichtig ist nur, dass B vor C und C vor D vorkommt. Wir können den "reduzierten Graph" definieren, indem alle Komponenten mit einem einzigen Knoten ersetzt. Hier wäre dieser Graph: { {a, b, c, d} ; {(b,c) ; (c,d)} }. Die "pseudo-topologische Sortierung" im originalen Graph entspricht einer richtigen topologischen Sortierung im reduzierten Graph: {b,c,d,a} oder {a,b,c,d} oder {b,a,c,d}.

Anders gesagt, es ist vollkommen egal, wie man die Anfangsknoten der TS Suchen wählt. Aber wenn wir von Knoten mit Eingangsgrad 0 starten, bekommen wir immer b, c und d nacheinander, keine Sortierungen wie {b,a,c,d}.


EDIT: Die Lösung funktionniert, aber meine Erklärung ist falsch. Es gibt gar keine "pseudo-topologische Sortierung", und auch keine "topologische Sortierung". Ich finde es verwirrend, das in der Aufgabe die Funktion "topologicSort" heisst!
In meinem Beispiel bekommen wir nicht unbedingt {Knoten von B, Knoten von C, Knoten von D, Knoten von A}. Wir können auch sowas bekommen: {b1, b2, c1, c2, b3, b4, d1, c3, d2, a1}. Wichtig ist nur, dass es zwischen b1 und c1 keine di gibt. Und das ist nicht den Fall. Dann läuft man das Ergebnis von topologicSort (das keine topologische Sortierung ist!) durch, und starten eine TS falls der Knoten noch nicht besucht wurde. Nur der erste Knoten eines Komponentes zählt.

gr3mlin
Erstie
Erstie
Beiträge: 20
Registriert: 17. Okt 2008 18:13
Wohnort: Frankfurt

Re: Problem 2 - Topologische Ordnung der starken Zusammenhangsk.

Beitrag von gr3mlin »

Ich habe auch topologicalSort() geändert, damit sie Graphen mit Zyklen bearbeiten kann. Anstatt von den Knoten mit Eingangsgrad 0 zu starten, starte ich von beliebigen Knoten, bis alle besucht wurden. Es ist egal, dass es Zyklen gibt. Wenn wir eine Kante finden, die zu einem schon besuchten Knoten führt, machen wir als ob diese Kante nicht exisitierte.
Genau das hab ich auch getan, nachdem ich gemerkt hab, dass die Funktion (entgegen der Aufgabenstellung) auch zyklische Graphen "sortieren" (was ja nicht möglich ist) muss.
Trotzdem alles gut soweit, alle Tests von transpose() und topSort() grün.

Jetzt versuche ich components() folgendermaßen zu implementieren:

1. Ich führe mein topologicalSort() auf den aktuellen (Ursprungs-)Graphen aus.
2. Ich bilde den umgekehrten Graphen.
3. Ich mache pro topSort()-Knoten (mit ihm als Startknoten) eine DFS auf den umgekehrten Graphen
4. Direkt nach der DFS add()e ich die finishOrder des Aufrufs zum output und clear()e die finishOrder wieder für den nächsten Schleifendurchlauf.
5. return output

Ergebnis: Es läuft (bis auf testEmpty) kein einziger Test.

Ich kam nach mehrfachem Löschen der Funktion und Lesen der Tips hier im Forum immer wieder auf die selbe Implementierung.
Jetzt Frage ich mich, ob mein topSort() trotz Änderungen für zyklische Graphen und grüner Tests einfach falsch ist oder
ob ich bei components() einfach grundsätzlich die Tips/Aufgabenstellung falsch verstehe.

Für jede Hilfe bin ich dankbar.

robert.n
Nerd
Nerd
Beiträge: 673
Registriert: 29. Sep 2008 19:17

Re: Problem 2 - Topologische Ordnung der starken Zusammenhangsk.

Beitrag von robert.n »

gr3mlin hat geschrieben:
Ich habe auch topologicalSort() geändert, damit sie Graphen mit Zyklen bearbeiten kann. Anstatt von den Knoten mit Eingangsgrad 0 zu starten, starte ich von beliebigen Knoten, bis alle besucht wurden. Es ist egal, dass es Zyklen gibt. Wenn wir eine Kante finden, die zu einem schon besuchten Knoten führt, machen wir als ob diese Kante nicht exisitierte.
4. Direkt nach der DFS add()e ich die finishOrder des Aufrufs zum output und clear()e die finishOrder wieder für den nächsten Schleifendurchlauf.
Du musst in jedem Schleifen-Durchlauf eine neue Liste erzeugen und dann diese zu output hinzufügen! Ansonsten fügst du im Prinzip X Mal dieselbe Liste hinzu.

Insgesamt hört sich das schon ganz gut an, nur vergiss nicht immer dasselbe visited-Set zu verwenden für die DFS-Durchläufe (in Schritt 3/4). ;)

gr3mlin
Erstie
Erstie
Beiträge: 20
Registriert: 17. Okt 2008 18:13
Wohnort: Frankfurt

Re: Problem 2 - Topologische Ordnung der starken Zusammenhangsk.

Beitrag von gr3mlin »

Das Problem war in der Tat das clear()en.
Stattdessen muss ich die finishOrder komplett auf 'ne new ArrayList<String>() setzen, dann grünt es aus jeder Richtung ^^

Herzlichen Dank ;)

Antworten

Zurück zu „Archiv“