Übungen zu Automatisches Zeichnen von Graphen Ausgabe: 30.10.2007 — Besprechung: 13.11.2007

Martin Böhmer/Dennis Treder/Marina Schwacke

Übungen zu Automatisches Zeichnen

von Graphen

Ausgabe: 30.10.2007 — Besprechung: 13.11.2007

Gruppe 2

- Übungsblatt 2 -


Aufgabe 2

Ergänzen Sie OGDF um eine oder mehrere neue Kreuzungsminimierungsheuristik(-en) für 2-Schichten Graphen mit einer fixierten Schicht. Evaluieren Sie Ihre Heuristik im Vergleich mitder Median-Heuristik und der Barycenter-Heuristik und zwar

an den von uns zur Verfügung gestellten AT&T Graphen (Link s. Web).

an beliebigen (von Ihnen gewählten) 2-Schichten Graphen.

an beliebigen (von Ihnen gewählten) 7-Schichten Graphen.


Gliederung

Vorstellung der Heuristiken

Vergleich der Heursitiken mit den AT&T Graphen

Vorstellung der von uns gewählten Graphen.

Vergleich der Heursitiken mit unseren Graphen


Median Heuristik

Für jeden Knoten auf der unteren Schicht, berechne Median der Positionen der Nachbarn auf der oberen Schicht und sortiere die Knoten nach dem Wert.


Barycenter Heuristik

Für jeden Knoten auf der unteren Schicht, berechne durchschnittliche Position der Nachbarn auf deroberen Schicht und sortiere die Knoten nach dem Wert.


InsideEgalHeuristic

Gewichtung: arithm. Mittel von erstem und letztem adj. Knoten


PyramidHeuristic

Gewichtung „pyramidisch“; Größtes Gewicht bei Knoten n/2; Summe der Faktoren = 1;


Vergleich - Allgemein

Anzahl Graphen: 1277

MaxKnoten: 100

MaxKanten: 241

Anzahl Planarer Graphen: 854

Zeit: Sukijamah: 287689Median: 251368Barycenter: 289570Pyramid: 255579InsertE: 286366 (Millisek.)


Vergleich – Planare Graphen zu Graphen pro Knotenmenge


Vergleich – Durchschnittlicher Knotengrad


Vergleich – Heuristiken nach Grad


Vergleich – Gesamtzahl Kreuzungen


2-Schichten Graphen

Graph1: 7 Kreuzungen8 Knoten, 9 Kanten, Planar


2-Schichten Graphen

Graph1: 7 Kreuzungen8 Knoten, 9 Kanten, Planar


2-Schichten Graphen

Graph2: 3 Kreuzungen6 Knoten, 5Kanten, Planar

Werden vonallen Layoutsund Heuristikenmit 0 Krezungengezeichnet


2-Schichten Graphen

Graph3: 62 17 Knoten, 22Kanten, Planar


2-Schichten Graphen

Graph3: 62 17 Knoten,22 Kanten,Planar


7-Schichten Graphen

Graph1: 130 Kreuzungen40 Knoten,86 Kanten,nicht Planar


7-Schichten Graphen



7-Schichten Graphen



7-Schichten Graphen



7-Schichten Graphen



7-Schichten Graphen

Graph3:54 Kreuzungen26 Knoten,52 Kanten,nicht Planar


Vergleich

Zeit: Sukijamah: 296Median: 312Barency: 298Pyramid: 297InsertE: 329 #millis

Gesamt Anzahl Kreuzungen: Sukijamah: 216Median: 215Barency: 215Pyramid: 215InsertE: 216Orthogonal: 114

Documents

Übungen zu Automatisches Zeichnen von Graphen Ausgabe: 30.10.2007 — Besprechung: 13.11.2007