Seite 1 von 3

Übungsaufgabe WS 2014/15

Verfasst: 15. Okt 2014 09:28
von Prof. Karsten Weihe
Hallo allerseits,

hier nun die Programmieraufgabe für die EGA im WS 2014/15:

Implementieren Sie die folgenden, in der Vorlesung demnächst zu besprechenden Algorithmen für die Standardversion des Max-Flow Problems, jeweils in der einfachsten Variante:

-> Ford-Fulkerson mit DFS zur Berechnung des flusserhöhenden Pfades.

-> Edmonds-Karp

-> Dinic

-> Goldberg-Tarjan (Preflow-Push)

Für das Max-Flow Problem und die ersten beiden Algorithmen finden Sie schon vollständige Seiten im Wiki (Übersicht auf der Main Page oder Suchfunktion). Die anderen beiden Algorithmen folgen.

Alle diese Algorithmen sind auf dem residualen Netzwerk zu implementieren. Für die reale Laufzeit (CPU-Zeit) gibt es keine Vorgaben, aber die jeweils im Wiki angegebene und bewiesene asymptotische Komplexität im Worst Case ist einzuhalten. Insbesondere können hashbasierte Datenstrukturen nicht verwendet werden, um Zugriff in konstanter Zeit zu realisieren, da nur im Average Case konstante Zugriffszeit garantiert ist.

Dazu zu implementieren ist ein Zufallsgenerator (ZG) für Instanzen des Max-Flow Problems in Standardversion mit ganzzahligen Kapazitäten. Die Knotenzahl und die maximale Kapazität sind Inputs für den ZG. Der ZG generiert einen gerichteten Graphen, der zu jeder vorhandenen Kante auch die Rückwärtskante enthält. Der Graph soll stark zusammenhängend sein. Für die Visualisierung soll er zudem planar sein, das heißt, die Knoten können so als Punkte in der Ebene platziert werden, dass keine zwei Kanten sich kreuzen, wenn sie als gerade Strecken gezeichnet werden. Genauer gesagt, soll der generierte Graph maximal planar sein, das heißt, keine Kante kann mehr eingefügt werden, ohne dass sie schon vorhandene Kanten kreuzt. Eine gut gangbare Möglichkeit, starken Zusammenhang und maximale Planarität zu erzielen, wäre etwa, die Knoten zufällig in einem Rechteck zu platzieren, die Knotenpaare nach ihrem Abstand zu sortieren und in dieser Reihenfolge jeweils das verbindende Kantenpaar einzufügen, falls dadurch nicht andere, schon vorher eingefügte Kantenpaare geschnitten werden. Es gibt aber auch effizientere Möglichkeiten, bei Interesse gerne mehr Informationen.

(Unwichtige Nebenbemerkung der Vollständigkeit halber: Planarität wird hier leicht verfälscht dargestellt. Ob die Kanten gerade oder kurvig sind, spielt keine Rolle dafür, ob ein Graph planar ist oder nicht. Und die generierten Graphen sind nicht zwangsläufig maximal planar im üblichen Sinne, weil eine andere Platzierung der Knoten in der Ebene noch weitere Einfügungen erlauben könnte.)

Weiter implementieren Sie eine einfache GUI mit Visualisierung. Mein Rat ist, die Pfeilspitzen der Kanten nicht zu zeichnen, die sind überflüssig. Die einzelnen Schritte des Algorithmus sollen in Einzelschritten durch Nutzeraktion oder automatisch mit wählbarer Zeitverzögerung durchlaufen werden. Durch die üblichen Stilmittel (Farbe, Dicke…) soll der momentane (Prä)Fluss auf jeder Kante gut erkennbar dargestellt werden. Bei den ersten drei Algorithmen soll der aktuell betrachtete flusserhöhende Pfad durch Betonung und Kontrast herausgehoben werden. Bei Preflow-Push sollen statt dessen der zu jedem Zeitpunkt garantierte saturierte Schnitt sowie die aktuelle Push-Kante herausgehoben werden.

