+ All Categories
Home > Documents > 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen...

17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen...

Date post: 05-Apr-2015
Category:
Upload: koloman-heintzelman
View: 109 times
Download: 1 times
Share this document with a friend
36
17.10.05 Hierarchical GD, Benjamin Stähr 1 Hierarchical Graph- Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren des Quelltextes: Gansner, Koutsofios, North, Vo
Transcript
Page 1: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 1

Hierarchical Graph-Drawing

Eine Technik für das Zeichnen gerichteter Graphen

Referent: Benjamin Stähr

Autoren des Quelltextes: Gansner, Koutsofios, North, Vo

Page 2: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 2

Inhalt

1. Einführung in das Thema „Zeichnen von gerichteten Graphen“

2. Ein Überblick über die Technik

3. Optimale Schichtzuweisung

4. Knotenreihenfolge in Schichten

5. Knotenkoordinaten

6. Kanten zeichnen

7. Zusammenfassung und Ausblick

Page 3: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 3

Ästhetische Zeichenkriterien

Hierarchische Struktur hervorheben

Wenn möglich zeigen alle Kanten in die gleiche allgemeine Richtung

Erleichtert es gerichtete Pfade zu finden und hebt Quellen und Senken hervor

Q

S

Q

S

Page 4: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 4

Ästhetische Zeichenkriterien

Vermeide optische Anomalien

z.B. Kantenüberschneidungen und scharfe Knicke in Kanten sind zu

vermeiden

Page 5: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 5

Ästhetische Zeichenkriterien

• Zeichne möglichst kurze Kanten

Vereinfacht das Finden verwandter Knoten

Konform zur Vermeidung optischer Anomalien

Page 6: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 6

Ästhetische Zeichenkriterien

• Bevorzuge Symmetrie und Balance

spielt nur sekundäre Rolle

wird an einigen wenigen Stellen des vorgestellten Algorithmus verwendet

Page 7: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 7

Ästhetische Zeichenkriterien

Es ist unmöglich alle diese Kriterien gleichzeitig zu optimieren

Entwurf von schnellen Heuristiken, die in vielen Fällen gute Layouts produzieren

Page 8: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 8

Problemstellung

• Eingabe ist ein gerichteter Graph G = (V,E)– Enthält evtl. Kreise und Mehrfachkanten– o.B.d.A. ist G zusammenhängend– Die Attribute des Graphen sind:

xsize(v),ysize(v): Größe einer den Knoten v umgebenden Bounding Box

v ysize(v)

xsize(v)

Page 9: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 9

Problemstellung

nodesep(G): Minimaler horizontaler Abstand zwischen zwei Knotenboxen

ranksep(G): Minimaler vertikaler Abstand zwischen zwei Knotenboxen

w(e): Kantengewicht der Kante e

u v

nodesep(G)

Page 10: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 10

Ein Überblick über den Algorithmus

• Jedem Knoten v wird ein Rechteck mit den Mittelpunktkoordinaten (x(v),y(v)) zugewiesen

• Jeder Kante e wird eine Reihe von B-Spline Kontrollpunkten (x0(e),y0(e)),...,(xn(e),yn(e)) zugewiesen

• Layout hauptsächlich nach den vier ästhetischen Zeichenkriterien

Page 11: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 11

Ein Überblick über den Algorithmus

Die vier Phasen des Algorithmus sind:1. Rank: weist jedem Knoten eine Schicht

im Graphen zu2. Ordering: setzt die Reihenfolge der

Knoten innerhalb jeder Schicht3. Position: weist jedem Knoten seine

absoluten Koordinaten zu4. Make Splines: Zeichnet die Kanten des

Graphen

Page 12: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 12

3. Optimale Schichtzuweisung

• „Rank“ weist jedem Knoten eine ganzzahlige Schicht zu

• Hier muss evtl. min. Längenbeschränkung

beachtet werden

v G( )v

Page 13: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 13

Den Graph azyklisch machen

• Für eindeutige Schichtzuweisung muss ein Graph azyklisch sein

• Azyklisch machen Kreise brechen durch temporäre Umkehrung von Kanten

• DFS partitioniert den Graphen in Baumkanten und Nicht-Baumkanten

• Nicht-Baumkanten in Cross-, Forward- und Backkanten

