Hallo und Programmieraufgaben

[Prof. Karsten Weihe]

Hallo allerseits,

dies ist der erste Thread des WS 2013/14, und ich darf Sie auch auf diesem Wege noch einmal herzlich willkommen heißen!

Als Programmieraufgaben implementieren Sie drei Algorithmen aus der Vorlesung:

1. Aus Abschnitt 2: Berechnung der starken Zusammenhangskomponenten eines gerichteten Graphen (strongly connected components (SCC) of a digraph).

2. Aus Abschnitt 2: Eulers Algorithmus zur Berechnung eines Eulerkreises (Eulerian walk).

3. Aus Abschnitt 3: Edmonds' Algorithmus zur Berechnung eines optimalen Branchings.

Für jeden der drei Algorithmen sind durchzurechnende Beispiel aus ASCII-Textdateien einzulesen. Das Dateiformat ist wie folgt: (1) die Anzahl N der Knoten; (2) N Paare von reellen Zahlen, die zweidimensionalen Koordinaten der Knoten; (3) eine beliebig große Anzahl von Paaren von Zahlen {1..N}, die Kanten des Graphen. Ihre Programme dürfen ohne Prüfung des Dateiinhalts davon ausgehen, dass jeder einzulesende Graph einfach (simple) ist.

Das Ergebnis soll in einem Fenster visualisiert werden (zum Zwecke der Fehlersuche mag eine zusätzliche Dateiausgabe des Ergebnisses anzuraten sein). Die Knoten werden gemäß den Koordinaten aus der Eingabedatei platziert, und zwar so, dass das Ausgabefenster möglichst gut ausgefüllt wird (mit einem kleinen freigelassenen Bereich am Fensterrand, damit das Gesamtbild noch ästhetisch ansprechend bleibt). Kanten dürfen durchaus einfach als gerade Strecken gezeichnet, wobei Sie sich überlegen müssen, wie Sie die Pfeilrichtung gut lesbar darstellen und wie Sie zwei zueinander gegenläufige Kanten verständlich darstellen.

Für den ersten Algorithmus soll es in der Ausgabe möglich sein, jeweils alle SCC bis auf eine zu schattieren („auszugrauen“), so dass man sich jede einzelne SCC fokussiert anschauen kann, aber im Hintergrund immer noch den ganzen Graphen sieht.

Beim zweiten Algorithmus soll die Reihenfolge der Kanten auf dem Eulerkreis animiert visualisiert werden, indem die Kanten in einer Endlosschleife reihum eine kurze Zeit besonders hervorgehoben werden. Bei zwei zueinander gegenläufigen Kanten sollte aber in jedem Schritt deutlich sichtbar sein, welche der beiden Kanten jeweils die hervorgehobene ist.

Beim dritten Algorithmus reicht die Darstellung des Ergebnisses durch Hervorhebung derjenigen Kanten, die zum berechneten optimalen Branching gehören (auch hier wieder die klare Unterscheidung bei zueinander gegenläufigen Kanten).

In jedem der drei Fälle soll Ihre Implementation die asymptotische Komplexität gemäß Vorlesung erreichen. Anders gesagt: Es sollen nicht durch nachlässiges Design unnötige weitere Faktoren in die asymptotische Komplexität hineinkommen.

Da Ihre Implementationen nur Beispiele lösen sollen, die ausreichend klein sind, um sie gut am Bildschirm darzustellen, müssen sie nicht darüber hinaus auf Effizienz optimiert sein, also keine Programmiertricks zur Effizienzsteigerung verlangt.

C, C++, C#, Java und Scala sind ok. Falls Sie eine andere Sprache verwenden möchten, kontaktieren Sie mich bitte zuerst.

Rückfragen bitte hier im Forum, an Besten in diesem Thread.

KW

[jls]

Ich hätte folgende Fragen;
1. Können wir Trennzeichen, die Darstellung von Paaren etc. frei wählen oder gibt es eine feste Vorgabe? Wenn ja, wäre ich dankbar für eine Beispiel- Eingabedatei. Wäre folgendes ansonsten z.B. eine korrekte Eingabedatei?

Code: Alles auswählen

3
2.4;5.1
1.8;3.6
9.3;2.0
1;3
2;3

2. Ist die Verwendung von z.B. LWJGL für die Visualisierung des Graphen bei Verwendung von Java zulässig?

Vielen Dank im voraus.

[Prof. Karsten Weihe]

1. Können wir Trennzeichen, die Darstellung von Paaren etc. frei wählen oder gibt es eine feste Vorgabe?

Mist, ich hatte beim Schreiben noch an diesen Punkt gedacht, aber dann doch vergessen...

