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
• Umfang
• Veranstalter
• Kontakt
• Aufgabe
• Teilnahmevoraussetzungen
• Minimalziele
• Realisierung
• Erweiterungsmöglichkeiten
• Literatur

Zeitraum

Umfang

Veranstalter

Kontakt

Aufgabe

• Computernetzwerke, soziale Netzwerke
• Geschäftsprozessmodellierung, Organisationsdiagramme
• Softwaresysteme (z.B. UML Klassendiagramme)
• Datenbankschemata
• Flussdiagramme
• Biologische Reaktionswege

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:

• Compound-Graphen: In dieser Graphenklasse existiert die Möglichkeit, dass Knoten andere Knoten enthalten können, was zu einer zusätzlichen hierarchischen Struktur führt (vergl. Abb. 1). Derartige Konstrukte sind beispielsweise in Organisations- und UML-Diagrammen sehr gebräuchlich, und stellen einen regen Forschungsbereich dar. Daher ist es von besonderer Bedeutung, eine entsprechende Repräsentation im OGDF zu besitzen, um derartige Graphen editieren zu können, und vor allem auch dafür entwickelte Layoutalgorithmen zur Verfügung zu stellen. Ein wichtiger Punkt ist weiterhin, dass derzeit kein allgemeiner Standard zur Speicherung derartiger Graphen existiert. Daher soll auch ein erweiterbares Format entwickelt werden, das möglichst vielen der ständig wachsenden Ansprüchen genügt.

  Figure 1: Ein Beispiel eines Compound-Graphen; mehrere einzelne Knoten sind zu übergeordneten rechteckigen Compounds zusammengruppiert.

• Constraint-Manager: Ein wichtiges Teilgebiet des Graphenzeichnens ist die Behandlung von sogenannten Constraints. Das sind zusätzliche Bedingungen, die für eine gute Zeichnung erfüllt werden müssen oder sollen, und reichen von geometrischen Constraints (wie z.B. Alignments von Knoten) bis zu durch eine Semantik definierten Einschränkungen (wie z.B. dem Verbot von Kreuzungen bestimmter Kanten). Um ein flexibles Framework für diese Eigenschaften zu schaffen, gilt es einen allgemeinen Constraint-Manager zu entwickeln, mit dem sich Constraints formulieren und auch visualisieren lassen. Für viele derartige Constraints existieren bereits einzelne Zeichenmethoden, die diese berücksichtigen. Die wichtigsten dieser Methoden sollen im OGDF zur Verfügung stehen.

• Animations-Manager: Oft ist es notwendig für einen gezeichneten Graphen ein weiteres alternatives Layout zu berechnen - sei es wegen leichter Änderungen am Graphen selbst, oder um den Schwerpunkt der Darstellung zu verschieben. Aus der Psychologie ist der Begriff der Mental Map bekannt. Damit umschreibt man die Anhaltspunkte im Layout, die sich der Betrachter merkt, um sich im Diagramm zu orientieren. Solche Anhaltspunkte können z.B. die Lage besonders markanter Objekte zueinander oder hervorstechende Muster in der Darstellung sein. Wird nun ein anderes Layout gewählt, sollte sich die Mental Map des Benutzers nicht zu stark ändern, bzw. muss man dem Benutzer dabei helfen, die Tranformation nachvollziehen zu können. Es existeren diverse Forschungsergebnisse wie man eine Darstellung in eine andere transformieren kann, so dass der Anwender diese Änderung leicht verstehen kann. Darauf basierend ist ein Animationsmodul zu entwickeln, das geeignet ist, verschiedene Transformationsmodelle anzuwenden.

• Editorkomponente: Ein graphisches Frontend (vergl. Abb. 2) für Graphenzeichenalgorithmen ist weit mehr als eine einfache Zeichenfläche für Knoten und Kanten. Es erfordert sowohl programmiertechnisches als auch wissenschaftliches Geschick, damit das Ergebnis den Anforderungen der Graphenlayout-Community gewachsen ist. Ziel ist also nicht nur die Integration der oben aufgeführten Punkte in ein homogenes System, sondern dieses System auch - mit Verständnis für die derzeitigen Graphenzeichen-Methoden und Weitblick für die kommenden Entwicklungen - möglichst erweiterbar zu gestalten.

  Figure 2: Der OGDF GraphDrawing-Editor.

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

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

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