Zeichnen von Graphen - fernuni-hagen.de · PDF fileZeichnen von Graphen Fabio Valdés...

Zeichnen von Graphen

Fabio Valdés

ProgrammierpraktikumWS 2016/17

Lehrgebiet Datenbanksysteme für neue Anwendungen

FernUniversität in Hagen

Programmierpraktikum Zeichnen von Graphen 08.10.2016 1 / 28

Gliederung

1 Einleitung

ProblemstellungZiele

2 Einlesen des Graphen

DateiformatKorrektheitsprüfung

3 Zeichnen

Graphentheoretische DefinitionenInitialisierungPlanarisierungOrthogonalisierungKompaktifizierung

4 Anzeige und Manipulation

5 Export

6 Optionale Erweiterungen

Programmierpraktikum Zeichnen von Graphen 08.10.2016 2 / 28

Einleitung Problemstellung

Problemstellung

Mathematik: Graph durch Knotenmenge, Kantenmenge und ggf.Kantengewichte eindeutig definiert

graphische Darstellung: nicht eindeutig

5

4 3

1 2

1

2

3

4

5

1 2

3

4 5

Programmierpraktikum Zeichnen von Graphen 08.10.2016 3 / 28

Einleitung Ziele

Ziele in dieser Aufgabe

Einlesen eines Graphen aus einer Textdatei

Prüfung von Syntax und Semantik

Erzeugung einer platzsparenden Gitterdarstellung in vier Schritten

InitialisierungPlanarisierungOrthogonalisierungKompaktifizierung

weitere Anpassung durch Benutzer

Export als SVG-Datei

Programmierpraktikum Zeichnen von Graphen 08.10.2016 4 / 28

Einlesen des Graphen Dateiformat

Gerichtete Graphen

V = {1, 2, 3, 4, 5}

E = {1-2, 2-3, 3-4, 4-1, 4--5, 3--5}

5

4 3

1 2

1

2

3

4

5

1 2

3

4 5

Programmierpraktikum Zeichnen von Graphen 08.10.2016 5 / 28

Einlesen des Graphen Dateiformat

Ungerichtete Graphen

V = {1, 2, 3, 4, 5}

E = {1-2, 2-3, 3-4, 4-1, 4--5, 3--5}u

5

4 3

1 2

1

2

3

4

5

1 2

3

4 5

Programmierpraktikum Zeichnen von Graphen 08.10.2016 6 / 28

Einlesen des Graphen Dateiformat

Kantenbeschriftungen & Knotenkategorien

V = {Z:Zentrale, F:Filiale, K1:Kunde, K2:Kunde}

E = {Z-F:25, Z-K1:30, Z-K2:35, F-K1:10, F-K2:17, K1-K2:8.5}u

Z F

K1 K2

25

30 3510

17

8.5

Programmierpraktikum Zeichnen von Graphen 08.10.2016 7 / 28

Einlesen des Graphen Dateiformat

Beispiel: ER-Diagramm

Programmierpraktikum Zeichnen von Graphen 08.10.2016 8 / 28

Einlesen des Graphen Korrektheitsprüfung

Eingabefehler

V = {Ü, $, ξ}

V = {A, B, C, A}

V = {X, Y, Z}

E = {X-Y, Y-A}

V = {1, 2, 2}

E = {1-2, 1-2}

Programmierpraktikum Zeichnen von Graphen 08.10.2016 9 / 28

Zeichnen Graphentheoretische Definitionen

Teilgraph

Ein Graph G ′ = (V ′,E ′) heißt Teilgraph von G = (V ,E ), falls V ′ ⊆ V undE ′ ⊆ E ′ gelten.

1 2

3

4 5

1 2

3

4 5

G = ({1, 2, 3, 4, 5}, G ′ = ({3, 4, 5},

{(1, 2), (1, 4), (2, 3), {(3, 4), (3, 5), (4, 5)})

(3, 4), (3, 5), (4, 5)})

Programmierpraktikum Zeichnen von Graphen 08.10.2016 10 / 28

Zeichnen Graphentheoretische Definitionen

Grad

