Seite 1 von 1

Praktikum 3 - MiniCuts (Verständnisproblem)

Verfasst: 7. Jun 2009 17:21
von 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

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Verfasst: 7. Jun 2009 17:57
von Gnomix
Packe in die Liste alle Kanten von reachableNodes zu unreachableNodes.

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Verfasst: 7. Jun 2009 18:23
von 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 :-/

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Verfasst: 7. Jun 2009 18:40
von der_andy
Du sollst von den Knoten aus reachable die KANTEN zu nicht erreichbaren Knoten (!reachable) ausgeben.

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Verfasst: 7. Jun 2009 18:54
von 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.

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Verfasst: 7. Jun 2009 19:03
von 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.

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Verfasst: 7. Jun 2009 19:13
von 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?

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Verfasst: 7. Jun 2009 19:38
von 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.

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Verfasst: 7. Jun 2009 19:48
von Payam
vielen dank..
werd ich gleich mal ausprobieren

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Verfasst: 7. Jun 2009 21:31
von spaci76
Michael_R hat geschrieben: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 ..

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Verfasst: 7. Jun 2009 21:51
von 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?

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Verfasst: 7. Jun 2009 21:53
von 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