• Durch umkehren von Backkanten Graph kreisfrei

Page 14: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 14

Den Graph azyklisch machen

• Sinnvoll wäre es ein kleines oder minimales Kantenset umzudrehen

• „Feedback Arc Set“ jedoch leider NP-vollst.

• Lösung: DFS-Heuristik, welche Kanten umdreht, die in vielen Kreisen enthalten sind

Page 15: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 15

Baumkante

Backkante

Crosskante

Forwardkante

Page 16: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 16

Problem Definition

• Nach Ästhetischen Zeichenkriterien ist ein Ziel des Algos kurze Kanten zu zeichnen

• Gewünscht also optimale Schichtzuweisung z.B. mit min. Gesamtkantenlänge

• ILP:

u.d.N.:• Gewichtsfkt.

( , )

min ( , )( ( ) ( ))v w E

v w w v

( ) ( ) 1w v

Page 17: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 17

Netzwerk Simplex

• Worstcase-Laufzeit nicht polynomiell, aber in der Praxis sehr schnell

• Definitionen:– Feasible: Schichtzuweisung erfüllt die min.

Längenbedingungen – Slack: Differenz der aktuellen und

minimalen Länge einer Kante– Tight: Kante deren Slack = 0 ist

Page 18: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 18

Netzwerk Simplex

Erzeugung einer Schichtzuweisung durch einen

Spannbaum des Graphen:– Wähle Startknoten, weise ihm eine Schicht

zu– Nachbarknoten erhält den Wert eines

bewerteten Knoten +/- der min. Länge der sie verbindenden Kante, je nach Kantenrichtung

– Fortfahren bis alle Knoten eine Schichtzuweisung haben

Page 19: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 19

Netzwerk Simplex

• Ein Spannbaum ist feasible, wenn seine Schichtzuweisung feasible ist

• Alle Kanten im eben erzeugten Spannbaum sind tight

• Der Wert eines „Schnittes“ (bekannt aus EA) durch den Graphen ist s =

( , ), ,

( , )u v u Q v S

u v

2

4

11

5

s = 6

Page 20: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 20

Netzwerk Simplex

Für jede Spannbaumkante wird der Wert eines

Schnittes ermittelt. Dabei wird die Kante

eleminiert und der Spannbaum bricht dadurch

in Quellen- und Senkenkomponente

Page 21: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 21

Netzwerk Simplex

• Normalerweise impliziert ein negativer Wert eines Schnittes, dass die gewichtete Kantenlänge - durch Verlängerung der Baumkante bis eine der anderen Kanten tight wird - reduziert werden kann

• Diese wird neue Baumkante

• Dadurch neuer feasible Spannbaum

Page 22: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 22

Netzwerk Simplex

• Baumkanten mit negativen Schnittwerten werden durch Nicht-Baumkanten ersetzt, bis die Baumkanten pos. Schnittwerte haben

• Theoretisch wird eine Anti-Zyklen-Technik benötigt, um endl. Laufzeit zu garantieren

• Der resultierende Spannbaum entspricht einer opt. Schichtzuweisung

Page 23: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 23

4. Knotenreihenfolge in Rängen

• Kanten zwischen Knoten, die mehr als einen Rang auseinander liegen werden ersetzt durch Kantenketten mit jeweils Länge 1,virtuelle Knoten werden hinzugefügt

• Reflexive Kanten werden ignoriert• Multi-Kanten werden vereinigt• Es werden Heuristiken benutzt, da bereits für

zwei Schichten minimieren der Kantenüberschneidungen NP-vollst. Ist

Page 24: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 24

Lösungsschema

• Startsortierungen werden errechnet• Iterationssequenz um Reihenfolgen zu

verbessern– Jede Iteration geht von der ersten bis zur

letzten Schicht vor, oder umgekehrt– Jeder Knoten erhält eine Gewichtung

aufgrund der relativen Position der mit ihm verbundenen Knoten auf der vorhergehenden Schicht

– Danach werden die Schichten neu sortiert

Page 25: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 25

LösungsschemaPopuläre Gewichtsfunktionen:• Barycenter:

– Definiert das Gewicht eines Knoten v als den Durchschnitt der Ordnungszahlen der Knoten der letzten Schicht, die mit v verbunden sind.

• Median:– Wie Barycenter, allerdings wird der Median

