This page is for a student project regarding the OGDF.

If you are looking for the official site, please go to WWW.OGDF.NET!




Projektgruppe 478

OGDF: An Open Graph Drawing Framework

Inhalt

Zeitraum

WS 2005/06 & SS 06

Umfang

8 SWS pro Semester

Veranstalter

Prof. Petra Mutzel, Markus Chimani, Carsten Gutwenger, Karsten Klein
Informatik LS 11

Kontakt

Karsten Klein
karsten.klein (at) cs.uni-dortmund.de

Aufgabe

Beim Graphenzeichnen geht es darum, Graphen - bzw. Diagramme, die durch Graphen modelliert werden können - nach formalen und ästhetischen Kriterien zu zeichnen. Die Platzierung der Graphenelemente (Knoten, Kanten, Attribute, ...) bezeichnet man als Layout. Ziel ist es, effizient eine übersichtliche Zeichnung automatisch zu generieren. Solche Diagramme treten in der Praxis in unterschiedlichen Formen auf:

Je nach Anwendungsanforderung werden verschiedene Algorithmen zur Berechnung von Layouts herangezogen. Die Komplexität der vielfältigen Verfahren reicht von einfach bis sehr anspruchsvoll. Viele der dabei auftretenden Probleme stellen eine Herausforderung für die aktuelle wissenschaftliche Forschung dar. Das Gebiet des Graphenzeichnens vereint dabei unter anderem Grundlagen aus Algorithmik, Graphentheorie, Kombinatorik und Visualisierung. Im Bereich des interaktiven Zeichnens werden auch Ergebnisse aus psychologischen Studien herangezogen.

Es existiert bereits eine Reihe von Softwarepaketen für das automatische Graphenzeichnen, sowohl aus dem kommerziellen als auch aus dem akademischen Bereich. Eines dieser Pakete ist die C++ Bibliothek AGD (Algorithms for Graph Drawing), die zu Forschungszwecken an den Universitäten Saarbrücken, Köln, Halle, Wien und Dortmund entwickelt wurde. Im Laufe der Jahre haben sich dabei diverse Abhängigkeiten zu kommerziellen Softwarepaketen ergeben, die der weiteren Forschung hinderlich sind. Daher wurde mit der Entwicklung einer freien Alternative begonnen, dem Open Graph Drawing Framework (OGDF), dessen Funktionsumfang allerdings noch relativ beschränkt ist. Das OGDF ist ebenfalls eine C++ Bibliothek inklusive einem Grapheneditor.

Im Rahmen dieser Projektgruppe soll auf Basis des bestehenden Open-GD-Frameworks eine Erweiterung dieser Bibliothek in folgenden Bereichen vorgenommen werden:

Es ist uns ein Anliegen, den Teilnehmern der Projektgruppe durch die breite Auswahl der genannten Themen die Vielfalt des Gebietes des Graphenzeichnens anschaulich zu machen und Interesse für die weitere Beschäftigung damit zu wecken.

Teilnahmevoraussetzungen

C++ Kenntnisse (V) SoPra (V)
DAP2 (V) Effiziente Algorithmen (V)
Softwaretechnik (W)    

Minimalziele

  1. Lauffähiger Editor
  2. Unterstützung von Compounds inklusive mindestens eines Layoutalgorithmus
  3. Unterstützung von Constraint-Mechanismen inklusive geeigneter Layoutalgorithmen
  4. Unterstützung eines geeigneten Dateiformats (für Compounds, Constraints, Semantik)
  5. Teilberichte und Abschlussbericht

Realisierung

Übersicht

