Zeichnen von Graphen - fernuni-hagen.de · PDF fileZeichnen von Graphen Fabio Valdés Programmierpraktikum WS 2016/17 Lehrgebiet Datenbanksysteme für neue Anwendungen FernUniversität

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


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


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


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



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



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



Beispiel: ER-Diagramm


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}


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)})



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



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



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


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)



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



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



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



k-Zusammenhang



5

4 3

1 2

5

4 3

1




k-Zusammenhang



5

4 3

1 2

5

4

1 2




k-Zusammenhang



5

4 3

1 2

5

3

1 2




k-Zusammenhang



5

4 3

1 2

4 3

1 2




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



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 ∗


Zeichnen Initialisierung

Initialisierung

Theorie: initiale Positionen irrelevant

quadratische Grundstruktur

von links oben nach rechts unten

zuerst angegebene Knoten weiter links bzw. weiter oben


Zeichnen Planarisierung

Planarisierung

(a)

ursprünglicher Graph G = (V ,E )



Planarisierung

(b)

Aufteilung der Kanten in planareund nichtplanare (gestrichelt)



Planarisierung

(c)

nur noch planare Kanten; dualerGraph (grau)



Planarisierung

(d)

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



Planarisierung

(e)

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



Planarisierung

(f)

vollständig planarisierter Graph


Zeichnen Orthogonalisierung

Übersicht

für jede Komponente des Graphen:

Sichtbarkeitsdarstellung

orthogonale Darstellung durch lokale Expansion

Begradigung der Kanten




Knoten → horizontale Segmente

Kanten → vertikale Segmente

keine Schnitte von Segmenten




Knoten → horizontale Segmente

Kanten → vertikale Segmente

keine Schnitte von Segmenten



Lokale Expansion



Lokale Expansion



Begradigung der Kanten


Zeichnen Kompaktifizierung

Kompaktifizierung


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


Export

Export

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

Textdatei

LinienKreiseText


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



Danke für Ihre Aufmerksamkeit.



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


Documents

Zeichnen von Graphen - fernuni-hagen.de · PDF fileZeichnen von Graphen Fabio Valdés Programmierpraktikum WS 2016/17 Lehrgebiet Datenbanksysteme für neue Anwendungen FernUniversität