Schließlich schreiben Sie unabhängig von der GUI noch eine kleine Testumgebung, die mit einer Folge von Tripeln (Anzahl Instanzen, Knotenzahl, maximale Kapazität) parametrisiert ist. Für jedes Tripel werden so viele Instanzen mit dieser Knotenzahl und dieser maximalen Kapazität generiert, wie der erste Wert im Tripel angibt. Jeder Algorithmus wird auf jede Instanz angewandt, und jede Nichtübereinstimmung der von den einzelnen Algorithmen berechneten Flusswerte wird für die Fehlersuche geeignet mitprotokolliert.

Realisieren Sie am Besten die Aufgabe auf Ihrem eigenen Laptop, den Sie dann auch zum Testatstermin mitbringen. Java, C, C++ und C# sind ok; für andere Programmiersprachen bitte ich vorab um Anfrage - am Besten im Forum. Sollte aber normalerweise kein Problem sein.

Falls Sie frühzeitig mit der Bearbeitung der Aufgabe beginnen wollen, können Sie schon mit ZG, GUI und Testumgebung beginnen, bevor die Algorithmen in der Vorlesung behandelt werden.

Fragen von allgemeinem Interesse am Besten im Forum. Wenn Sie einen einzelnen konkreten inhaltlichen Punkt ansprechen wollen, bietet es sich an, einen eigenen Thread dafür aufzumachen.

KW

Re: Übungsaufgabe WS 2014/15

Verfasst: 16. Okt 2014 18:01
von rrr
Hi, ich studiere Mathe mit Nebenfach Informatik und habe noch nie selbst eine GUI geschrieben, in GDI II haben wir die vorgegeben bekommen. Lernt man das als Informatiker, oder sind da alle auf diesem Stand?

Re: Übungsaufgabe WS 2014/15

Verfasst: 16. Okt 2014 18:14
von LucasR
Mir ist keine Veranstaltung bekannt, in der Informatiker das explizit lernen, wie man eine GUI schreibt… das wird sich so zwischendrin angeeignet. Ist aber gerade in Java/Scala auch nicht sonderlich schwierig. Relativ einfach ein JPanel und ein JFrame genommen, und darauf mit den unterschiedlichen draw() Methoden kleine Kreise, Linien und andere Sachen an gegebene Koordinaten gemalt :-) Da solltest du dich in wenigen Stunden einlesen können - inklusive testing, denn parallel zum Tutorial-Lesen solltest du immer dein Eclipse o.ä. offen haben und probieren :-)

Re: Übungsaufgabe WS 2014/15

Verfasst: 16. Okt 2014 21:35
von Matthias Senker
Ist es für die Visualisierung des Graphen erlaubt, eine entsprechende Library zu verwenden, oder sollen wir die Graphen tatsächlich von Grund auf selber zeichnen?

Re: Übungsaufgabe WS 2014/15

Verfasst: 16. Okt 2014 21:39
von Prof. Karsten Weihe
Matthias Senker hat geschrieben:Ist es für die Visualisierung des Graphen erlaubt, eine entsprechende Library zu verwenden, oder sollen wir die Graphen tatsächlich von Grund auf selber zeichnen?
Das Zeichnen der Graphen soll nicht der Fokus der Aufgabe sein - also ja, Sie können für die Visualisierung auch Libraries verwenden.

Die Algorithmen implementieren Sie natürlich von Grund auf selbst.

KW

Re: Übungsaufgabe WS 2014/15

Verfasst: 19. Okt 2014 20:16
von oe14ireg
1. Um diese Aufgabe kann man Bonus bekommen?
2. Beim Schreiben im WIKI, wie viel Bonus kann man maximal erhalten, und wie kann es schaffen?

Danke im Voraus.

Re: Übungsaufgabe WS 2014/15