Den Teilnehmern der Projektgruppe wird die Gelegenheit gegeben, einen eigenen genauen Projektplan zu erstellen, in welchem sie ihre Schwerpunkte selbst setzen können. Dies geschieht natürlich in Abstimmung mit den Veranstaltern, und im Rahmen des unten angegebenen Grundgerüsts. Nachdem es Ziel dieser PG ist, ein möglichst weites Feld des Graphenzeichnens zu beleuchten, beruht der Projektplan auf der im Folgenden dargestellten iterativen Abfolge.

  1. Seminarphase: Diese Phase dient dazu, den Studierenden das Thema des Graphenzeichens nahezubringen. Dazu erhalten die Teilnehmer in der letzten Woche der Vorlesungszeit des SS 2005 Themen für Seminarvorträge sowie Hinweise auf relevante Literatur. Durch die in den ersten Wochen des Wintersemesters von ihnen gehaltenen Vorträge, sollen alle Studenten einen möglichst breiten Einblick in die Thematik gewinnen.
    Die Vortragsserie wird durch die Veranstalter abgeschlossen, in dem sie eine Einführung in die für die Projektgruppe wichtigen Bibliotheken AGD und OGDF geben.

  2. Generelle Planungssitzungen: Hier werden die Aufgabenstellungen besprochen, Schwerpunkte gesetzt und ein Projektplan erarbeitet. Darüber hinaus wird hier eine erste Zuteilung der Studenten zu ihrem ersten Spezialisierungsthema durch die Studenten selbst vorgenommen.
    Für die Projektgruppe werden ein Projektmanager sowie ein Stellvertreter gewählt, die für das Zusammenspiel der einzelnen Komponenten verantwortlich zeichnen; auch in den entstehenden Kleingruppen wird ein definierter Teilprojektleiter bestimmt.

  3. Spezialisierungsphasen: Die Studenten arbeiten sich in den speziellen Themenkreis ihrer Aufgabenstellung ein und entwickeln in den Kleingruppen passende Lösungskonzepte. Danach werden diese realisiert, getestet und ins OGDF integriert. Darüber hinaus wird ein Abschlussteilbericht erstellt.

  4. Generelle Zwischensitzungen: In regelmässigen Abständen (alle 2 Wochen) finden Treffen der gesamten PG statt, um sowohl fachliche als auch gruppendynamische Probleme zu besprechen, über das Vorankommen der einzelnen Gruppen zu berichten sowie weitere Planungen vorzunehmen. Immer wenn eine Kleingruppe mit der ihr zugeteilten Aufgabe fertig ist, sucht sie sich aus dem Pool der Themen ein weiteres heraus. Zu diesem Zeitpunkt sind auch personelle Wechsel innerhalb der Gruppen möglich und wünschenswert. Die Gruppen treten sodann abermals in eine Spezialisierungsphase ein.

  5. Generelle Abschlusssitzungen: Am Ende der PG wird ein Abschlussbericht erstellt, der sich im wesentlichen aus einem zusammenfassenden Teil sowie den Abschlussteilberichten zusammensetzt. Darüber hinaus werden resümierend Fehler und Erfolgspunkte analysiert.

Während der gesamten Projektarbeit wird großer Wert auf Dokumentation, selbstständige Projektorganisation, und Validierung der Ergebnisse gelegt. Die Veranstalter sind sich jedoch darüber im Klaren, dass sie vor allem bei den beiden letzen Punkten gegenenfalls helfend eingreifen werden müssen.

Zeitplan

Siehe obigen Abschnitt für die ausführliche Beschreibung der einzelnen Arbeitsschritte.

42.+43. KW:
Seminarphase

44.-45. KW:
Generelle Planungssitzungen

46.-50. KW:
Spezialisierungsphase I (Schwerpunkt Editor), Zwischenbericht

51.-1. KW:
Weihnachtsferien

2.-6. KW:
Spezialisierungsphase II (Schwerpunkt Compounds), Zwischenbericht

7.-13. KW:
Semesterferien

14.-20. KW:
Spezialisierungsphase III (Schwerpunkt Constraints&Animation), Zwischenbericht

21.-25. KW:
Pufferzeit, Integrationstests, Code-Cleaning, Verfeinerungen

26.-28. KW:
Fertigstellung des Endberichts, Generelle Abschlusssitzungen

Erweiterungsmöglichkeiten

Auf eine genaue Auflistung der Zeichenalgorithmen, beispielsweise für Compound-Graphen, wurde ob der schieren Anzahl verzichtet, und es ist - in Absprache mit den Veranstaltern - den Studenten überlassen welche Algorithmen sie für besonders interessant und implementierungswürdig erachten. Dadurch, und da das Gebiet des Graphenzeichnens eine rasante Entwicklung zu verzeichnen hat, ist eine Bibliothek wie das OGDF natürlich nie richtig fertig, und ihre Erweiterbarkeit ist auch innerhalb der Projektgruppe oberstes Gebot. Aufgrund der Tatsache, dass der veranstaltende Lehrstuhl die Bibliothek in der täglichen wissenschaftlichen Forschung anwendet und erweitert, wird der beiderseitige Nutzen der PG deutlich.

Literatur

Einführungsartikel zum Graphenzeichnen

