Praktikum 3 - MiniCuts (Verständnisproblem)

[Payam]

Hallo,

ich bin gerade am verzweifeln. Ich verstehe absolut nicht, was MiniCuts machen soll. Ich kann mir den Text noch zehn mal durchlesen und werde nicht schlauer.

Mag mir jemand es bitte Schritt für Schritt erklären?
Schritt für Schritt Implementierung wäre auch nett

ich habe so angefangen:

minicuts(graph, source, sink)
{
Schritt 1. AddSuperSourceSink()
Schritt 2. EdmonsKarp()..
Schritt 3.??

}

Was soll denn in der Liste<Edge> alles reingepackt werden?
Die Methode reachableSet ist auch fertig implementiert.. aber keine Ahnung was man da nun machen soll... mal ehrlich: die Beschreibung und der Text kann man sowas von knicken

Danke im Vorraus,

Payam

[Gnomix]

Packe in die Liste alle Kanten von reachableNodes zu unreachableNodes.

[Payam]

also soll ich das Ergebnis von reachableNodes in die Liste reinpacken oder soll ich die Liste nehmen und die Kanten, die nicht vorhanden sind, da reinpacken?

also als beispiel

graph 1.)

A-> B | 5
B -> C | 5

was würde da in der Liste stehen?

oder A->B | 10 ?
oder
A->B | 10 ,
B->C |0
??
Ich habe die Aufgabe immernoch nicht verstanden :-/

[der_andy]

Du sollst von den Knoten aus reachable die KANTEN zu nicht erreichbaren Knoten (!reachable) ausgeben.

[Payam]

Verstehe ich immernoch nicht...

heißt im Grunde, ich soll alle Kanten, die nicht erreichbar sind in die Liste einfügen, oder?

wenn ich A->B , 5 habe, sollte dann die Liste leer sein, weil alle Kanten erreichbar sind, oder nicht?
Der sagt mir aber, dass da ein cut drinne ist..

bei
A->B | 10 ,
B->C |0 sind auch alle Knoten/Kanten erreichbar,.. hier will er aber ne leere Liste.

[der_andy]

Test 1 (testOneEdge) soll als Ausgabe ausgegeben werden: new Edge("A", "B", 5.0).
Da "Source" und "A" erreichbar sind (d.h. Elemente der Liste reachable) "B" aber nicht erreichbar ist (d.h. !Element reachable), jedoch eine KANTE (A->B) esistiert.

[Payam]

das heißt, alle knoten die von source nicht als nachbaren haben, sollen in die liste rein?

also source - A
source - B

B- C
alles was niht mit source verbunden ist -> in die Liste reinpacken?

[Michael_R]

Du schaust welche Kanten vor anwendung von EdmonsKarp von "Source" aus erreichbar waren und welche Knoten nach anwendung von EdmonsKart noch erreichbar sind.

Zurück gibst Du dann eine Liste mit allen Kanten die von Knoten die immernoch erreichbar sind zu Knoten die nur vor anwendung von EdmonsKarp erreichbar waren.

[Payam]

vielen dank..
werd ich gleich mal ausprobieren

[spaci76]

Du schaust welche Kanten vor anwendung von EdmonsKarp von "Source" aus erreichbar waren und welche Knoten nach anwendung von EdmonsKart noch erreichbar sind.

Zurück gibst Du dann eine Liste mit allen Kanten die von Knoten die immernoch erreichbar sind zu Knoten die nur vor anwendung von EdmonsKarp erreichbar waren.

ich wollte jetzt mal nachdem ich die addsupersourcesinke ausgeführt habe mir die verfügbaren knoten besorgen.

Code: Alles auswählen

Set<String> erreichbar = reachableSet(g, "Source");

Danach das edmonskarp drüberlaufen lassen und mit

Code: Alles auswählen

Set<String> erreichbar2 = reachableSet(g, "Source");

vergleichen um dann die fehlenden knoten mir den mit den ensprechenden edges in die edge einfügen zu können.

wäre das vom ablauf her der korrekte ..

[Payam]

mit reachable erhält man ja nur die nicht erreichbaren knoten... alles klar..

aber woher weiß ich denn, welche kanten von der liste mit knoten nicht vorhanden sind?

[Gnomix]

[quote="Payam"]
minicuts(graph, source, sink)
{
Schritt 1. AddSuperSourceSink()
Schritt 2. EdmonsKarp()..
Schritt 3.??

}

Schritt 3: set x = reachableSet()

Gehe alle Knoten in X durch und schaue nach Kanten die zu Knoten führen, die nicht in x sind.
Diese müssen bei Mincut zurück gegeben werden.

!reachable = V ohne reachable