der Ordnungszahlen verwendet.– Liefert bessere Ergebnisse,

Approximationsfaktor von 3

Page 26: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 26

Lösungsschema

• Hier benutzte Methode basiert auf Median• Wenn zwei Mediane existieren wird

interpolierter Wert verwendet, der die Seite mit dichter gepackten Knoten bevorzugt

• Zus. Heuristik für lokales Optimum (20% - 50% weniger Kreuzungen)

a b

c d

ab

c d

Page 27: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 27

5. Knotenkoordinaten• Jeder Knoten erhält in diesem Schritt x- und

y-Koordinaten

• LP:

u.d.N.:

dabei:

• : Interne Gewichtung um das Zeichnen langer, gerader Kanten zu bevorzugen

( , )

min ( ) ( ) w ve v w

e e x x

( , )b ax x a b

( ) ( )( , ) ( )

2

xsize a xsize ba b nodesep G

( )e

Page 28: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 28

Kantentypen

1. Beide Knoten der Kante sind reale Knoten

2. Ein Knoten ist realer, einer virtueller Knoten

3. Beide Knoten sind virtuelle Knoten

Seien e,f,g Kanten der drei Typen, dann gilt:

( ) ( ) ( )e f g

Page 29: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 29

Lösung mit Simplex Verfahren

• Resultierendes LP ist total unimodular und kann daher in einem Schritt per Simplex gelöst werden

• Transformation bläht den Graphen leider auf Größe |V| |E| + |E²| auf

Große Graphen können nicht mehr mit effizientem Platzbedarf gespeichert werden

Page 30: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 30

Heuristischer AnsatzEigentlich Iterationen folgender Heuristiken1. Medianpos:

2. Minedge: ähnlich, nur für reale Knoten2. Minnode: Lokale Optimierung obiger

Methoden3. Minpath: Begradigt Ketten

virtueller Knoten(Spaghetti-Effekt verhindern)

4. Packcut: Zeichnet Knoten möglichst kompakt

8

8

2

3

Page 31: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 31

Simplex verbessern• Heuristik ist leider schwer zu implementieren

und arbeitet oft suboptimal doch wieder Simplex

• Idee: Simplex aus 3. wiederverwenden und x-Koordinaten als Schichten ansehen

• Dazu muss G in einen Hilfsgraph G‘ transformiert werden

v w

u

v w

u

e

ev

eu

e(v,w)

e

Page 32: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 32

Simplex verbessern

• Optimale Lösung für G‘ induziert optimale Lösung für G

• Es sind Verbesserungen möglich, die den Simplex um ca. 500 bis 1000% beschleunigen

• Damit schneller als heuristische Lösung

Page 33: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 33

Weiterführende TechnikenNeuerer Algorithmus nach Buchheim, Jünger und Leipert (1999)

• Verhindert spätere Bildung eines Spaghetti-Effekts in den Kanten

• Möglich dadurch, dass jede Kante nur zwei Knicke hat und dazwischen vertikal verläuft

• Lösungsansätze heuristisch und mit Simplex möglich, den hier vorgestellten Ansätzen recht ähnlich

Page 34: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 34

6. Kanten zeichnen• Kanten zwischen Knoten werden am

einfachsten durch jeweils alle virtuellen Knoten gezeichnet

• Nachteil: Übersichtlichkeit leidet etwas, Graph ist optisch nicht perfekt

• Lösung: Verwendung von Splines

Page 35: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 35

Berechnung von Splines

B5 BB5

p0

p1

p2

Page 36: 17.10.05Hierarchical GD, Benjamin Stähr1 Hierarchical Graph-Drawing Eine Technik für das Zeichnen gerichteter Graphen Referent: Benjamin Stähr Autoren.

17.10.05 Hierarchical GD, Benjamin Stähr 36

7. Zusammenfassung und Ausblick • Der vorgestellte Algorithmus ist klar

strukturiert und programmiertechnisch gut umsetzbar

• Sowohl Laufzeit als auch Zeichenergebnis sind zufriedenstellend

• Splines müssten nicht benutzt werden, wenn ein anderer Ansatz zur Berechnung der x,y-Koordinaten gewählt würde

• Evtl. wäre „Kommunikation“ zwischen den einzelnen Schritten wünschenswert um Ergebnis zu verbessern


Recommended