Verfasst: 19. Okt 2014 20:19
von Prof. Karsten Weihe
oe14ireg hat geschrieben:1. Um diese Aufgabe kann man Bonus bekommen?
Nein, diese Aufgabe ist verbindlich.
oe14ireg hat geschrieben: 2. Beim Schreiben im WIKI, wie viel Bonus kann man maximal erhalten, und wie kann es schaffen?
Maximal 0.4 sind zu erreichen. Sie können den Bonus durch substantielle inhaltliche Beiträge erreichen. Das können neue Seiten sein oder Verbesserungen/Ergänzungen bestehender Seiten.

KW

Re: Übungsaufgabe WS 2014/15

Verfasst: 20. Nov 2014 16:05
von Mathematics
In der Übungsaufgabe heißt es, der Graph soll zu einer Kante stets auch die Rückwärtskante enthalten. Dazu habe ich zwei Fragen:
a) Soll die Rückwärtskante dieselbe Kapazität haben?
b) Soll der Residualgraph dann bis zu vier Kanten zwischen den mit der Ursprungskante inzidenten Knoten haben (zwei hin, zwei zurück)? Oder sollen diese jeweils aufaddiert werden zu maximal zwei Kanten (eine hin, eine zurück)?

Re: Übungsaufgabe WS 2014/15

Verfasst: 20. Nov 2014 16:10
von Prof. Karsten Weihe
Mathematics hat geschrieben: a) Soll die Rückwärtskante dieselbe Kapazität haben?
Nein, dafür gibt es meines Erachtens keinen Grund.

Mathematics hat geschrieben: b) Soll der Residualgraph dann bis zu vier Kanten zwischen den mit der Ursprungskante inzidenten Knoten haben (zwei hin, zwei zurück)? Oder sollen diese jeweils aufaddiert werden zu maximal zwei Kanten (eine hin, eine zurück)?
Beides wäre ok.

KW

Re: Übungsaufgabe WS 2014/15

Verfasst: 23. Nov 2014 00:37
von hhh
Ist JavaScript auch ok?

Re: Übungsaufgabe WS 2014/15

Verfasst: 23. Nov 2014 08:14
von Prof. Karsten Weihe
hhh hat geschrieben:Ist JavaScript auch ok?
Ja.

KW

Re: Übungsaufgabe WS 2014/15

Verfasst: 27. Feb 2015 16:53
von hanneswernery
Ich habe noch eine Frage zum Graphen-Generieren.
Wie sollen wir festlegen in welche Richtung eine Kante "hin" und in welche Richtung sie "zurück" geht?

Wenn ich es per Zufall setze, bekomme ich oft eine sehr unschöne/niedrige Lösung.
Wenn ich es "von links nach rechts" (von S zu T) laufen lasse, haben wir einen sehr künstlichen Graphen links-rechts Graphen
Wenn ich es in dem Moment festlege, indem ich die Kante das erste mal brauche (Richtung on-the-fly festlegen), bekomme ich ein künstlich sehr gutes Ergebnis.

Oder ist mir das komplett freigestellt?
MFG

Re: Übungsaufgabe WS 2014/15

Verfasst: 27. Feb 2015 17:31
von Prof. Karsten Weihe
hanneswernery hat geschrieben: Oder ist mir das komplett freigestellt?
Ja, basteln Sie es so hin, dass ordentliche Instanzen herauskommen. 8)

KW

Re: Übungsaufgabe WS 2014/15

Verfasst: 18. Mär 2015 04:36
von philipp_m
Repräsentiert dieser Thread den aktuellsten Stand der Aufgabenstellung? Ich kann mich nämlich daran erinnern, dass in einer der Vorlesungen zum Max Flow Problem eine Abänderung der Aufgabenstellung (genauer: der zu generierenden Graphen) erwähnt wurde.

Zudem verstehe ich die obige Frage im Zusammenhang mit der Problemstellung nicht:
"Wie sollen wir festlegen in welche Richtung eine Kante "hin" und in welche Richtung sie "zurück" geht?"
Laut Aufgabenstellung soll ja zu jeder Kante a1=(v,w) auch die Rückwärtskante a2=(w,v) im Graph sein. Dabei sollen beide Kanten a1,a2 jeweils eine zufällige Kapazität u(a1) bzw. u(a2) haben, wobei diese jeweils unter der festgelegten maximalen Kapazität liegt. Inwiefern ist nun also die Richtung einer einzelnen Kante relevant, wenn es ja sowieso immer auch eine Kante in die entgegengesetzte RIchtung gibt?

