Problem 3 - Schritt 4: minimaler Schnitt

[leviathan]

So, gerade das ganze laufen lassen und festgestellt, dass doch alles in Ordnung ist - die randomTests() terminieren auch. Nach einer Weile. Einer ganzen, ganzen Weile... Ob das Problem jetzt in meinem Code oder eher doch im Profiler ist, werde ich dann versuchen festzustellen.

[kutschke]

Hi!
Was benutzt du denn als Datenstruktur in der BFS? Eine Warteschlange wäre optimal, um die zu besuchenden Knoten zu speichern...

[ice-breaker]

also mit TPTP brauchen die Tests natürlich eine ganze Ecke länger, TPTP hängt sich in die Java VM und wird eben andauernd mit Infos gefüttert.
Ich würde euch auch empfehlen die Agent.exe oder so nicht zu killen, wenn die auf einmal CPU oder Speicher frisst ohne Ende, das killt TPTP und es kommt die Meldung von daniel_b, ich habe es nur geschafft es zu fixxen, indem ich Eclipse gelöscht habe und ein brandneues genommen habe und da wieder TPTP installiert habe.

[Vockilein]

Ahahah bei mir gehts immer noch nicht. Ich kann in der Monitor Auswahl auch nur Java 1.5 pre auswählen.

Jemand ne Idee was da schief läuft? Ich hab das neuste Eclipse heute draufgemacht.

[robert.n]

Ahahah bei mir gehts immer noch nicht. Ich kann in der Monitor Auswahl auch nur Java 1.5 pre auswählen.

Jemand ne Idee was da schief läuft? Ich hab das neuste Eclipse heute draufgemacht.

Einfach eclipse paar mal neu starten und hoffen, dass auf einmal Java 1.5 or NEWER drinsteht... war bei mir genauso und ich weiß leider nicht, warum es plötzlich funktioniert hat. Geändert habe ich eigentlich nichts.

[dalinger]

Ich wollte kurz etwas zum Profiler sagen. Es ist möglich den Profiler HPROF über Eclipse zu starten. Dazu schreibt man z. B.

-Xrunhprof:cpu=samples,depth=8

in die vm arguments der jeweiligen run configuration. Unter Ubuntu 8.04 mit dazugehörigem Eclipse klappt das jedenfalls.

[b00m3r]

Hallo zusammen,
könnt ihr mir mal verständlich erklären was das Zielbild der Aufgabe ist?

Ich verstehe den letzten Hinweis auf dem Blatt nicht so ganz!

Grüße

[Michael_R]

Die Kanten die Du auflisten sollst sind alle Kanten aus dem Original Graphen, die von Knoten aus der Menge A zu Knoten aus der Menge B führen.

In Menge A sind alle Knoten drin die nach Anwendung von Edmonds-Karp noch von der Quelle aus erreichbar sind.

In Menge B sind alle Knoten die im Original Graphen von der Quelle erreichbar waren, aber nach Anwendung von Edmonds-Karp nichtmehr erreichbar sind.

[b00m3r]

Um diese Beschreibung mal mit Leben zu füllen versuche ich mal ein Beispiel.
Ich beziehe mich jetzt auf TestNr.1 testOneEdge()
Der Graph laute
A;
A -> B: 5.0;
B;
B -> A: 5.0;

Vor Anwendung des EK
5
A ---->B
<-----
5

Nach der Anwendung sieht der Graph folgermaßen aus:

A;
A -> B: 0.0;
B;
B -> A: 10.0;

Residualgraph
0
A ---->B
<-----
10

Das heißt in Menge A befindet sich nur noch {A} und in Menge B befindet sich {A,B}

Den MinCut bilden nun alle Kanten von den erreichbaren zu den nicht mehr erreichbaren Knoten!
MinCut Edge(A, B, 5)

Ist das so richtig ?

[Michael_R]

fast

In Menge B sind alle Knoten die im Original Graphen von der Quelle erreichbar waren, aber nach Anwendung von Edmonds-Karp nichtmehr erreichbar sind.

Knoten A ist daher nicht in Menge B

[b00m3r]

