Problem2:Wahlen Sie Startknoten des DFS in topologischer...

[glowhand]

"Wahlen Sie Startknoten des DFS in topologischer Ordnung des ursprünglichen Graphen."
Was ist damit gemeint?

[Trillium]

Du wendest im 1. Schritt deinen TopSort Algorithmus auf den ursprünglichen Graphen an. Im zweiten Schritt gehst du die resultierende Liste Knoten für Knoten durch und wendest jeden Knoten als Startknoten für einen DFS im umgekehrten Graphen an.

[MonkeyT]

Wie sieht sollte denn die Rückgabe zu folgendem Graph lauten:

graph = { Imbiss=[Bronko], Bronko=[] }

transposeGrpah = { Imbiss=[], Bronko=[Imbiss] }
topologicalSort = [Imbiss, Bronko]

Und nun soll ich erst DFS von Imbiss im transposeGraph machen und dann von Bronko?

Imbiss:
Imbiss

Bronko:
Bronko, Imbiss

Soll dann also das zurück gegeben werden:
[ [Imbiss], [Bronko, Imbiss] ]

[leviathan]

Und was wenn der vorliegende Graph Zyklen enthält (kommt in den Tests vor)? Man kann zu einem Graphen mit Zyklen doch keine topologische Sortierung finden. Welche Reihenfolge hat man dann zu beachten?..

edit Durch das Cormen Buch bin ich jetzt auf eine funktionierende Lösung gekommen. Ich finde den Hinweis allerdings verwirrend, weil eine topologische Sortierung wie gesagt nicht immer existiert, und in solchen Fällen es zu weiteren Algorithmusanwendungen führt, auf die ich z.B. ohne das Buch definitiv nicht gekommen wäre.

[glowhand]

Durch das Cormen Buch bin ich jetzt auf eine funktionierende Lösung gekommen.

edit:

Hmm... ich bin es an der Stelle so angegangen, dass ich erstmal probiert habe, ob topologische Sortierung geht, und danach die Ordnung durch das anwenden von DFS auf den normalen Graphen und Umkehren der Ergebnisse gefunden habe - so ist die Ordnungfindung im Algorithmus im Cormen Buch beschrieben. Alle Tests laufen grün, ich bin mir aber auch nicht 100% sicher dass es so komplett korrekt ist...

[Vockilein]

Ich häng auch an der Stelle. Also wenn ich das richtig verstanden habe mache ich folgendes:

1. Prüfen ob topologische Sortierung möglich. (Also ob Graph Zyklen enthält oder nicht)
1.1 Wenn eine top. Sort. möglich => hinweise auf dem blatt befolgen
1.2 Wenn eine top. Sort. nicht möglich => Hier komm ich nicht weiter...

[SecretAgent]

1. Prüfen ob topologische Sortierung möglich. (Also ob Graph Zyklen enthält oder nicht)
1.1 Wenn eine top. Sort. möglich => hinweise auf dem blatt befolgen
1.2 Wenn eine top. Sort. nicht möglich => Hier komm ich nicht weiter...

Ich glaube man sollte TopologicalSort() aufrufen, egal ob der Graph Zyklen hat oder nicht. Ich glaube es geht in diesem Fall nur darum, dass man die Knoten in "finishOrder" durchläuft.

[leviathan]

Wenn man die topologicalSort() so implementiert, wie diese in den Vorlesugnsfolien beschrieben ist, liefert sie bei einem Graphen mit Zyklen keinen gültigen Ergebnis - Knoten, die in Zyklen sind, werden in der Reihenfolge fehlen.

Wie man die Ordnung für das zweite DFS (Komponentenfindung) findet, steht in dem Zitat von mir zwei Posts weiter oben bzw. im Buch "Introduction to Algorithms" (Cormen).

[SecretAgent]

liefert sie bei einem Graphen mit Zyklen keinen gültigen Ergebnis

