Problem 2 - Topologische Ordnung der starken Zusammenhangsk.

[ms1006]

In Schritt 3 soll man die Identifizierung von starken Zusammenhangskomponenten implementieren, wobei diese auch noch topologisch sortiert sein sollen.

Angenommen, der Graph enthält Zyklen (sonst könnte er ja nirgendswo stark zusammenhängend sein,oder?). Dann ist er nicht topologisch sortierbar. Damit kann man auch nicht, wie im Hinweis angegeben, die Startknoten des DFS in Topologischer Ordnung wählen. Ich habe das jetzt so gelöst, dass ich die Startknoten einfach unsortiert gewählt habe (also in irgendeiner Reihenfolge) falls eine sortierung nicht möglich ist, und die Tests laufen grün. ABER: ich glaube, dass die Komponenten so nicht unbedingt topologisch sortiert sind,kann das sein? Das braucht man für die letzte Aufgabe, da sollten die Komponenten sortiert sein, bin mir jetzt nicht sicher ob da vielleicht (m)ein Fehler liegt....

Danke
Maggus

[leviathan]

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...

Hatte auch den wesentlich komplizierteren Ansatz, die gefundenen Komponenten als Knoten in einem neuen Graphen aufzufassen, die Kanten zu übertragen und den Graphen topologisch zu sortieren... aber es ist fast viel zu komplex, dafür dass das andere läuft

[SecretAgent]

Alle Tests laufen grün, ich bin mir aber auch nicht 100% sicher dass es so komplett korrekt ist...

Es ist auch richtig so. Meine Meinung nach ist es nicht so gut auf dem Übungsblatt erklärt. Bei components() geht es eher um, dass wir die Knoten in der absteigenden Reihenfolge der FinishOrder einer DFS durchlaufen. Es ist nur so, dass topologicalSort() uns das liefert.

[tigris]

Ich stimme ms1006 vollkommen zu. Nur wenn das so ist, kann mir dann mal einer erklären, wie die Aufgabe zu verstehen ist?
Muss ich auf Zyklen testen und von jedem Zyklus dann eine Collection der Knoten erstellen? Wenn ja, sollen die Zyklen dann maximal sein.
Wie könnte dann aber eine topologische Sortierung möglich sein? Entweder ich verstehe die Aufgabe also vollkommen falsch, oder es ist meine Meinung nach einfach nicht möglich.

[Scorpius]

Nochmal um ganz klar zu machen was starke Zusammenhangskomponenten sind:

Ein gerichteter Graph, in dem jeder Knoten von jedem anderen aus durch einen Pfad erreichbar ist, heißt stark zusammenhängend (strongly connected). Eine starke Zusammenhangskomponente (strongly connected component) ist ein maximaler stark zusammenhängender Teilgraph. Abbildung 5.18 zeigt einen Graphen mit 4 starken Zusammenhangskomponenten. In jeder solchen Komponente ist jeder Knoten von jedem anderen aus erreichbar; wird die Komponente verlassen, gibt es keinen Weg mehr zurück.

[robert.n]

Nochmal um ganz klar zu machen was starke Zusammenhangskomponenten sind:

Ein gerichteter Graph, in dem jeder Knoten von jedem anderen aus durch einen Pfad erreichbar ist, heißt stark zusammenhängend (strongly connected). Eine starke Zusammenhangskomponente (strongly connected component) ist ein maximaler stark zusammenhängender Teilgraph. Abbildung 5.18 zeigt einen Graphen mit 4 starken Zusammenhangskomponenten. In jeder solchen Komponente ist jeder Knoten von jedem anderen aus erreichbar; wird die Komponente verlassen, gibt es keinen Weg mehr zurück.

Also wenn ich auf dieses Beispiel den im Hinweis angegebenen Algorithmus anwende, dann kommt da nur Schrott raus.
Dann gehe ich mal davon aus, dass schlicht und einfach ich den Hinweis nicht richtig verstehe...

Was ich momentan versuche:
- topologische Ordnung des ursprünglichen Graphen erstellen
- in der Reihenfolge dieser topologischen Ordnung eine DFS auf jeden Knoten im umgekehrten Graphen anwenden
- alle finishOrder's, die bei diesen DFS rauskommen, in output stecken (von vorneherein Käse, dann hätte man ja |V| viele Komponenten...)

Da heißt es dann bei den Tests aber immer "vertex twice" o.ä. Kann aber auch gar nicht klappen IMO, bei dem Beispiel gehts ja auch nicht...

Hint: Run DFS on the transposed graph, selecting the DFS roots in topological order with respect to the original graph. The vertices of each explored subtree form a strongly connected component.

Also, was habe ich falsch verstanden? Was ist mit den "explored subtree[s]" gemeint?

[Vockilein]

subtree kann ja eigentlich schon mal gar nicht stimmen. ne starke zusammenhangskomponente enthält zyklen sonst wärs ja keine starke zusammenhangskomponente...
und baum ist definiert als vollständiger graph OHNE zyklus.

langsam versteh ich nur noch bahnof...

[Conny-Cidius]

langsam versteh ich nur noch bahnof...

der erste sinnvolle satz den ich heute über diese aufgabe gelesen habe.

Ansonsten kann ich bei meinem problem robert 1:1 zitieren, denn bei mir sieht es genauso aus.
ich mein...
was lässt sich aus der aufgabenstellung verstehen:
topologische reihenfolge des ursprungsgraphen ... check
umgekehrter graph ... check
der topologischen sortierung entsprechend einmal der reihe nach über die Liste wandern und dabei jedesmal _eine_ DFS von dort aus starten, welche mir eine finishedOrder gibt (dafür war schonma ein gang zunem tutor notwendig weil der gesunde menschenverstand an dieser stelle aus der aufgabenstellung garnichts oder visited rausliest) ... check
diese liste in die output-liste stecken ... check
profit? ... FAIL