Ich denke, das praktikabelste wäre, dass alle Whitespaces in beliebiger Zahl Trennung sein dürfen.

2. Ist die Verwendung von z.B. LWJGL für die Visualisierung des Graphen bei Verwendung von Java zulässig?

Es ist alles zulässig außer die Verwendung von fremdem Code, der wesentliche Teile der Algorithmen implementiert.

Anforderung ist, dass Sie einen Laptop o.ä. mitbringen, auf dem Ihre Implementation dann läuft.

Klar soweit?

KW

[jls]

Danke Also wie in meinem Beispiel, nur statt den Semikoli beliebig viele Leerzeichen.
Die einzelnen Paare sowie der erste Wert (Zahl der Knoten) können zur besseren Übersicht je in eine eigene Zeile?

[Prof. Karsten Weihe]

statt den Semikoli beliebig viele Leerzeichen.

Semikola

Anstelle der Semikola beliebig viele Whitespaces, also Spaces (Leerzeichen), Tabs, Newlines usw.

KW

[tacu]

Können wir davon ausgehen das die Koordinaten "Informatiker freundlich" sind? also (0,0) ist oben links, und es gibt keine negativen Koordinaten?

[Prof. Karsten Weihe]

Können wir davon ausgehen das die Koordinaten "Informatiker freundlich" sind? also (0,0) ist oben links, und es gibt keine negativen Koordinaten?

Sie können die Koordinaten so definieren, wie es Ihnen recht ist.

KW

[tacu]

Hab ich dann etwas falsch verstanden? ich bin davon ausgegangen das Sie bei der Besprechung der Aufgaben einen eigenen Graphen einlesen. Also das unser Code in der Lage sein soll ein von Ihnen erstelltes Textfile einzulesen. Lag ich da falsch?

[Prof. Karsten Weihe]

Hab ich dann etwas falsch verstanden? ich bin davon ausgegangen das Sie bei der Besprechung der Aufgaben einen eigenen Graphen einlesen. Also das unser Code in der Lage sein soll ein von Ihnen erstelltes Textfile einzulesen. Lag ich da falsch?

Ooooops, ich bin blindlings dem Link in der Email-Benachrichtigung gefolgt und dachte, ich wäre im Forum zur LV Optimierungsalgorithmen gelandet.

Dort hätte diese Frage ebenfalls Sinn gemacht (meine Antwort auch).

Also noch einmal zurück auf Los: Ja, oben links ist (0,0).

KW

[Gallontzke]

Hallo.
Wir betrachten ja endliche Graphen in den Aufgaben, können wir dann von einer Obergrenze der Koordinaten ausgehen?
Untergrenze ist ja (0,0). Das ist ja eigentlich o.B.d.A. möglich. Ich denke, das begrenzt nicht die Anzeige der Funktionsweise der Algorithmen.
Ich frage deshalb, weil einige Arbeiten Richtung scrollen/zoomen bei der Anzeige dann wegfallen.
LG

[Prof. Karsten Weihe]

Wir betrachten ja endliche Graphen in den Aufgaben, können wir dann von einer Obergrenze der Koordinaten ausgehen?

Bei endlich vielen Knoten = Punkten in der Ebene liegen natürlich alle x-Werte bzw. alle y-Werte jeweils in einem beschränkten Intervall \([x_\min\ldots x_\max]\times[y_\min\ldots y_\max]\). Dieses Rechteck können (und dürfen) Sie natürlich immer durch eine affin-lineare Transformation in das Zeichenrechteck einpassen.

Beantwortet das Ihre Frage?

KW

[Gallontzke]

Beantwortet das Ihre Frage?

Vollkommen, danke.

[co09vago]

Hallo,
für den dritten Aufgabenteil werden wir Kantengewichte brauchen.
Fallen die Kantengewichte unter Punkt (3) des Formats für die Eingabe?
3 7 5 würde dann heissen Knoten 3 hat eine gerichtete Kante zu Knoten 7 mit Gewicht 5.
Falls die Gewichte anders dargestellt werden sollen würde ich mich über eine Beispieldatei freuen.

[Prof. Karsten Weihe]

für den dritten Aufgabenteil werden wir Kantengewichte brauchen.
Fallen die Kantengewichte unter Punkt (3) des Formats für die Eingabe?
3 7 5 würde dann heissen Knoten 3 hat eine gerichtete Kante zu Knoten 7 mit Gewicht 5.
Falls die Gewichte anders dargestellt werden sollen würde ich mich über eine Beispieldatei freuen.

Ja, sorry, dass ich diesen Punkt vergessen hatte!

KW

[Thomas Huxhorn]

Hallo,

gibt es denn schon ein paar Beispiel Dateien zum reinschnuppern?

Grüße