Ist ja auch unmöglich, das zu machen. Trotzdem glaube ich, dass es nicht wirklich um TopologicalSort() geht, sondern um die finishOrder Reihenfolge (wie in Cormen steht). Dieses Problem scheint wohl weitestgehend von Cormen geklaut zu sein.

[Vockilein]

Ich steh momentan völlig auf dem Schlauch bzw. bin verwirrt was ich machen soll bei der Aufgabe... Kann jemand das nochmal verständlich erklären welche Schritte man macht? Wär hilfreich Danke.

[eesti]

ich versteh auch nicht so wirklich was diese funktion bewirken soll.
iteration über topologischen sortierten Graph und dfs auf umgedrehten, mit vertex aus topSort und visited und finishorder. visited und finishOrder leg ich neu(leer) in components an?!
was bewirkt dann eigtl, dass ich dfsvisit mit dem umgedrehten Graph aufrufe?
Was soll dann output, also meine rückgabe genau sein
wäre super, wem das ,al jemand an einem bsp erklären könnte


Danke schon mal

[VMann]

Ich hab das Problem mit der topologischen Sortierung von zyklischen Graphen so gelöst, dass jeder Knoten, der in einem Zyklus steckt, unsortiert ans Ende der Liste gestopft wird. (hab auch brav im JavaDoc drauf hingewiesen )

[linn]

kann mal jemand den dritten Beitrag im Thread (von MonkeyT) kommentieren.
In dem Beispiel wird doch genau das gemacht was als Hilfe in der Aufgabenstellung steht, liefert aber das falsche Ergebnis (Bronko und Imbiss sind keine starken zusammenhangsblub)

Dann heisst es hier noch das man für die Reihnfolge bei zyklischen graphen die Finishorder benutzen kann... Aber von welchen Knoten aus gestartet?

Edit: ok, jetzt funtzt alles bei mir, aber glaub is einiges unnötiges drin ^^
Also erstens mach ich zwei DFS pro knoten, eine auf den normalen und eine auf dem umgekehrten graphen.
Für die Reihnfolge hab ich erst soweit möglich toplogisch sortiert, dann alle zylken am ende eingefügt.

[ice-breaker]

Also ich habe eben den Teil ohne Corman implementiert, funzt ganz gut, läuft alles durch.

Nachdem ihr den Graph umgedreht und die topologischen DFS ausgeführt habt, habt ihr ja für jeden Knoten noch eine Menge weiterer Knoten.
Also so:
Graph = {Amy=[], Barney=[Amy]}

dann sollte rauskommen:
Amy=[Amy, Barney]
Barney=[Barney]

Die Menge sagt also, Amy kann durch Amy oder Barney erreich werden.
Das sagt ja alles schon die Aufgabe das es so gemacht werden soll, und nun muss man doch nur noch die Ergebnisse prüfen ob die Lösungsmengen auch stark zusammenhängend sind (denn durch den DfsVisit haben wir ja nur die einfache Richtung).

So alles verrate ich auch net, aber der Ansatz sollte reichen, achso, es ist dabei komplett egal ob der Graph zyklisch oder nicht ist.

[ff1010]

Durch das Cormen Buch bin ich jetzt auf eine funktionierende Lösung gekommen.

edit:

Hmm... ich bin es an der Stelle so angegangen, dass ich erstmal probiert habe, ob topologische Sortierung geht, und danach die Ordnung durch das anwenden von DFS auf den normalen Graphen und Umkehren der Ergebnisse gefunden habe - so ist die Ordnungfindung im Algorithmus im Cormen Buch beschrieben. Alle Tests laufen grün, ich bin mir aber auch nicht 100% sicher dass es so komplett korrekt ist...

Würdest auch verraten, wo ich das im Cormen finden kann? Habe die englische Ausgabe und bisher ist die components so unperformant, dass es dauert und dauert...

edit: Ok, funktioniert jetzt auch ohne Cormen... habs so gemacht, wie in den Hinweisen verlangt... hat allerdings einiges an Zeit in Anspruch genommen.