Praktikum 3 - MiniCuts (Verständnisproblem)

Benutzeravatar
Payam
Erstie
Erstie
Beiträge: 13
Registriert: 19. Nov 2005 16:55
Wohnort: 64331
Kontaktdaten:

Praktikum 3 - MiniCuts (Verständnisproblem)

Beitrag 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

Benutzeravatar
Gnomix
Computerversteher
Computerversteher
Beiträge: 306
Registriert: 31. Okt 2005 08:44

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Beitrag von Gnomix »

Packe in die Liste alle Kanten von reachableNodes zu unreachableNodes.

Benutzeravatar
Payam
Erstie
Erstie
Beiträge: 13
Registriert: 19. Nov 2005 16:55
Wohnort: 64331
Kontaktdaten:

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Beitrag 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 :-/

der_andy
Neuling
Neuling
Beiträge: 6
Registriert: 7. Jun 2009 01:52

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Beitrag von der_andy »

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

Benutzeravatar
Payam
Erstie
Erstie
Beiträge: 13
Registriert: 19. Nov 2005 16:55
Wohnort: 64331
Kontaktdaten:

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

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

der_andy
Neuling
Neuling
Beiträge: 6
Registriert: 7. Jun 2009 01:52

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

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

Benutzeravatar
Payam
Erstie
Erstie
Beiträge: 13
Registriert: 19. Nov 2005 16:55
Wohnort: 64331
Kontaktdaten:

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Beitrag 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?

Benutzeravatar
Michael_R
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 172
Registriert: 4. Apr 2008 17:58
Wohnort: Frankfurt

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

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

Benutzeravatar
Payam
Erstie
Erstie
Beiträge: 13
Registriert: 19. Nov 2005 16:55
Wohnort: 64331
Kontaktdaten:

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Beitrag von Payam »

vielen dank..
werd ich gleich mal ausprobieren

spaci76
Mausschubser
Mausschubser
Beiträge: 52
Registriert: 9. Mai 2009 18:27

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

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

Benutzeravatar
Payam
Erstie
Erstie
Beiträge: 13
Registriert: 19. Nov 2005 16:55
Wohnort: 64331
Kontaktdaten:

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Beitrag 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?

Benutzeravatar
Gnomix
Computerversteher
Computerversteher
Beiträge: 306
Registriert: 31. Okt 2005 08:44

Re: Praktikum 3 - MiniCuts (Verständnisproblem)

Beitrag 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

Antworten

Zurück zu „Archiv“