42
Zeichnen von Graphen Fabio Valdés Programmierpraktikum WS 2016/17 Lehrgebiet Datenbanksysteme für neue Anwendungen FernUniversität in Hagen Programmierpraktikum Zeichnen von Graphen 08.10.2016 1 / 28

Zeichnen von Graphen - fernuni-hagen.de...Zeichnen Planarisierung Planarisierung (f) vollständig planarisierter Graph Programmierpraktikum Zeichnen von Graphen 08.10.2016 18 / 28

  • Upload
    others

  • View
    6

  • Download
    0

Embed Size (px)

Citation preview

  • 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 ′ ⊂ Vmit 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 ′ ⊂ Vmit 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 ′ ⊂ Vmit 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 ′ ⊂ Vmit 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 ′ ⊂ Vmit 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

    EinleitungProblemstellungZiele

    Einlesen des GraphenDateiformatKorrektheitsprüfung

    ZeichnenGraphentheoretische DefinitionenInitialisierungPlanarisierungOrthogonalisierungKompaktifizierung

    Anzeige und ManipulationExportOptionale Erweiterungen