BJM97
F.-J. Brandenburg, M. Jünger, and P. Mutzel.
Algorithmen zum automatischen Zeichnen von Graphen.
Informatik-Spektrum, 20(4):199-207, 1997.

Mut
Petra Mutzel.
Zeichnen von Diagrammen -- Theorie und Praxis.
See http://ls11-www.cs.uni-dortmund.de/people/gutweng/dfgihk.pdf.

Systeme zum Graphenzeichnen

BFP+02
F. Brandenburg, M. Forster, A. Pick, M. Raitner, and F. Schreiber.
BioPath.
In P. Mutzel, M. Jünger, and S. Leipert, editors, Graph Drawing (Proc. GD '01), volume 2265 of Lecture Notes in Computer Science, pages 455-456. Springer-Verlag, 2002.

FPR+02
M. Forster, A. Pick, M. Raitner, F. Schreiber, and F.-J. Brandenburg.
The system architecture of the BioPath system.
In Silico Biology, 2(0037), 2002.

GD001
GD 2001 Software Exhibition, 2001.
See http://www.ads.tuwien.ac.at/gd2001/gd-swe_slides/.

GJK+02
C. Gutwenger, M. Jünger, G. W. Klau, S. Leipert, and P. Mutzel.
Graph drawing algorithm engineering with AGD.
In S. Diehl, editor, Software Visualization, International Dagstuhl Seminar on Software Visualization 2001, volume 2269 of Lecture Notes in Computer Science, pages 307-323. Springer-Verlag, 2002.

JKMW04
M. Jünger, G. W. Klau, P. Mutzel, and R. Weiskircher.
AGD: A library of algorithms for graph drawing.
In M. Jünger and P. Mutzel, editors, Graph Drawing Software, Mathematics and Visualization, pages 149-172. Springer, 2004.
See http://www.ads.tuwien.ac.at/~gunnar/gunnar/pubs/juenger+Al:AGDlibrary:2003.pdf.

Rya02
K. Ryall.
GLIDE.
In P. Mutzel, M. Jünger, and S. Leipert, editors, Graph Drawing (Proc. GD '01), volume 2265 of Lecture Notes in Computer Science, pages 479-480. Springer-Verlag, 2002.

Sch02
F. Schreiber.
High quality visualization of biochemical pathways in BioPath.
In Silico Biology, 2(0006), 2002.

GUI-Programmierung

BS04
J. Blanchett and M. Summerfield.
C++ GUI Programming with Qt.
Prentice Hall PTR, 2004.

Constraints

BP90
Karl-Friedrich Böhringer and Frances Newbery Paulisch.
Using constraints to achieve stability in automatic graph layout algorithms.
In CHI '90: Proceedings of the SIGCHI conference on Human factors in computing systems, pages 43-51, New York, NY, USA, 1990. ACM Press.

RMS96
Kathy Ryall, Joe Marks, and Stuart Shieber.
An interactive system for drawing graphs.
In Proc. Graph Drawing, GD, number 1190 in Lecture Notes in Computer Science, LNCS, pages 387-394, Berlin, Germany, 18-20 September 1996. Springer-Verlag.

Tam98
Roberto Tamassia.
Constraints in graph drawing algorithms.
Constraints, 3(1):87-120, 1998.

Compound-Graphen

EF99
P. Eades and Q.-W. Feng.
Drawing clustered graphs on an orthogonal grid.
Journal of Graph Algorithms and Applications (JGAA), 3(4):3-29, 1999.
http://www.cs.brown.edu/publications/jgaa/.

San96
G. Sander.
Layout of compound directed graphs.
Technical Report A/03/96, Universität des Saarlandes, 1996.

SM91
K. Sugiyama and K. Misue.
Visualization of structural information: Automatic drawing of compound digraphs.
IEEE Trans. Softw. Eng., 21(4):876-892, 1991.

Graph-Animation

FE02
C. Friedrich and P. Eades.
Graph drawing in motion.
Journal of Graph Algorithms and Applications (JGAA), 6(3):353-370, 2002.
http://www.cs.brown.edu/publications/jgaa/.

FH02
C. Friedrich and M-E. Houle.
Graph drawing in motion II.
In P. Mutzel, M. Jünger, and S. Leipert, editors, Graph Drawing (Proc. GD '01), volume 2265 of Lecture Notes in Computer Science, pages 220-231. Springer-Verlag, 2002.


6/17/2005 MCh