Der Grad grad(v) eines Knoten v ∈ V entspricht der Summe der Anzahlenseiner ein- und ausgehenden Kanten, d.h.,grad(v) = |{(u, v) ∈ E}|+ |{(v ,w) ∈ E}|.

1 2

3

4 5

grad(1) = 2grad(2) = 2grad(3) = 4grad(4) = 4grad(5) = 4

Programmierpraktikum Zeichnen von Graphen 08.10.2016 11 / 28

Zeichnen Graphentheoretische Definitionen

Planarität

Ein Graph G heißt planar, falls er eine Einbettung in die Ebene besitzt, d.h.,dass seine Kanten durch stetige, schnittpunktfreie Kurven dargestellt werdenkönnen, die sich nur in ihren gemeinsamen Endpunkten schneiden.

1 2

3 4

1

2

3 4

planarer Graph G Einbettung von G

Programmierpraktikum Zeichnen von Graphen 08.10.2016 12 / 28

Zeichnen Graphentheoretische Definitionen

Planarität

Ein Graph G heißt planar, falls er eine Einbettung in die Ebene besitzt, d.h.,dass seine Kanten durch stetige, schnittpunktfreie Kurven dargestellt werdenkönnen, die sich nur in ihren gemeinsamen Endpunkten schneiden.

1 2

3

4 5

nicht-planarer GraphProgrammierpraktikum Zeichnen von Graphen 08.10.2016 12 / 28

Zeichnen Graphentheoretische Definitionen

Weg & Kreis

Ein Weg von v1 nach vk in G = (V ,E ) ist eine Folge (v1, v2), . . . , (vk−1, vk)von Kanten, für v1, . . . , vk ∈ V , (v1, v2), . . . , (vk−1, vk) ∈ E .Ein Kreis in G ist ein Weg mit v1 = vk .Gibt es für alle u, v ∈ V höchstens einen Weg von u nach v , heißt G kreisfrei.

1 2

3

4 5

Weg von 1 nach 5: (1, 2), (2, 3), (3, 5)

Kreis von 1 nach 1: (1, 2), (2, 3), (3, 4), (4, 1)

Programmierpraktikum Zeichnen von Graphen 08.10.2016 13 / 28

Zeichnen Graphentheoretische Definitionen

Weg & Kreis

Ein Weg von v1 nach vk in G = (V ,E ) ist eine Folge (v1, v2), . . . , (vk−1, vk)von Kanten, für v1, . . . , vk ∈ V , (v1, v2), . . . , (vk−1, vk) ∈ E .Ein Kreis in G ist ein Weg mit v1 = vk .Gibt es für alle u, v ∈ V höchstens einen Weg von u nach v , heißt G kreisfrei.

1 2

3

4 5

kreisfreier Graph

Programmierpraktikum Zeichnen von Graphen 08.10.2016 13 / 28

Zeichnen Graphentheoretische Definitionen

Zusammenhang & Komponente

Ein ungerichteter Graph G = (V ,E ) heißt zusammenhängend, falls es zujedem Paar v ,w ∈ V einen Weg von v nach w gibt.Ein maximaler zusammenhängender Teilgraph K von G heißt Komponente.

1 2

3

4 5

1 2

3

4 5

zusammenhängender Graph zwei Komponenten eines nicht-zusammenhängenden Graphen

Programmierpraktikum Zeichnen von Graphen 08.10.2016 14 / 28

Zeichnen Graphentheoretische Definitionen

k-Zusammenhang

Ein ungerichteter Graph G = (V ,E ) heißt k-zusammenhängend, falls derGraph (V \ V ′,E \ {(v ,w) | v ∈ V ′ ∨ w ∈ V ′}) für alle Mengen V ′ ⊂ V

mit weniger als k Knoten zusammenhängend ist.

5

4 3

1 2

5

4 3

2

2-zusammenhängend zusammenhängend, aber i.A.nicht 2-zusammenhängend

Programmierpraktikum Zeichnen von Graphen 08.10.2016 15 / 28

Zeichnen Graphentheoretische Definitionen

k-Zusammenhang

