Martin Böhmer/Dennis Treder/Marina Schwacke Übungen zu Automatisches Zeichnen von Graphen Ausgabe: 28.11.2007 Besprechung: 11.12.2007 Gruppe 2 - Übungsblatt

Martin Böhmer/Dennis Treder/Marina Schwacke

Übungen zu Automatisches Zeichnen

von Graphen

Ausgabe: 28.11.2007 — Besprechung: 11.12.2007

Gruppe 2

- Übungsblatt 4 -


Aufgabe 3: Knotenpositionierung

Entwerfen Sie ein Verfahren Ihrer Wahl für die dritte Phase (Knotenpositionierung) des Sugiyama Algorithmus.

Implementieren Sie Ihr Verfahren in OGDF, so dass es in der Lage ist, die bisherigen Module für die dritte Phase zu ersetzen.

Evaluieren Sie Ihr Verfahren (anhand selbst gewählter qualitativer Kriterien) im Vergleich zu einem in OGDF enthaltenen Verfahren.Wählen Sie als Benchmark Graphen die AT&T Graphen sowie selbst erzeugte zufällige Graphen.


Gliederung

Vorstellung des Layoutverfahrens

Bewertung:

Bewertungskriterien

Vergleich der Verfahren an AT&T Graphen.

Vergleich der Verfahren an Zufallsgraphen


Layoutverfahren

“Normale” Ansätze:

Knoten haben Wunschposition (gemäß irgendeiner Heuristik) und bekommen

diese zugeteilt.

Die wichtigen Knoten zuerst!


Layoutverfahren

Idee: Relaxiation

Problem: Abstände zu klein

Schritt: 0


Layoutverfahren

Idee: Relaxiation

Problem: Abstände zu klein (aber besser)

Schritt: 1


Layoutverfahren

Idee: Relaxiation

Problem: Abstand zu groß

Schritt: 2


Layoutverfahren

Idee: Relaxiation

kein Problem: “eingependelt“

Schritt: 3


Layoutverfahren

=> RelaxHierarchyLayout

Zur Vereinfachzung: Y-Koordinaten Fest

Initial werden alle Konten gleichmäßig zentriert positioniert (x-Position)

Anhand irgendwelcher Gewichtungen schieben sich die Knoten hin und her, um

festgelegte Constraints zu erfüllen


GewichteVerfahren: Knoten kümmern sich um sich und ihren

Nachbarn, dann um Ihre Kinder

Knotenwichtigkeit:

Dummyknoten?

Nachbarknoten?

Normaler Knoten?

Child-Knoten

einzelnes Kind?

Dummy child?

Layoutverfahren

Constraint-Wichtigkeit:

Dummy untereinander?

Child-Nähe? (höhere Gewichtung bei nur

einem Child)

Nachbar Nähe (zu nah? Zu weit weg?)


Layoutverfahren

Das Herzstück des Verfahrens:

void howToMove(weight1, weight2, pos1, pos2, wantedDiff, importance,

&resultDiff1, &resultDiff2)


Layoutverfahren zum Angucken

RandomSimpleGraph(G,10,11);Schritt: 0

Info: Veränderung pro Step gering (zum Gucken)

Gewichtungen (bei Weitem) noch nicht optimal

„Ausbruch nach rechts unten“












RandomSimpleGraph(G,10,11);Letzer Schritt: „Ganzzahlige“ Positionen

Was konnte man sehen? Nach kurzer Zeit hat sich nicht mehr viel verändert

Es hätten also auch weniger Iterationen zu einem

ähnlichen Ergebnis geführt



RandomSimpleGraph(G,10,11);Zum Vergleich: FastHierarchyLayout



Noch ein Vergleich (diesmal schneller), diesmal an Julian

<--FHR

Relax-->











Vergleich: Iterationen vs. Zeit vs. Ergebnis(Nein, das ist nicht das Gleiche wie bei den vorherigen Beispielen)

Gemessen wird nur die Laufzeit des Layoutverfahrens (Sugi-Overhead egal)



FastHierarchyLayout RelaxHierarchyLayoutIterationen: 1

30 15




30 30




30

125


Layoutverfahren

Was haben wir gesehen und was machen wir damit? Die Gewichtungen sind noch nicht gut gewählt (kann man aber ändern)

Spätestens wenn wir mehr als 3 bis 4 Iterationen haben, sind wir langsamer

als FastHierarchieLayout (denn das ist sehr schnell)

Laufzeit bei dichten Graphen besonders schlecht

IterationenAnzahl * KnotenAnzahl * AnzahlJeweiligerKinder

Spagetti! (Siehe Punkt 1)

Aber auch Gutes:

Layout wird nach wenigen Iterationen “stabil“

Es ist anschaulich, was passiert


Bewertungskriterien

Zeit

Größe des Gitters

Anzahl der Knicke in Kanten

Winkel von Kanten

Länge von Kanten


Bewertungskriterien - Winkel

0°

90° 90°

0°

α

α


AT&T Graphen - Allgemein

Anzahl Graphen: 1277

MaxKnoten: 100

MaxKanten: 241

Anzahl Planarer Graphen: 854


AT&T – Planare Graphen zu Graphen pro Knotenmenge


Vergleich: Gittergröße - AT&T


Vergleich: Anzahl Knicke - AT&T


Vergleich: Winkel von Kanten - AT&T


Vergleich: Kantenlänge - AT&T


Zufallsgraphen – Planare Graphen zu Graphen pro Knotenmenge


Vergleich: Gittergröße - Zufallsgraphen


Vergleich: Anzahl Knicke - Zufallsgraphen


Vergleich: Winkel von KantenZufallsgraphen


Vergleich: Kantenlänge - Zufallsgraphen


Ende

Vielen Dank für's Zuhören

Documents

Martin Böhmer/Dennis Treder/Marina Schwacke Übungen zu Automatisches Zeichnen von Graphen Ausgabe: 28.11.2007 Besprechung: 11.12.2007 Gruppe 2 - Übungsblatt