Und noch zwei weitere Fragen...

Zur Connectedness:
"Der Graph soll stark zusammenhängend sein."
Folgt aus obiger Bedingung (jeweils eine Kante in Rückrichtung) nicht, dass aus schwachem Zusammenhang auch direkt starker Zusammenhang folgt, da ja keine Kanten umgedreht werden müssen, wenn sowieso jeweils eine Kante in die andere Richtung existieren muss?

Zur Generierung der Graphen:
Habe ich den vorgeschlagenen Algorithmus so richtig verstanden?
1. Knoten zufällig in Rechteck legen (wie zufällig muss hier gearbeitet werden? ist eine EInschränkung hinsichtlich der Darstellbarkeit wie zB. durch Mindestabstände gewünscht?)
2. Knotenpaare nach ihrem Abstand sortieren
3. Beim geringsten Abstand anfangend für jedes Knotenpaar zwei Kanten (hin und zurück, je zufällige Kapazität kleiner max. Kapazität) einfügen, falls diese keine anderen Kanten schneiden
Start- und Zielknoten zufällig setzen?

Re: Übungsaufgabe WS 2014/15

Verfasst: 18. Mär 2015 10:22
von Prof. Karsten Weihe
philipp_m hat geschrieben:Repräsentiert dieser Thread den aktuellsten Stand der Aufgabenstellung? Ich kann mich nämlich daran erinnern, dass in einer der Vorlesungen zum Max Flow Problem eine Abänderung der Aufgabenstellung (genauer: der zu generierenden Graphen) erwähnt wurde.
Ich nehme an, Sie meinen die Frage, ob der Graph symmetrisch oder anti-symmetrisch sein soll? Beides ist ok.

philipp_m hat geschrieben: Zudem verstehe ich die obige Frage im Zusammenhang mit der Problemstellung nicht:
"Wie sollen wir festlegen in welche Richtung eine Kante "hin" und in welche Richtung sie "zurück" geht?"
Laut Aufgabenstellung soll ja zu jeder Kante a1=(v,w) auch die Rückwärtskante a2=(w,v) im Graph sein. Dabei sollen beide Kanten a1,a2 jeweils eine zufällige Kapazität u(a1) bzw. u(a2) haben, wobei diese jeweils unter der festgelegten maximalen Kapazität liegt. Inwiefern ist nun also die Richtung einer einzelnen Kante relevant, wenn es ja sowieso immer auch eine Kante in die entgegengesetzte RIchtung gibt?
Auf anti-symmetrischen Graphen ist der Residualgraph einfacher zu implementieren, aber dann gibt es nicht unbedingt Pfade von s nach t, dieses Problem muss man nicht lösen, wenn der Graph symmetrisch ist. Bei einem symmetrischen Graphen müssten Sie so vorgehen: Für zwei Kanten (v,w) und (w,v), die residuale Kapazität von (v,w) wäre die Summe aus den aus (v,w) selbst und aus (w,v) induzierten residualen Kapazitäten: c(v,w)-f(v,w)+f(w,v). Klar?

philipp_m hat geschrieben: "Der Graph soll stark zusammenhängend sein."
Folgt aus obiger Bedingung (jeweils eine Kante in Rückrichtung) nicht, dass aus schwachem Zusammenhang auch direkt starker Zusammenhang folgt, da ja keine Kanten umgedreht werden müssen, wenn sowieso jeweils eine Kante in die andere Richtung existieren muss?
Ist das durch die obigen Erläuterungen beantwortet?

philipp_m hat geschrieben: Zur Generierung der Graphen:
Habe ich den vorgeschlagenen Algorithmus so richtig verstanden?
Generell sind Sie frei darin, die zufällige Erzeugung so zu gestalten, dass aussagekräftige, leicht zu durchschauende Instanzen herauskommen. 8)

KW