Algorithmen zur Visualisierung von Graphen

Transcrição

Algorithmen zur Visualisierung von Graphen
Teile & Herrsche-Algorithmen:
Bäume und serien-parallele Graphen
Vorlesung im Wintersemester 2012/2013
Tamara Mchedlidze – Martin Nöllenburg – Ignaz Rutter
23. Oktober 2012
Algorithmen zur Visualisierung von Graphen – Teile & Herrsche-Algorithmen
Institute for Theoretical Informatics
Ignaz Rutter
Algorithmics Group I
Algorithmen zum Zeichnen von Bäumen
Ignaz Rutter
Anwendbarkeit
Gut bei induktiv oder rekursiv definierten Familien von Graphen
Binärbaum mit Wurzel:
1. Zeichne linken Teilbaum
2. Zeichne rechten Teilbaum
3. füge zusammen + Wurzel
ss
tiefe(v): Abstand zur
Wurzel
ss Durchlaufreihenfolgen
ss preorder
ss inorder
ss postorder
Ignaz Rutter
Algorithmus von Reingold und Tilford (’81)
Ignaz Rutter
Ignaz Rutter
2 Phasen:
1. postorder
(bottom-up):
Konturen und x-Offsets
zum Vorgänger einsammeln
2. preorder (top-down): absolute Koordinaten ausrechnen
Ignaz Rutter
2 Phasen:
1. postorder
(bottom-up):
Konturen und x-Offsets
zum Vorgänger einsammeln
2. preorder (top-down): absolute Koordinaten ausrechnen
Kontur: verkettete Liste von Knoten (-Koordinaten)
Ignaz Rutter
Phase 1:
1. Bearbeite T` (v) und Tr (v)
2. Laufe parallel linke Kontur von Tr (v) und rechte Kontur von
T` (v) ab
3. Bestimmt daraus dv , den horizontalen Minimalabstand von
v` und vr
4. x-Offset(v` ) = −d d2v e, x-Offset(vr ) = d d2v e
5. Baue linke Kontur von Tv aus: v, linke Kontur von T` (v) und
evtl. überhängendes Teilstück von linker Kontur von Tr (v)
6. Rechte Kontur analog
Ignaz Rutter
Phase 2
1. Setze y-Koordinate y(v) = −tiefe(v)
2. Setze x(v) = 0 für Wurzel und rekursiv die x-Koordinate
x(v` ) und x(vr ) der Nachfolger von v auf
x(v)+ x-Offset(x(v` )) bzw. x(v)+ x-Offset(x(vr ))
Zusammenfassung:
Algorithmus berechnet Binärbaumlayout:
ss geradliniges Gitterlayout
ss tiefengeschichtet, kreuzungsfrei
ss Knoten derselben Tiefe haben Abstand ≥ 2
ss Knoten sind über Nachfolgern zentriert
ss linke/rechte Nachfolger sind strikt links/rechts
ss identische Teilbäume gleich gezeichnet
Ignaz Rutter
Breitenminimierung von Binärbaumlayouts
Satz (Supowit, Reingold)
Die Breitenminimierung von Binärbaumlayouts ist NP-schwer
Beweis: Reduktion von 3S AT
F = C1 ∧ · · · ∧ Cm ,
Ci = yi,1 ∨ yi,2 ∨ yi,3 , yi,j ∈ {x1 , . . . , xn , x1 , . . . , xn }
Konstruiere Baum T (F ), der genau dann Layout mit
Breite W ≤ 24 hat, wenn F erfüllbar ist.
Baum T (xk ) für Var. xk :
p
p
q0
q0
qk
qk
Ignaz Rutter
F = C1 ∧ · · · ∧ Cm ,
p
q0
q0
qk
qk
u1
u`
Höhe ` = 3(i − 1) + j
p
Baum Ti,j
Ignaz Rutter
F = C1 ∧ · · · ∧ Cm ,
p
q0
qk
u1
q0
qk
u`
Höhe ` = 3(i − 1) + j
p
Baum Ti,j
Literalbaum:
yi,j = xk
T (yi,j ) für
yi,j = xk
p
b
T (xk )
6
Ti,j
b
T (xk )
Ti,j
6
Ignaz Rutter
Breitenminierung II
Klauselbaum T (Ci ):
T (yi,1 )
T (yi,2 )
T (yi,3 )
Erfüllte Klausel hat Breite höchstens
6 + 2 + 7 + 2 + 7 = 24
Beachte: alle Literalbäume haben volle Breite auf
vierter Ebene von oben
Nicht erfüllte Klausel: 7+2+7+2+7 = 25
Ignaz Rutter
Breitenminierung II
Klauselbaum T (Ci ):
Formelbaum T (F )
T (C1 )
b
T (yi,1 )
T (yi,2 )
T (yi,3 )
T (C2 )
b
Erfüllte Klausel hat Breite höchstens
6 + 2 + 7 + 2 + 7 = 24
Beachte: alle Literalbäume haben volle Breite auf
vierter Ebene von oben
Nicht erfüllte Klausel: 7+2+7+2+7 = 25
T (Cm )
Breite ≤ 24 ⇔ F erfüllbar
Ignaz Rutter
HV-Bäume
Idee:
ss
Zeichne Teilbäume in Rechtecke,
Wurzel liegt in linker oberer Ecke
ss Nachfolger liegen vertikal unterhalb bzw. horizontal rechts
Induktionsanfang:
Induktionsschritt: kombiniere Layouts
horizontale Kombination
(Fläche: 3 × 7)
Berechne optimale Zeichnung mit
vertikale Kombination
dynamischer Programmierung
(Fläche: 4 × 6)
Ignaz Rutter
Rechtslastige hv-Layouts
Rechtslastiges hv-Layout:
ss
ss
Wähle in jedem Schritt Horizontal-Kombination
Platziere größeren Teilbaum rechts
Lemma
Höhe eines rechtslastigen hv-Layouts für Baum mit n Knoten ist
höchstens log n.
Beweis:
ss
ss
ss
ss
Vertikale Kanten haben Länge 1
w Knoten mit minimaler y-Koordinate
betrachte eindeutigen Pfad P zur Wurzel
für jede vertikale Kante (u, v) auf P : |T (v)| > |2T (u)|
ss ⇒ P enthält höchstens log n solcher Kanten
Platzbedarf: O(n log n)
Ignaz Rutter
Radiale Baumlayouts
Ignaz Rutter
Beispiel Radiallayout
11
9
1
7
1
5
1
3
1
1
1
Ignaz Rutter
11
9
1
7
1
5
1
3
1
1
1
Ignaz Rutter
11
9
1
7
1
1
10
5
1
3
1
1
1
Ignaz Rutter
11
9
1
7
1
1
10
5
1
3
1
1
1
Ignaz Rutter
9
10
11
·
1
8
9
1
7
1
1
10
5
1
3
1
1
1
Ignaz Rutter
9
10
11
·
1
8
9
1
7
1
1
10
5
1
3
1
1
1
Ignaz Rutter
9
10
11
·
7
8
·
1
6
9
10
·
1
8
9
1
7
1
1
10
5
1
3
1
1
1
Ignaz Rutter
9
10
11
·
7
8
·
1
6
9
10
·
1
8
9
1
7
1
1
10
5
1
3
1
1
1
Ignaz Rutter
Verlassen des Kreisringsektors
Ignaz Rutter
ρi
τ
ρi+1
cos τ =
ρi
ρi+1
Ignaz Rutter
ρi
τ
ρi+1
cos τ =
ρi
ρi+1
Ignaz Rutter
Serien-parallele Graphen
Ignaz Rutter
Serien-parallele Graphen
Graph G heißt serien-parallel, wenn er
t
ss
aus genau zwei Knoten (Quelle s, Senke t sowie
der Kante (s, t) besteht oder
ss aus zwei serien-parallelen Graphen G1 , G2 mit
Quellen s1 , s2 und Senken t1 , t2 durch eine der
folgenden Kombinationen hervorgeht
s
parallele Komposition:
serielle Komposition:
Identifiziere s1 , s2 als neue Quelle
Identifiziere t1 und s2 ,
s1 neue Quelle, T2 neue Senke Identifiziere t1 , t2 als neue Senke
t2
t1 = t2
t1 = s2
s1
s1 = s2
Ignaz Rutter
Serien-parallele Graphen II
Lemma
Serien-parallele Graphen sind azyklisch und planar.
Beschreibung des rekursiven Aufbaus durch binären Baum:
ss
ss
Blätter sind Kanten (Q-Knoten)
Innere Knoten sind S- oder P-Knoten
(vgl. SPQR-Baum)
Ignaz Rutter
SP-Graphen: Dekompositionsbaum
Ignaz Rutter
P
Ignaz Rutter
P
P
Ignaz Rutter
P
P
S
Q
Q
Ignaz Rutter
P
P
S
S
Q
Q
Q
Q
Ignaz Rutter
P
P
S
S
S
Q
Q
Q
Q
Q
Ignaz Rutter
P
P
S
S
S
Q
Q
S
Q
Q
Q
Q
Ignaz Rutter
P
P
S
S
S
Q
Q
S
Q
P
Q
Q
Q
Ignaz Rutter
P
P
S
S
S
Q
Q
S
Q
P
S
Q
Q
Q
Q
Q
Ignaz Rutter
P
P
S
S
S
Q
Q
S
Q
P
S
Q
S
Q
Q
Q
Q
Q
Q
Ignaz Rutter
SP-Graphen in Anwendungen
Ablaufdiagramme
PERT-Diagramme
(Program Evaluation and Review Technique)
Außerdem: Linearzeitalgorithmen für sonst NP-vollständige Probleme (z.B. Maximum Independent Set)
Ignaz Rutter
Untere Schranke für die Fläche
Satz
Jedes kreuzungsfreie Aufwärtslayout für geordnete einfache
serien-parallele Graphen mit n Knoten benbötigt im worst case
ein Gitter der Größe Ω(2n ).
Ignaz Rutter
Satz
Beweis:
tn+1
t0
tn
Gn
sn
s0
G0
sn+1
Gn+1
Ignaz Rutter
Satz
Beweis:
tn+1
t0
tn
Gn
tn
Gn
sn−1
sn
s0
G0
sn+1
Gn+1
sn
Ignaz Rutter
Satz
Beweis:
tn+1
tn+1
t0
tn
Gn
tn
Gn
sn−1
sn
s0
G0
sn+1
Gn+1
sn
Ignaz Rutter
Satz
Beweis:
tn+1
tn+1
t0
tn
tn
Gn
Gn
sn
s0
G0
sn+1
sn−1
sn+1
Gn+1
sn
Ignaz Rutter
Satz
tn+1
Beweis:
tn+1
t0
tn
tn
Gn
Gn
sn
s0
G0
sn−1
sn+1
sn+1
Gn+1
sn
Ignaz Rutter
Satz
tn+1
Beweis:
tn+1
t0
tn
tn
Gn
Gn
sn
s0
G0
sn−1
sn+1
sn+1
Gn+1
sn
Ignaz Rutter
Satz
tn+1
Beweis:
tn+1
t0
tn
tn
Gn
Gn
sn
s0
G0
sn−1
sn+1
sn+1
Gn+1
sn
Ignaz Rutter
Satz
tn+1
Beweis:
tn+1
t0
∆2
tn
tn
Gn
Gn
sn
s0
G0
sn+1
Gn+1
sn−1
∆1
sn+1
Π
sn
Ignaz Rutter
Satz
tn+1
Beweis:
tn+1
t0
∆2
tn
tn
Gn
Gn
sn
s0
G0
sn+1
Gn+1
sn−1
∆1
sn+1
Π
sn
Ignaz Rutter
Satz
tn+1
Beweis:
tn+1
t0
∆2
tn
tn
Gn
Gn
sn
s0
G0
sn+1
Gn+1
sn−1
∆1
sn+1
Π
sn
Ignaz Rutter
Satz
tn+1
Beweis:
tn+1
t0
∆2
tn
tn
Gn
Gn
sn
s0
G0
sn+1
Gn+1
sn−1
∆1
sn+1
Π
sn
Ignaz Rutter
Linkslastige Ordnungen
Ordnung heißt linkslastig, wenn Q-Knoten nur als rechte Nachfolger von P-Knoten vorkommen.
Satz
Wenn G serien-parallel, einfach und linkslastig geordnet, so besitzt G Zeichnung der Größe O(n2 ).
Komponenten des Dekompositionsbaums:
ss Layout von G passt in rechtwinkliges, gleichschenkliges Dreieck mit vertikaler Basis, Schenkel nach links.
ss Quelle in unterer Ecke, Senke in oberer Ecke, linke
t
v
Ecke frei
ss rechtester Nachbar von s 6= t (t 6= s) liegt unterhalb
(oberhalb) der Mitte
ss v Nachbar der Quelle (Senke) ⇒ kein Knoten liegt im
v
Parallelogramm von v und s (t).
s
Ignaz Rutter
Konstruktion
s
Q-Knoten (Induktionsanfang):
t
Ignaz Rutter
Konstruktion
s
t
t
∆(G2 )
S-Knoten (serielle Komposition):
∆(G1 )
s
Ignaz Rutter
Konstruktion
s
t
∆(G2 )
t
t
∆(G1 )
P-Knoten (parallele Komposition):
∆(G1 )
s
∆(G2 )
s
Ignaz Rutter
Konstruktion
s
t
∆(G2 )
t
t
∆(G1 )
P-Knoten (parallele Komposition):
Eigenschaften:
ss kreuzungsfrei und aufwärts
ss höchstens quadratische Fläche
∆(G1 )
s
∆(G2 )
s
Ignaz Rutter
Darstellung von Symmetrien in Graphen
aus Hong, Eades, Lee ’00
Ignaz Rutter
Definition: Automorphismen eines DAG
Ein Automorphismus eines DAG G = (V, E) ist eine Knotenpermutation π : V → V , die Adjazenzen respektiert und alle
Kantenrichtungen erhält oder alle Kantenrichtungen umdreht:
(u, v) ∈ E ⇔ (π(u), π(v)) ∈ E
oder
(u, v) ∈ E ⇔ (π(v), π(u)) ∈ E.
Die Automorphismen von G bilden mit der Hintereinanderausführung eine Gruppe.
ss die Automorphismengruppe eines Graphen zu bestimmen ist GI-
vollständig
ss für Graphen mit beschränktem Maximalgrad und planare Graphen
geht das in Polynomialzeit
Ignaz Rutter
Definition: Automorphismen eines DAG
Ein Automorphismus eines DAG G = (V, E) ist eine Knotenpermutation π : V → V , die Adjazenzen respektiert und alle
Kantenrichtungen erhält oder alle Kantenrichtungen umdreht:
(u, v) ∈ E ⇔ (π(u), π(v)) ∈ E
oder
(u, v) ∈ E ⇔ (π(v), π(u)) ∈ E.
Die Automorphismen von G bilden mit der Hintereinanderausführung eine Gruppe.
ss die Automorphismengruppe eines Graphen zu bestimmen ist GI-
vollständig
ss für Graphen mit beschränktem Maximalgrad und planare Graphen
geht das in Polynomialzeit
Ignaz Rutter
Darstellbare Symmetrien
ss ein Automorphismus π eines Graphen ist darstellbar, wenn es eine
Zeichnung gibt, die eine Symmetrie enthält, welche π induziert
ss Lin charakterisiert darstellbare Automorphismen [Lin ’92]
ss Darstellbare Automorphismen eines Graphen zu finden ist NP-
schwer
ss für planare Graphen ist das wieder in Polynomialzeit möglich
2
1
1
3
2
1
4
3
4
2
3
4
5
Ignaz Rutter
Darstellbare Symmetrien
ss ein Automorphismus π eines Graphen ist darstellbar, wenn es eine
Zeichnung gibt, die eine Symmetrie enthält, welche π induziert
ss Lin charakterisiert darstellbare Automorphismen [Lin ’92]
ss Darstellbare Automorphismen eines Graphen zu finden ist NP-
schwer
ss für planare Graphen ist das wieder in Polynomialzeit möglich
2
1
1
3
2
1
4
3
4
stellt 1 → 2 → 3 → 4 → 1 dar,
aber nicht 1 → 2 → 3 → 1
2
3
stellt 1 → 2 → 3 → 1 dar, aber
nicht 1 → 2 → 3 → 4 → 1
4
5
1 → 2 → 3 → 1, 4 → 5 → 4
nicht darstellbar
Ignaz Rutter
Symmetrien in SP-Graphen
v
π(v)
u
π(u)
πvert
Ignaz Rutter
π(u)
π(v)
v
π(v)
u
π(u)
πvert
v
u
πhor
Ignaz Rutter
v
π(v)
u
π(u)
πvert
π(u)
π(u)
π(v)
π(v)
v
v
u
u
πhor
πrot
Ignaz Rutter
v
π(v)
u
π(u)
πvert
π(u)
π(u)
π(v)
π(v)
v
v
u
u
πhor
πrot
{πvert , πhor , πrot }
Ignaz Rutter
Symmetrien in SP-Zeichnungen
Satz (Hong, Eades, Lee ’00)
Die in einem kreuzungsfreien Aufwärtslayout eines SPGraphen darstellbaren Symmetrien sind entweder
ss {id}
ss {id, π} mit π ∈ {πvert , πhor , πrot }
ss {id, πvert , πhor , πrot }.
Ignaz Rutter
Knotenkodierung im Dekompositionsbaum
P
P
S
S
S
Q
Q
S
Q
P
S
Q
S
Q
Q
Q
Q
Q
Q
Ignaz Rutter
P
P
S
S
S
Q
Q
S
Q
P
S
Q
S
Q
Q
Q
Q
Q
Q
Ignaz Rutter
P
S
S
S
P
S
S
Ignaz Rutter
Kanonische Kodierung
ss Setze C(G) = h0i für alle Q-Knoten G.
ss Für jede Tiefe t = max tiefe(G), . . . , 0
G
ss
ss
ss
Für jeden S- oder P-Knoten G der Tiefe t mit Nachfolgern
G1 , . . . , Gk setze C(G) = hc(G1 ), . . . , c(Gk )i und sortiere C(G)
nichtabsteigend, falls G ein P-Knoten ist.
Sortiere die Menge der Tupel aller Knoten der Tiefe t lexikographisch.
Für jede Komponente G der Tiefe t setze ihre Kodierung auf c,
falls ihr Tupel in der sortierten Tupelfolge als c-tes verschiedenes Tupel auftritt.
Ignaz Rutter
G
ss
ss
ss
Ignaz Rutter
G
ss
ss
ss
Ignaz Rutter
G
ss
ss
ss
Ignaz Rutter
G
ss
ss
ss
Zwei Knoten u und v gleicher Tiefe sind genau dann isomorph, wenn sie
den gleichen Code haben.
Ignaz Rutter
P
S
S
S
P
h0i
h0i
h0i
h0i
h0i
S
S
h0i
h0i
h0i
h0i
h0i
Ignaz Rutter
P
S
S
S
P
h0i
h0i
h0i
h0i
h0i
S
S
h0i
h0i 1
h0i 1
h0i 1
h0i 1
Ignaz Rutter
P
S
S
S
P
h0i
h0i
h0i
h0i
h0i
h0i
S
S
h1, 1i
h1, 1i
h0i 1
h0i 1
h0i 1
h0i 1
Ignaz Rutter
P
S
S
S
P
h0i
h0i
h0i
h0i
h0i
h0i
S
S
h1, 1i
h1, 1i
1
h0i 1
h0i 1
h0i 1
h0i 1
Ignaz Rutter
1
P
S
S
S
P
h1, 1i
h0i
h0i
h0i
h0i
h0i
h0i
S
S
h1, 1i
h1, 1i
1
h0i 1
h0i 1
h0i 1
h0i 1
Ignaz Rutter
1
P
S
S
S
P
h1, 1i 2
h0i 1
h0i 1
h0i 1
h0i 1
h0i 1
h0i 1
S
S
h1, 1i
h1, 1i
1
h0i 1
h0i 1
h0i 1
h0i 1
Ignaz Rutter
1
P
S
S
h1, 1, 2i
h1, 1i
h1, 1i
S
P
h1, 1i 2
h0i 1
h0i 1
h0i 1
h0i 1
h0i 1
h0i 1
S
S
h1, 1i
h1, 1i
1
h0i 1
h0i 1
h0i 1
h0i 1
Ignaz Rutter
1
P
S
S
h1, 1i
h1, 1, 2i
1
2
h1, 1i 1
S
P
h1, 1i 2
h0i 1
h0i 1
h0i 1
h0i 1
h0i 1
h0i 1
S
S
h1, 1i
h1, 1i
1
h0i 1
h0i 1
h0i 1
h0i 1
Ignaz Rutter
1
P
h1, 1, 2i
1
S
S
h1, 1i
h1, 1, 2i
1
2
h1, 1i 1
S
P
h1, 1i 2
h0i 1
h0i 1
h0i 1
h0i 1
h0i 1
h0i 1
S
S
h1, 1i
h1, 1i
1
h0i 1
h0i 1
h0i 1
h0i 1
Ignaz Rutter
1
Vertikale Symmetrien
Gegeben sei der kanonische Dekompositionsbaum eines serienparallelen Graphen. Es sei G eine Komponente, die durch Komposition der Komponenten G1 , . . . , Gk entstehe.
ss Ist G ein S-Knoten, dann ist G vertikal symmetrisch, wenn alle
G1 , . . . , Gk vertikal symmetrisch sind.
ss Ist G ein P-Knoten, so betrachten wir die Klassen Gj = {Gi : 1 ≤
i ≤ k, c(Gi ) = j}, j = 1, . . . , k, von isomorphen Teilgraphen.
ss |Gj | gerade ∀j ⇒ vertikal symmetrisch
ss |Gj | ungerade für genau ein j ⇒ G vertikal symmetrisch g.d.w.
Graphen in Gj vertikal symmetrisch
ss |Gi |, |Gj | ungerade für i 6= j ⇒ G nicht vertikal symmetrisch
Ignaz Rutter
Ignaz Rutter
Ignaz Rutter
Ignaz Rutter
Beweisidee vertikale Symmetrie
S-Knoten
Ignaz Rutter
P-Knoten, alle Klassen gerade Anzahl
S-Knoten
Ignaz Rutter
P-Knoten, alle Klassen gerade Anzahl
S-Knoten
alle Knoten v-symm.
P-Knoten, eine Klasse ungerade Anzahl & v-symm.
Ignaz Rutter
Symmetrien zeichnen
Ignaz Rutter
Symmetrien zeichnen
Ignaz Rutter
Symmetrien zeichnen
Ignaz Rutter

Algorithmen zur Visualisierung von Graphen

Transcrição

Documentos relacionados

Beschreibung der Behandlung am Taschenrechner TI-82

SPS-Programmierer / in

Projekt-Steckbrief Konsortium

Rendering von Landschaften

Inhaltsverzeichnis - cpe - Technische Universität Kaiserslautern

konzerte im rahmen des musikalisch kulturellen austauschs ivoti

Life Sciences - ERC

ATMOS Diagnostic World

Social Media

Internationale Zusammenarbeit

Bentley Systems

Glanzvolle Premiere für Erfurts neues Opernhaus

Numerische Analyse von gemischten Ausfallverteilungen in der