Ich denke das Gerüst was ich gebastelt habe stimmt.
Hab die zwei Mengen A und B programmiert und die MinimalCutlogik sollte stimmen. 5 von 10 Tests laufen schonmal.Aber hab eben festgestellt das ich noch ein Problem habe mit dem SenkKnoten in der reachableSet. Die Funktion edmondskarp verlangt ja eine Quelle und eine Senke in der reachableSet bekommt man jedoch nur eine Quelle übergeben. Ich rufe reachableSet mit der Startknotenliste auf, sodass ich jeden Startknoten mitnehme. Wie bekomm ich das jetzt für die Senken hin.Momentan betrachte ich jeden Knoten im Graphen einmal als Senke. Was natürlich quatsch ist. Wie habt ihr das gelöst?

Also das Problem ist konkret wie kann ich auf die Zielknotenliste in der reachableSet zugreifen? Wie habt ihr das elegant gelöst.


EDIT habs Problem gelöst haben ja so ne tolle funktion gehabt addSuper...

[dumbo2]

Also ich komm hier irgendwie nicht weiter. Meine Tests laufen alle durch, bis auf Random und Big.

Bei random hängt er bei 588, aber gibt keine Fehlermeldung zurück, sondern bleibt einfach stehen und frist CPU und Speicher.

Die anderen Tests (edmondKarp, augmentingPath, BFS) laufen jeweils unter 1sec durch. Ich iteriere, wenn ich Listen habe nur über LinkedLists, Vergleiche(contains) werden nur auf Sets gemacht. mincut läuft so ab:

graph nehmen, supersource/sink einbauen
graph clonen
edmondkarp auf geclonten graph
erreichbare Knoten für den geclonten graph

dann für jeden erreichbaren knoten(a)
für jeden nachbarn(b) von (a)
wenn (b) nicht in erreichbaren Knoten Set
füge kante a->b in ergebnisliste


Hab auch nochmal TPTP 50sec laufen lassen, aber so wirklich schlau werd ich nicht draus.
Also nur mincutTest random:
-------------------------Cumulative Time----Calls
mincut-----------------16---------------------588
bfs--------------------- 2,23------------------32710
augmentingpath------3,11------------------31536
edmondkarp-----------9,7-------------------1175
reachable--------------0,04------------------587
addsupersourcesink--0,25------------------588

Auffällig ist wohl, dass EdmondKarp 2 mal aufgerufen wird, aber in mincut selber tue ich es definitiv nur einmal. Es müsste also auch nur 587/588 sein. Reachable haengt bei 587, weil es EdmondKarp tut, zumindest der zweite Aufruf.
Ich verstehs wirklich nicht, naja, mal sehen was nach dem Weitertüfteln bei rauskommt.

Gruß Olli

[robert.n]

augmentingPath/BFS wird sehr oft aufgerufen... vllt. kommst du in edmondsKarp() in eine Endlosschleife, weil er nie aufhört zunehmende Wege zu finden? edmondsKarp() wird übrigens AFAIK von den Testcases nochmal aufgerufen...

[der_andy]

Leider hab ich ebenfalls das Problem, dass die Tests Random, sowie Big mit der Fehlermeldung:
"is a minimum cut expected:<534.5353689520231> but was:<368.40680038679596>" (Random) bzw.
"is a minimum cut expected:<122.90144875328525> but was:<87.55557550738746>" (Big)
fehlschlagen! Ich hab schon alle Forenbeiträge zu diesem Thema durchgearbeitet, doch leider konnte ich dieses Problem nicht beheben. Alle anderen Test's laufen einwandfrei durch.
Hat vielleicht jemand das selbe Problem aktuell bzw. gelöst?

Gruß Andy

[dumbo2]

Bah, könnte meinen Kopf gegen die Wand schlagen.

Mein Fehler war, dass ich in EdmondKarp die Variablen tempFlow und flow zur Berechnung des maximalen Flusses in einem Pfad nach dem verändern des Graphen nicht reseted hab, bei mir auf Double.pos_inf .

Nun laufen alle Tests in 5,9 sec durch!

Schönen Sonntag noch und danke für die Hilfe.

Gruß Olli