Übungen zur Vorlesung „Zeichnen von Graphen“ (Sommersemester 2009)
|
+++ Aktuelles +++ 09.07.2009: Am Dienstag, den 14.07.2009 fällt die Vorlesung aus |
Grundlage für die effektive und effiziente Visualisierung von Netzwerken sind Algorithmen zur Bestimmung eines Layouts für den die Netzwerkstruktur beschreibenden Graphen. Das automatische Zeichnen von Graphen hat daher wichtige Anwendungen in Kernbereichen der Informatik wie etwa Datenbanken, Software-Engineering, VLSI- und Netzwerk-Design und visuelle Benutzerschnittstellen. Anwendungen in anderen Bereichen betreffen alle Aspekte der visuellen Datenanalyse, z.B. in den Ingenieurwissenschaften, Chemie und Biologie oder Sozial- und Politikwissenschaft. Dazu werden verschiedene algorithmische Prinzipien und Methoden wie z.B. kräftebasierte Verfahren und Flussmethoden besprochen.
|
Termine
| Vorlesung (U. Brandes, S. Cornelsen) | Di 08.30–10.00 (D 404) Mi 08.30–10.00 (D 436) |
| Übung (M. Mader, C. Pich) | Mo 14.00–16.00 (D 406) |
| mündliche Prüfungen | nach Vereinbarung |
Übungsblätter
Die theoretischen Aufgaben werden mittwochs als Übungsblätter in der Vorlesung ausgegeben, sind innerhalb einer Woche bis Freitagmorgen zu bearbeiten, und werden als schriftliche Ausarbeitungen im Treppenhaus vor dem Sekretariat des Lehrstuhls (Raum E 214) abgegeben.
Daneben gibt es praktische Aufgaben, in denen Algorithmen zum Zeichnen von Graphen entworfen und in Java implementiert und getestet werden. In vier dreiwöchigen Projekten werden Layoutprobleme aus verschiedenen Teilgebieten behandelt, für die Lösungen erarbeitet und an praktischen Beispielen erprobt werden.
Die Besprechung aller Aufgaben und die Rückgabe der korrigierten und mit Punkten bewerteten Abgaben erfolgt in der Übung. Das Erlangen von mindestens der Hälfte der möglichen Punkte und die aktive Teilnahme an den Übungen ist Voraussetzung für die Zulassung zur Prüfung.
Alle Aufgaben können und sollen in Zweiergruppen abgegeben werden.
| Nr. | Ausgabe | Abgabe | Besprechung | Download |
|---|---|---|---|---|
| 1 | 22.04.2009 | 30.04.2009 | 04.05.2009 | |
| 2 | 29.04.2009 | 08.05.2009 | 11.05.2009 | |
| 3 | 06.05.2009 | 15.05.2009 | 18.05.2009 | |
| 4 | 13.05.2009 | 22.05.2009 | 25.05.2009 | |
| 5 | 20.05.2009 | 29.05.2009 | 08.06.2009 | |
| 6 | 27.05.2009 | 05.06.2009 | 08.06.2009 | |
| 7 | 03.06.2009 | 12.06.2009 | 15.06.2009 | |
| 8 | 10.06.2009 | 19.06.2009 | 22.06.2009 | |
| 9 | 17.06.2009 | 26.06.2009 | 29.06.2009 | |
| 10 | 24.06.2009 | 03.07.2009 | 06.07.2009 | |
| 11 | 01.07.2009 | 08.07.2009 | 13.07.2009 | |
| 12 | 09.07.2009 | 17.07.2009 | 20.07.2009 |
Hinweis: Einige Dokumente sind nur lokal lesbar.
Praktische Aufgaben
Für die praktischen Aufgaben wird die Bibliothek yFiles verwendet. Die Lösungen sind als Quellcode per Email zu versenden.
| Nr. | Ausgabe | Abgabe | Besprechung | Download |
|---|---|---|---|---|
| 1 | 22.04.2009 | 15.05.2009 | 18.05.2009 | PDF, BinaryTreeGenerator.java |
| 2 | 22.05.2009 | 12.06.2009 | 15.06.2009 | PDF, yEd-Beispiel zu Optionsdialogen, st-Graph (Beispiel) |
| 3 | 17.06.2009 | 10.07.2009 | 13.07.2009 |
Hinweis: Einige Dokumente sind nur lokal lesbar.
- Einführung in die Programmierumgebung
- yFiles Developer's Guide
- yFiles-Beispiele, für Anfänger v.a. interessant: Base Demos
- yFiles 2.4.0.1 API Documentation
Skriptum
Grundlage ist das Skript der Veranstaltung im Sommersemester 2007. Dieses wird im Verlauf des Semesters ergänzt und überarbeitet. Für Anmerkungen und Hinweise auf Fehler sind wir dankbar.
Ergänzende Schriften:
- Kurzskripte zu Grundlagen
- Kapitel 1 aus dem Skriptum zur Vorlesung "Entwurf und Analyse von Algorithmen" von Prof. Wagner über Rekursion
- Originalartikel zum Verfahren für die x-Koordinatenzuweisung im Sugiyama-Ansatz
Literatur
- G. Di Battista, P. Eades, I.G. Tollis, R. Tamassia: "Graph Drawing: Algorithms for the Visualization of Graphs". Prentice Hall, 1999
- M. Jünger, P. Mutzel (Eds.): "Graph Drawing Software" Mathematics and Visualization Series, Springer-Verlag, 2003
- M. Kaufmann, D. Wagner (Eds.): "Drawing Graphs -- Methods and Models". Lecture Notes in Computer Science Tutorial 2025, Springer-Verlag 2001
- K. Sugiyama: "Graph Drawing and Applications for Software and Knowledge Engineers". World Scientific, 2002
Weitere Informationen
- Eintrag im Vorlesungsverzeichnis
- Informationen zum Account-Tool
- Java Demo Applet (Spring Embedder)
- Anwendungsbeispiele für das Zeichnen von Graphen
- Konferenz: Graph Drawing 2009 (mit Wettbewerb zum Thema Graphenzeichnen)