Ein ungerichteter Graph G = (V ,E ) heißt k-zusammenhängend, falls derGraph (V \ V ′,E \ {(v ,w) | v ∈ V ′ ∨ w ∈ V ′}) für alle Mengen V ′ ⊂ V

mit weniger als k Knoten zusammenhängend ist.

5

4 3

1 2

5

4 3

1

2-zusammenhängend zusammenhängend, aber i.A.nicht 2-zusammenhängend

Programmierpraktikum Zeichnen von Graphen 08.10.2016 15 / 28

Zeichnen Graphentheoretische Definitionen

k-Zusammenhang

Ein ungerichteter Graph G = (V ,E ) heißt k-zusammenhängend, falls derGraph (V \ V ′,E \ {(v ,w) | v ∈ V ′ ∨ w ∈ V ′}) für alle Mengen V ′ ⊂ V

mit weniger als k Knoten zusammenhängend ist.

5

4 3

1 2

5

4

1 2

2-zusammenhängend zusammenhängend, aber i.A.nicht 2-zusammenhängend

Programmierpraktikum Zeichnen von Graphen 08.10.2016 15 / 28

Zeichnen Graphentheoretische Definitionen

k-Zusammenhang

Ein ungerichteter Graph G = (V ,E ) heißt k-zusammenhängend, falls derGraph (V \ V ′,E \ {(v ,w) | v ∈ V ′ ∨ w ∈ V ′}) für alle Mengen V ′ ⊂ V

mit weniger als k Knoten zusammenhängend ist.

5

4 3

1 2

5

3

1 2

2-zusammenhängend zusammenhängend, aber i.A.nicht 2-zusammenhängend

Programmierpraktikum Zeichnen von Graphen 08.10.2016 15 / 28

Zeichnen Graphentheoretische Definitionen

k-Zusammenhang

Ein ungerichteter Graph G = (V ,E ) heißt k-zusammenhängend, falls derGraph (V \ V ′,E \ {(v ,w) | v ∈ V ′ ∨ w ∈ V ′}) für alle Mengen V ′ ⊂ V

mit weniger als k Knoten zusammenhängend ist.

5

4 3

1 2

4 3

1 2

2-zusammenhängend zusammenhängend, aber i.A.nicht 2-zusammenhängend

Programmierpraktikum Zeichnen von Graphen 08.10.2016 15 / 28

Zeichnen Graphentheoretische Definitionen

Dualer Graph

Zu einem planaren Graphen G ist der duale Graph G ∗ wie folgt definiert:

Fläche in G ←→ Knoten in G ∗

Kante in G ←→ Kante in G ∗

1 2

1

3 3

2

4 5

Programmierpraktikum Zeichnen von Graphen 08.10.2016 16 / 28

Zeichnen Graphentheoretische Definitionen

Dualer Graph

Zu einem planaren Graphen G ist der duale Graph G ∗ wie folgt definiert:

Fläche in G ←→ Knoten in G ∗

Kante in G ←→ Kante in G ∗

Programmierpraktikum Zeichnen von Graphen 08.10.2016 16 / 28

Zeichnen Initialisierung

Initialisierung

Theorie: initiale Positionen irrelevant

quadratische Grundstruktur

von links oben nach rechts unten

zuerst angegebene Knoten weiter links bzw. weiter oben

Programmierpraktikum Zeichnen von Graphen 08.10.2016 17 / 28

Zeichnen Planarisierung

Planarisierung

(a)

ursprünglicher Graph G = (V ,E )

Programmierpraktikum Zeichnen von Graphen 08.10.2016 18 / 28

Zeichnen Planarisierung

Planarisierung

(b)

Aufteilung der Kanten in planareund nichtplanare (gestrichelt)

Programmierpraktikum Zeichnen von Graphen 08.10.2016 18 / 28

Zeichnen Planarisierung

Planarisierung

(c)

nur noch planare Kanten; dualerGraph (grau)

Programmierpraktikum Zeichnen von Graphen 08.10.2016 18 / 28

Zeichnen Planarisierung

Planarisierung

(d)

Hinzufügen der restlichen Kanten;kürzester Weg im dualen Graphenfür nichtplanare Kante entsprichtminimaler Anzahl vonKantenkreuzungen

