PG 478 – Open Graph Drawing Framework Thema: Compounds & Force-Directed Francois Bertault & Mirka Miller – An Algorithm for Drawing Compound Graphs [1999]

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


• 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


1. Einleitung – Cluster-Graphen

• Einteilung von Knoten in Cluster


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


• 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


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


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


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


• 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


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


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


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


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


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


3. Algorithmus zum Compound-Zeichnen – NUAGE

• NUAGE ist ein Rahmenalgorithmus

• Idee: Konstruktion eines Nested-Graphen aus dem Compound-Graphen

• Zeichenalgorithmen als Unterprogramme


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


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


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



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


• 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




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


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


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


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“


16

13 14

153

8

11

510

4

1

7


PROBLEM!

16

13 14

153

8

11

10

4

1

7

5


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


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


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


Literatur:

• Francois Bertault & Mirka Miller – An Algorithm for Drawing Compound Graphs

Das war‘s

Documents

PG 478 – Open Graph Drawing Framework Thema: Compounds & Force-Directed Francois Bertault & Mirka Miller – An Algorithm for Drawing Compound Graphs [1999]