bin ich einfach nur zu blöd oder wollen _die_ mich glauben lassen, ich wär blöd.

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?

edit2: und jetzt hab ich was gemacht, was ich garnicht verstehe wieso es geht, und es geht alles...

ein Hoch auf GDI 2 Aufgabenstellungen *prost*

[robert.n]

edit2: und jetzt hab ich was gemacht, was ich garnicht verstehe wieso es geht, und es geht alles...

ein Hoch auf GDI 2 Aufgabenstellungen *prost*

Und was hast du gemacht?

[eesti]

wenn ich nur 2 knoten habe, sollen dann die zwei knoten zurückgegeben werden? oder zählt das noch nicht als zusammenhang???

[linn]

wenn jeder der beiden knoten den jeweils anderen erreichen kann, gibst du sie zusammen aus, ansonsten einfach.
also
a b führt zu {a}->{b} oder {b}->{a}
a -> b führt zu {a}->{b}
a <-> b führt zu {a,b}

[tigris]

Schaut euch mal folgendes Bildchen an:


folgender Code erzeugt solch einen Graphen:

Code: Alles auswählen

StrikeForce myStrikeForce = new StrikeForce();
Graph myGraph = myStrikeForce.emptyGraph();
	myGraph.addEdge("1","2");
	myGraph.addEdge("2","1");
	myGraph.addEdge("1","4");
	myGraph.addEdge("4","2");
	myGraph.addEdge("2","3");

Meine Vorstellung der Aufgabenstellung für die Funktion components(Graph graph) lautet wie folgt:
1.) Ich bestimme alle starken Zusammenhangskomponenten. Das wäre hier der Teilgraph bestehend aus Knoten 1 und 2, sowie der Teilgraph bestehend aus Knoten 1, 2, und 4.
2.) Ich wende meine topologische Sortierung auf die Teilgraphen an.
3.) Ich füge meine Knotennamen in Collections<String> der Liste hinzu.

Hier meine Gedanken:
- Es ist für mich unklar, ob ich die maximalen Zusammenhangskomponenten suchen muss. In meinem Beispiel hatte ich ja zwei Teilgraphen, die nur steng zusammengehörende Komponenten enthalten. Allerdings enthielt mein zweiter Teilgraph den ersten.
- Wenn ich eine starke Zusammenhangskomponente gefunden habe, so muss laut Definition jeder Knoten jeden anderen Knoten erreichen können. Das führt aber zwangsläufig zu Zyklen, die wiederum in einem Widerspruch zu einer topologischen Sortierung stehen würden. Demnach könnte aber die Aufgabenstellung schon nicht so gemeint sein, wie ich sie gerade aufgeschrieben habe.
- Dies wird nur noch bestärkt dadurch, dass meine zurückzugebende Liste (ist sortiert) aus Collections<String> (sind nicht zwangsläufig sortiert) bestehen soll. Wende ich eine (unmögliche) topologische Sortierung auf meine Teilgraphen an, und füge dann nur die Namen in eine (unsortierte) Collection<String> hinzu, bräuchte ich mir von Anfang an auch nicht die Mühe zu machen, sie topologisch zu Sortieren (falls das mir irgendeiner Implementierung entgegen der Definition möglich sein sollte ).

Schlussfolgerung:
Nach den Gedanken kommt mir nur noch eine Schlussfolgerung. Es müssten die maximalen Teilgraphen gesucht werden, die jeweils starke Zusammenhangskomponenten sind. Diese müssen danach untereinander topologisch sortiert werden. Das würde auch erklären, weshalb die Collections<String> auch in einer (sortierten) Liste sind. Die Frage, über die ich mir noch nicht so sicher bin, ist aber ob solch eine topologische Sortierung dann überhaupt möglich ist (ich glaube dafür gibt es aber noch einen anderen Thread). Die weitere Frage wäre, was in meinem Beispiel mit Knoten 3 passieren würde. Streng genommen ist dieser Knoten alleine keine starke Zusammenhangskomponente, da er sich selbst nicht erreichen kann (er besitzt ja keine Schlinge).
Sollte es also wirklich laut Vorstellung von Herrn Terpstra so gemeint sein, wie ich es gerade vorgestellt habe, dann wäre deshalb nur noch die Frage, welche der beiden List<Collection<String>> herauskommen sollte. Entweder [ {1, 2, 4} ] oder [ {1, 2, 4}, {3} ]...

Über Meinungen und vor allem Hilfestellungen von Leuten, die das schon lösen konnten bin ich sehr dankbar .

[robert.n]

Habe gerade das hier gefunden und ackere mich da durch...
http://books.google.de/books?id=abPtEX0 ... &resnum=10

// edit: von DFS auf jeden Knoten in topologischer Ordnung geschweige denn vom umgekehrten Graphen ist hier keine Rede...

// edit2: Das hier passt wohl besser zu unserer Aufgabenstellung: http://books.google.de/books?id=ZfMgGph ... 2#PPA93,M1
So, dieser 2. Link und ein paar Minuten geistiges Jonglieren haben mir durch eine kleine Änderung meines bisherigen Verfahrens (siehe oben) viele neue bestandene Testfälle beschert (3 fehlen noch).
// edit3: ComponentsTests laufen alle durch... \o/

[Le_Coeur]

In den Kommentaren von topologicalSort(...) steht, dass Input: A directed acyclic graph.
Aber in der Aufgabe 3 kommen Cyclenm, dann kann ich nicht dieses Method verwenden! Oder?

[linn]

doch, es wird ja nirgends gesagt was die funktion in falle eines zyklischen graphen ausgeben soll.