Martin Böhmer/Dennis Treder/Marina Schwacke Übungen zu Automatisches Zeichnen von Graphen Ausgabe:...

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

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

Größe des Gitters

Anzahl der Knicke in Kanten

Winkel von Kanten

Länge von Kanten

Bewertungskriterien - Winkel

90° 90°

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

Vielen Dank für's Zuhören

Martin Böhmer/Dennis Treder/Marina Schwacke Übungen zu Automatisches Zeichnen von Graphen Ausgabe:...

Documents

KLEINE ANFRAGE - Landtag of Mecklenburg-Vorpommern · November 2007 beantwortet. LANDTAG MECKLENBURG-VORPOMMERN Drucksache 5/964 5. Wahlperiode 28.11.2007 KLEINE ANFRAGE des Abgeordneten

Meg Cabot Wie man sich beliebt macht · 2013-11-06 · Meg Cabot Wie man sich beliebt macht Aus dem Amerikanischen von Katarina Ganslandt Cabot_Wie man sich_NEU.indd 3 11.12.2007

Entwässerungssatzung i.d.F. vom 28.11.2007 - · PDF file1 / 34 Satzung über die Entwässerung und den Anschluss an die öffentliche Abwasseranlage – Allgemeine Entwässerungssatzung

Übungen zu Automatisches Zeichnen von Graphen Ausgabe: 28.11.2007 — Besprechung: 11.12.2007

Eine nirgends differenzierbare Funktion · Eine nirgends differenzierbare Funktion Ausarbeitung zum Seminar zur Fourieranalysis, 11.12.2007 Aaron Klüppelberg Obwohl es keine Umstände

Hans-Jürgen Treder Die Beziehungen von Marx und Engels zur ... … · zur Mathematik und Naturwissenschaft . Die Feuerbach-Thesen von Kar! Marx enthalten den Grundgedanken der Marxschen

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

Ambulante Versorgung Amputierter in anderen Systemen · Ralf Rensinghoff 28.11.2007 Ambulante Versorgung Amputierter in anderen Systemen von Ralf Rensinghoff-Dipl.-Betriebsw . - Berufsgenossenschaft

Arbeitsschwerpunkte der IHK zu Leipzig Dezember 20076 bis ... · § Von der Biomasse zum Energieträger Biogas am 11.12.2007 § Energieeffizienz in der betrieblichen Praxis am 22.01.2008

Kinderspaß 2008 V8 final:Kinderspaß 2008 11.12.2007 22:45 ... · Kinderspaß_2008_V8 final:Kinderspaß 2008 11.12.2007 22:45 Seite 1. ... Tel. 06531 – 3003 FAMILIENURLAUB PLANEN?

Www.WUPPERVERBAND.de Morphologische Randbedingungen und Entwicklungspotenziale am Beispiel Mors-, Leyer- und Müggenbach Morsbach F & E Projekt 28.11.2007

Übungen zu Automatisches Zeichnen von Graphen Ausgabe: 11.12.2007 — Besprechung: 15.01.2007

KR Ergebnisse 2015 · Lutz Pammel Albrecht Garbe 8. JF 2x A 97/98 I/II/III RV Weser Hameln RV Weser Hameln Katharina Stegen Joelle Edler Kaya Treder Mia Brocks RV Weser Hameln Lara

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

Das G-DRG-System 2008 … · Das G-DRG-System 2008 aus der Sicht des medizinischen Controllings Mannheim 28.11.2007 Steffen Koller. GB Unternehmensentwicklung. Controlling & Medizincontrolling

„Kinder in armen Familien“ Gerda Holz Vortrag, anlässlich der Fachtagung der LSJV Mainz am 28.11.2007 in Mainz

Gitarre Barock III - pop-sheet-music.com · Gitarre Barock III Diverse Komponisten des Barock Ausgewählt und übertragen auf die Gitarre von Michael Treder

Kurs: GK Soziologie Dozent: Sasa Bosancic Di. 11.12.2007 ... · PDF fileGruppen und Systeme Kurs: GK Soziologie Dozent: Sasa Bosancic Di. 11.12.2007 Referenten: Amelie Schuster & Gesa

Repertoire für die 11-chörige Barocklaute (C/a) · Repertoire für die 11-chörige Barocklaute (C/a) Diverse Komponisten des Barock Ausgewählt und übertragen von Michael Treder

Humanismus I: Das Erbe Wilhelm von Humboldts Seminar: Geschichte der Pädagogik, 28.11.2007 lic.phil. Christine Ruckdäschel