Programmierpraktikum Zeichnen von Graphen 08.10.2016 18 / 28

Zeichnen Planarisierung

Planarisierung

(e)

neue Kante, neuer Knoten fürKantenkreuzung; Aktualisierungdes dualen Graphen

Programmierpraktikum Zeichnen von Graphen 08.10.2016 18 / 28

Zeichnen Planarisierung

Planarisierung

(f)

vollständig planarisierter Graph

Programmierpraktikum Zeichnen von Graphen 08.10.2016 18 / 28

Zeichnen Orthogonalisierung

Übersicht

für jede Komponente des Graphen:

Sichtbarkeitsdarstellung

orthogonale Darstellung durch lokale Expansion

Begradigung der Kanten

Programmierpraktikum Zeichnen von Graphen 08.10.2016 19 / 28

Zeichnen Orthogonalisierung

Sichtbarkeitsdarstellung

Knoten → horizontale Segmente

Kanten → vertikale Segmente

keine Schnitte von Segmenten

Programmierpraktikum Zeichnen von Graphen 08.10.2016 20 / 28

Zeichnen Orthogonalisierung

Sichtbarkeitsdarstellung

Knoten → horizontale Segmente

Kanten → vertikale Segmente

keine Schnitte von Segmenten

Programmierpraktikum Zeichnen von Graphen 08.10.2016 20 / 28

Zeichnen Orthogonalisierung

Lokale Expansion

Programmierpraktikum Zeichnen von Graphen 08.10.2016 21 / 28

Zeichnen Orthogonalisierung

Lokale Expansion

Programmierpraktikum Zeichnen von Graphen 08.10.2016 21 / 28

Zeichnen Orthogonalisierung

Begradigung der Kanten

Programmierpraktikum Zeichnen von Graphen 08.10.2016 22 / 28

Zeichnen Kompaktifizierung

Kompaktifizierung

Programmierpraktikum Zeichnen von Graphen 08.10.2016 23 / 28

Anzeige und Manipulation

Anzeige und Manipulation

Graph im Hauptfenster

Zoomen (Vergrößern und Verkleinern)

Scrollen (Balken einblenden, wenn nötig)

Markieren und Verschieben von Knoten und Kanten

mögliche Darstellungen für Knotenkategorien:

KreisRechteckRauteEllipsejeweils einfach oder doppelt, oder ohne Umrandung

Programmierpraktikum Zeichnen von Graphen 08.10.2016 24 / 28

Export

Export

Abspeichern des Graphen als SVG-Datei (Scalable Vector Graphics)

Textdatei

LinienKreiseText

Programmierpraktikum Zeichnen von Graphen 08.10.2016 25 / 28

Optionale Erweiterungen

Optionale Erweiterungen

Algorithmen

komplexere Algorithmen zur Planarisierung und Kompaktifizierungweitere Algorithmen zur Zeichnung von GraphenAuswahl der Verfahrens durch Benutzer

Anzeige

Ergebnisse der einzelnen TransformationsschritteAuswahl von Farben, Schrifttypen, -größen, -farben fürKnotenkategorien und Kanten(beschriftungen)

Druckfunktion

Ausgabe auf PapierPDF-Ausgabe

Export

EPS-Format

Programmierpraktikum Zeichnen von Graphen 08.10.2016 26 / 28

Optionale Erweiterungen

Danke für Ihre Aufmerksamkeit.

Programmierpraktikum Zeichnen von Graphen 08.10.2016 27 / 28

Optionale Erweiterungen

Quellenangabe

http://www.leda-tutorial.org/de/inoffiziell/ch05s03s07.html

http://www.rhinodidactics.de/Artikel/latex-2006-09-01.html

Di Battista, G., Eades, P., Tamassia, R. und Tollis, I.G.Graph Drawing: Algorithms for the Visualization of Graphs.Prentice-Hall, 1999

Tamassia, R. und Tollis, I.G. Planar grid embedding in linear time.IEEE Transactions on Circuits and Systems, 36(9):1230-1234, 1989

Programmierpraktikum Zeichnen von Graphen 08.10.2016 28 / 28