Hallo und Programmieraufgaben
Moderator: Effiziente Graphenalgorithmen
-
- Dozentin/Dozent
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Hallo und Programmieraufgaben
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
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
Re: Hallo und Programmieraufgaben
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?
2. Ist die Verwendung von z.B. LWJGL für die Visualisierung des Graphen bei Verwendung von Java zulässig?
Vielen Dank im voraus.
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
Vielen Dank im voraus.
-
- Dozentin/Dozent
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Re: Hallo und Programmieraufgaben
Mist, ich hatte beim Schreiben noch an diesen Punkt gedacht, aber dann doch vergessen...jls hat geschrieben: 1. Können wir Trennzeichen, die Darstellung von Paaren etc. frei wählen oder gibt es eine feste Vorgabe?

Ich denke, das praktikabelste wäre, dass alle Whitespaces in beliebiger Zahl Trennung sein dürfen.
Es ist alles zulässig außer die Verwendung von fremdem Code, der wesentliche Teile der Algorithmen implementiert.jls hat geschrieben: 2. Ist die Verwendung von z.B. LWJGL für die Visualisierung des Graphen bei Verwendung von Java zulässig?
Anforderung ist, dass Sie einen Laptop o.ä. mitbringen, auf dem Ihre Implementation dann läuft.
Klar soweit?
KW
Re: Hallo und Programmieraufgaben
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?

Die einzelnen Paare sowie der erste Wert (Zahl der Knoten) können zur besseren Übersicht je in eine eigene Zeile?
-
- Dozentin/Dozent
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Re: Hallo und Programmieraufgaben
Semikolajls hat geschrieben:statt den Semikoli beliebig viele Leerzeichen.


Anstelle der Semikola beliebig viele Whitespaces, also Spaces (Leerzeichen), Tabs, Newlines usw.
KW
Re: Hallo und Programmieraufgaben
Können wir davon ausgehen das die Koordinaten "Informatiker freundlich" sind? also (0,0) ist oben links, und es gibt keine negativen Koordinaten?
-
- Dozentin/Dozent
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Re: Hallo und Programmieraufgaben
Sie können die Koordinaten so definieren, wie es Ihnen recht ist.tacu hat geschrieben:Können wir davon ausgehen das die Koordinaten "Informatiker freundlich" sind? also (0,0) ist oben links, und es gibt keine negativen Koordinaten?


KW
Re: Hallo und Programmieraufgaben
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? 

-
- Dozentin/Dozent
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Re: Hallo und Programmieraufgaben
Ooooops, ich bin blindlings dem Link in der Email-Benachrichtigung gefolgt und dachte, ich wäre im Forum zur LV Optimierungsalgorithmen gelandet.tacu hat geschrieben: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?



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
-
- Erstie
- Beiträge: 22
- Registriert: 22. Mär 2010 21:22
Re: Hallo und Programmieraufgaben
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
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
-
- Dozentin/Dozent
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Re: Hallo und Programmieraufgaben
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.Gallontzke hat geschrieben: Wir betrachten ja endliche Graphen in den Aufgaben, können wir dann von einer Obergrenze der Koordinaten ausgehen?
Beantwortet das Ihre Frage?
KW
-
- Erstie
- Beiträge: 22
- Registriert: 22. Mär 2010 21:22
Re: Hallo und Programmieraufgaben
Vollkommen, danke.Beantwortet das Ihre Frage?
Re: Hallo und Programmieraufgaben
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.
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.
-
- Dozentin/Dozent
- Beiträge: 1824
- Registriert: 21. Feb 2005 16:33
Re: Hallo und Programmieraufgaben
Ja, sorry, dass ich diesen Punkt vergessen hatte!co09vago hat geschrieben: 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.

KW
-
- Endlosschleifenbastler
- Beiträge: 172
- Registriert: 6. Okt 2011 15:25
Re: Hallo und Programmieraufgaben
Hallo,
gibt es denn schon ein paar Beispiel Dateien zum reinschnuppern?
Grüße
gibt es denn schon ein paar Beispiel Dateien zum reinschnuppern?
Grüße