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

Martin Böhmer/Dennis Treder/Marina Schwacke

Übungen zu Automatisches Zeichnen

von Graphen

Ausgabe: 13.11.2007 — Besprechung: 27.11.2007

Gruppe 2

- Übungsblatt 3 -


Aufgabe 2

Sugiyama-Verfahren für große Graphen

(a) Evaluieren Sie das in OGDF enthaltene Sugiyama-Verfahren als Eignung für große Graphen(mehr als 1000 Knoten): Wo bleibt die Laufzeit?

(b) Entwickeln Sie eigene Ideen, wie man das Sugiyama Verfahren abändern könnte, so dass esfür große Graphen verwendet werden kann. Welche Qualitätsverluste nehmen Sie dabei inKauf? Mögliche Ideen finden Sie in der Arbeit von Eiglsperger, Siebenhaller und Kaufmann:An Efficient Implementation of Sugiyama’s Algorithm for Layered Graph Drawing. Journalof Graph Algorithms and Applications (JGAA), vol. 9, nr. 3, 305–325, 2005.


Gliederung

Test großer Graphen mit Sugiyama

Kleine Graphen testen mit Sugiyama

Paper vorstellen

eigene Idee vorstellen

Test der eigenen Idee


große Graphen mit Sugiyama

Anzahl Graphen: 20

#Knoten: 1206,20#Kanten: 1677,60

Anzahl Planarer Graphen: keine

Gesamtzeit: 146968631 Phase Ø: 4423,402 Phase Ø: 729134,253 Phase Ø: 1228,30 (Millisek.)

#crossings Ø: 0 Fehler#crossCalls Ø: 41847,55









Anzahl Graphen: 20

#Knoten: 100#Kanten: 300

Anzahl Planarer Graphen: keine

Gesamtzeit: 1797351 Phase Ø: 21,902 Phase Ø: 7367,953 Phase Ø: 29,60 (Millisek.)

#crossings Ø: 3974,35#crossCalls Ø: 3002,70






Arbeit von Eiglsperger, Siebenhaller und Kaufmann

Problem von Sugiyama:Zu viele Dummy-Knoten!

„The complexity of algorithms in the Sugiyama framework heavily depends on the number of dummy vertices inserted.“

Neuer Ansatz:






Eigene Idee

Weniger Crossmin-Aufrufe!

Nicht ganz so naiver Ansatz:

Gezieltes Auslassen von Crossmin-Aufrufen.

Naiver Ansatz:

Einfach die Anzahl der Crossmin-Ebenendurchläufe verringern. Führt (natürlich) zu weniger Crossmin-Aufrufen, aber auch (ungezielt) zu mehr Kreuzungen.


Eigene Idee: CrossminThreshold

Crossmin wird nur dann aufgerufen, wenn zwischen den betreffenden Layern überdurchschnittlich viele Kreuzungen auftreten.

Umsetzung:Nach jedem Crossmin-Durchlauf wird der Durchschnittswert der Kreuzungen pro Layer ausgerechnet (#Kreuzungen / #Layer).

Beim jedem weiteren Durchlauf für jedes Schicht-Paar:

if (KreuzungenZwischenSchichten > Grenzwert*Durchschnitt)crossMin

elsenoop

Beim Nach Testläufen hat sich Grenzwert = 1 durchgesetzt (guter Kompromiss aus Zeitersparniss und Kreuzungeszahl).



Zufallsgraphen: 20 Stück, 100 Knoten, 300 Kanten



Wo ist das Problem?

Die Graphen sind zu „klein“ - nach wenigen Crossmin-Durchläufen ändert sich nichts mehr.

Lösung?

Um repräsentativere Ergebnisse zu bekommen, wurde eine Anzahl an Durchläufen gewählt, nach der keine sehr deutliche Verbesserung der Kreuzungszahl mehr auftritt:

SG.setRuns(5);




Barycenter vs. Pyramid



2 * 1000 Knoten, 1500 Kanten & 2 * 1500 Knoten 2000 Kanten



Vielen Dank für die Aufmerksamkeit ;)

Documents

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