Übungsaufgabe WS 2014/15

Moderator: Effiziente Graphenalgorithmen

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Übungsaufgabe WS 2014/15

Beitrag von Prof. Karsten Weihe » 15. Okt 2014 09:28

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

rrr
Neuling
Neuling
Beiträge: 1
Registriert: 16. Okt 2014 17:55

Re: Übungsaufgabe WS 2014/15

Beitrag von rrr » 16. Okt 2014 18:01

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?

LucasR
Kernelcompilierer
Kernelcompilierer
Beiträge: 474
Registriert: 9. Jun 2009 09:55

Re: Übungsaufgabe WS 2014/15

Beitrag von LucasR » 16. Okt 2014 18:14

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 :-)

Matthias Senker
Windoof-User
Windoof-User
Beiträge: 41
Registriert: 14. Okt 2010 22:42

Re: Übungsaufgabe WS 2014/15

Beitrag von Matthias Senker » 16. Okt 2014 21:35

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?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übungsaufgabe WS 2014/15

Beitrag von Prof. Karsten Weihe » 16. Okt 2014 21:39

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

oe14ireg
Neuling
Neuling
Beiträge: 6
Registriert: 14. Jul 2013 17:23

Re: Übungsaufgabe WS 2014/15

Beitrag von oe14ireg » 19. Okt 2014 20:16

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.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übungsaufgabe WS 2014/15

Beitrag von Prof. Karsten Weihe » 19. Okt 2014 20:19

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

Mathematics
Erstie
Erstie
Beiträge: 17
Registriert: 23. Sep 2013 12:12

Re: Übungsaufgabe WS 2014/15

Beitrag von Mathematics » 20. Nov 2014 16:05

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

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übungsaufgabe WS 2014/15

Beitrag von Prof. Karsten Weihe » 20. Nov 2014 16:10

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

hhh
Neuling
Neuling
Beiträge: 1
Registriert: 23. Nov 2014 00:25

Re: Übungsaufgabe WS 2014/15

Beitrag von hhh » 23. Nov 2014 00:37

Ist JavaScript auch ok?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übungsaufgabe WS 2014/15

Beitrag von Prof. Karsten Weihe » 23. Nov 2014 08:14

hhh hat geschrieben:Ist JavaScript auch ok?
Ja.

KW

hanneswernery
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 30. Dez 2012 15:26

Re: Übungsaufgabe WS 2014/15

Beitrag von hanneswernery » 27. Feb 2015 16:53

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

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übungsaufgabe WS 2014/15

Beitrag von Prof. Karsten Weihe » 27. Feb 2015 17:31

hanneswernery hat geschrieben: Oder ist mir das komplett freigestellt?
Ja, basteln Sie es so hin, dass ordentliche Instanzen herauskommen. 8)

KW

philipp_m
Mausschubser
Mausschubser
Beiträge: 99
Registriert: 4. Dez 2010 18:10

Re: Übungsaufgabe WS 2014/15

Beitrag von philipp_m » 18. Mär 2015 04:36

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?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Übungsaufgabe WS 2014/15

Beitrag von Prof. Karsten Weihe » 18. Mär 2015 10:22

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

Antworten

Zurück zu „Effiziente Graphenalgorithmen“