PG 478 – Open Graph Drawing Framework
Thema: Compounds & Force-Directed
Francois Bertault & Mirka Miller – An Algorithm for Drawing Compound Graphs [1999]
Bernd Zey
27.10.05 Compounds & Force-Directed – Bernd Zey
3. Zeichen-Algorithmus für Compounds
1. Einleitung
2. Was sind Cluster-, Compound-, Nested- Graphen?
Übersicht – Worum geht‘s?
27.10.05 Compounds & Force-Directed – Bernd Zey 3
• Darstellung von Relationen Graphen
• Grenzen des klassischen Graph-Modells werden schnell erreicht
Cluster-, Compound-, Nested-, Hyper- Graphen
1. Einleitung
27.10.05 Compounds & Force-Directed – Bernd Zey 4
• Hyper-Graphen sind vielfältig und können Inklusionen, Schnitte und Relationen in einem Diagramm darstellen
1. Einleitung – Hyper-Graphen
A
B
C D
E
F
G H
IJK
L
M
27.10.05 Compounds & Force-Directed – Bernd Zey 5
1. Einleitung – Cluster-Graphen
• Einteilung von Knoten in Cluster
27.10.05 Compounds & Force-Directed – Bernd Zey 6
16 13 14
153
2
8
11
5
17
10 6
4
17
• Compound = Mittelweg zwischen Cluster und Hyper
1. Einleitung – Compound-Graphen
• Inklusionen bzw. Hierarchien als auch Relationen
27.10.05 Compounds & Force-Directed – Bernd Zey 7
• Wird definiert durch einen Baum und einen (un)gerichteten Graph
• Baum Hierarchie
• Knotenmengen sind identisch, die Kantenmengen unterscheiden sich
2. Was ist ein Compound-Graph?
• Graph Relationen
27.10.05 Compounds & Force-Directed – Bernd Zey 8
4
2
5
1
3
76
15
14
13
16
8
10
11
17
16 13 14
153
2
8
11
5
17
10 6
4
17
2. Was ist ein Compound-Graph? 1
2 3 4 5 176 7
15141311108
16
27.10.05 Compounds & Force-Directed – Bernd Zey 9
2. Compound-Graph – alternative Darstellung
4
2
5
1
3
76
15
14
13
16
8
10
11
17
1
2 3 4 5 176 7
15141311108
16
1
2 3 4 5 176 7
15141311108
16
27.10.05 Compounds & Force-Directed – Bernd Zey 10
2. Formale Definition eines Compound-Graphen
• Ein Compound-Graph wird definiert durch ein Paar C = (G,T) mit G ist ein Graph: G = (V,EG)
T ist ein Baum: T = (V,ET,r),
wobei folgende Bedingung erfüllt ist: (a,b) EG a Vorfahren(b) und
b Vorfahren(a)
14
13 6 1413
6 14
136
27.10.05 Compounds & Force-Directed – Bernd Zey 11
• Compound-Graph, in dem nur Kanten zwischen Blättern existieren
• Formal: Ein Cluster-Graph Cl = (G,T) ist ein Compound-Graph mit
(a,b) EG : a Blätter(T) & b Blätter(T)
2. Formale Definition eines Cluster-Graphen
27.10.05 Compounds & Force-Directed – Bernd Zey 12
7
6
4 8
1
9
11
10
5
3 2
2. Cluster-Graph – Beispiel
76 4 8 1
9
11
10
5
3 2
27.10.05 Compounds & Force-Directed – Bernd Zey 13
3. Zeichen-Algorithmus
• Vielzahl von Algorithmen für Cluster-Graphen
• Beispiel: Cluster Planarization SpanningTree, SimpleReinsertion, Reinsertion (Materialisierung der Cluster, Dualer Graph)
• Ziel: Algorithmus für Compound-Graphen
27.10.05 Compounds & Force-Directed – Bernd Zey 14
44
3. Zeichen-Algorithmus – Idee
16 13 14
153
2
8
11
5
17
10 6
17
4
2
5
1
3
76
15
14
13
16
8
10
11
17
1
2 3 4 5 176 7
15141311108
16
1
44
6
7
1016 13 14
153
2
8
11
5
17
27.10.05 Compounds & Force-Directed – Bernd Zey 15
3. Definition: Nested- Graph
• Formal: Ein Nested-Graph N = (G,T) ist ein Compound-Graph mit
(a,b) EG : Elter(a) = Elter(b)
• Nested-Graph = Compound-Graph, in dem Kanten nur zwischen Geschwistern existieren
27.10.05 Compounds & Force-Directed – Bernd Zey 16
1
2 3 4 5 176 7
15141311108
16
16 13 14
153
2
8
11
5
17
10 6
4
17
3. Nested- Graph
27.10.05 Compounds & Force-Directed – Bernd Zey 17
3. Algorithmus zum Compound-Zeichnen – NUAGE
• NUAGE ist ein Rahmenalgorithmus
• Idee: Konstruktion eines Nested-Graphen aus dem Compound-Graphen
• Zeichenalgorithmen als Unterprogramme
27.10.05 Compounds & Force-Directed – Bernd Zey 18
3. Algorithmus – Beschreibung
• Schritt 1: Konstruktion des Nested-Graphen
• Schritt 2: Berechne Positionen und Größe der Knoten
• Schritt 3: Transformation in den Compound-Graphen
• Schritt 4: Zeichnung erstellen
27.10.05 Compounds & Force-Directed – Bernd Zey 19
Für e = (a,b) EG :
Wenn Elter(a) = Elter(b) (a,b) EH
Ansonsten:
suche Vorfahren a‘,b‘ von a,b mit Elter(a‘) = Elter(b‘) (a‘,b‘) EH
3. Algorithmus – Schritt 1
• Gegeben: Compound-Graph mit Kantenmenge EG
• Gesucht: Nested-Graph mit Kantenmenge EH
Schritt 1: Konstruktion des Nested-Graphen
27.10.05 Compounds & Force-Directed – Bernd Zey 20
3. Konstruktion des Nested-Graphen – Beispiel
1
2 3 4 5 176 7
15141311108
16
16 13 14
153
2
8
11
5
17
10 6
4
17
1
6
7
4
1016 13 14
153
2
8
11
5
17
27.10.05 Compounds & Force-Directed – Bernd Zey 21
3. Algorithmus – Schritt 2
Schritt 2: Berechne Positionen und Größe der Knoten
• Basiert auf den klassischen Graph-Zeichen-Algorithmen
• Funktionsweise des Algorithmus:DFS-Durchlauf durch den Baum
• Jeder Teilgraph wird betrachtet
27.10.05 Compounds & Force-Directed – Bernd Zey 22
• Für jeden inneren Knoten v wird der Teilgraph G‘ mit v als Wurzel betrachtet
• Unteralgorithmus Größe und Position für jeden Knoten
• Berechne die Größe des Rechtecks, welches G‘ enthält
• Es wird für alle Knoten in G‘ die relative Position gesetzt
• Nach einem vollständigen DFS wird jedem Knoten seine absolute Position zugewiesen
3. Algorithmus – Schritt 2
27.10.05 Compounds & Force-Directed – Bernd Zey 23
3. Algorithmus – Schritt 2
Procedure FLEUR (N)Begin relative_position(r); absolute_position(r,0,0);End;
Eingabe: Nested-Graph, Größe jedes Blatt-Knotens
Ausgabe: Position und Größe aller Knoten in N
27.10.05 Compounds & Force-Directed – Bernd Zey 24
Procedure relative_position(v:node)Begin If Kinder(v) then begin For all s Kinder(v) do relative_position(s); H := Teilgraph von G mit v als Wurzel; Berechne Positionen von Knoten in H mit Hilfe eines Unteralgorithmus; Berechne die bounded-box von H; Setze relative Position von Knoten in H; end;End;
3. Algorithmus – Schritt 2 – Pseudocode
27.10.05 Compounds & Force-Directed – Bernd Zey 25
3. Algorithmus – Schritt 2 – Beispiel
532
9
8
11
6
7
10
14
1
4 5 10 6 7
2 3 8 9 11
1
4 5
10 6 7
2 3
9
8
11
2
4
3
5
8 9 11
10 6 7
1
27.10.05 Compounds & Force-Directed – Bernd Zey 26
3. Zwischenresultat
• Schritt 1: Compound Nested
• Schritt 2: Berechne Positionen und Größe der Knoten
• Nun: Schritt 3: Nested-Graph Compound-Graph
Vorgehensweise: Kanten „zurück biegen“
27.10.05 Compounds & Force-Directed – Bernd Zey 27
16
13 14
153
8
11
510
4
1
7
3. Algorithmus – Schritt 3
PROBLEM!
16
13 14
153
8
11
10
4
1
7
5
27.10.05 Compounds & Force-Directed – Bernd Zey 28
3. Algorithmus – Problem
• NUAGE ignoriert Kanten, welche im Schritt CompoundNested verändert wurden
• Kantenkreuzungen möglich
• Lösungen? Kantenlängen minimieren Knoten - die Kanten nach „außen“ haben - an den Rand schieben
27.10.05 Compounds & Force-Directed – Bernd Zey 29
3. Algorithmus – Problemlösung
• Vorgehensweise zur Verbesserung:
• Betrachte Kanten, welche zwischen Knoten mit unterschiedlichem Elter verlaufen
• force-directed-Algorithmus, welcher die Abstoßungskraft ignoriert
• Dadurch erhält man den gewünschten Effekt
27.10.05 Compounds & Force-Directed – Bernd Zey 30
3. Algorithmus – Problemlösungs-Beispiel
16
13 14
153
8
11
10
4
1
7
5
1
7
4
1016
13 14
153
8
11
5
1
7
4
1016 13 14
15 3
8
11 5
1
7
4
1016 13 14
15 3
8
11 5
27.10.05 Compounds & Force-Directed – Bernd Zey 31
Literatur:
• Francois Bertault & Mirka Miller – An Algorithm for Drawing Compound Graphs
Das war‘s