1 Graph Drawing by Force-directed PlacementJana Ludolph

2 Graph Drawing by Force-Directed PlacementÜbersicht Problemstellung Eades Kamada und Kawai Davidson und Harel Fruchtermann und Reingold Graph Drawing by Force-Directed Placement

3 Graph Drawing by Force-Directed PlacementProblemstellung Gegeben: Graph G=(V,E) Ungerichtet Gerade Kanten Gesucht: ästhetisch ansprechende Darstellung des Graphen Graph Drawing by Force-Directed Placement

4 Graph Drawing by Force-Directed PlacementProblemstellung Knoten gleichmäßig im Raum verteilen Kantenkreuzungen vermeiden Kanten gleich lang zeichnen Symmetrien hervorheben Nicht über den gegebenen Rahmen hinauszeichnen Evtl. noch 3d sachen erwähnen, Graphiken einfügen? Graph Drawing by Force-Directed Placement

5 Die Federanalogie [Eades '84]Knoten entsprechen Stahlringen Kanten entsprechen Zugfedern Ziel: Energielevel im System minimieren Graph Drawing by Force-Directed Placement

6 Graph Drawing by Force-Directed PlacementDie Federanalogie Noch zu malen, evtl. animiert? Graph Drawing by Force-Directed Placement

7 Graph Drawing by Force-Directed PlacementEades '84 Hookes Gesetz F = D(x – x0) wird nicht genau berechnet Für die anziehenden Kräfte nur Nachbarknoten betrachten: Θ(|E|) Für die abstoßenden Kräfte alle Knoten betrachten: Θ(|V|2) Überschrift? Hookes Law: mit Minus oder ohne vor dem k? Mit oder ohne Formeln? Evtl. Variablen vorher klären? Graph Drawing by Force-Directed Placement

8 Graph Drawing by Force-Directed PlacementKamada und Kawai '89 l13 = 1 x5 x2 l15 = 3 x4 x3 x6 x1 Graph Drawing by Force-Directed Placement

9 Graph Drawing by Force-Directed PlacementKamada und Kawai '89 Anziehende Kräfte zwischen allen Knoten, die verbunden sind Optimierungsfunktion: Σ D(|xi - xj| - lij)2 Weitere Punkte? Ohne Funktion? Graph Drawing by Force-Directed Placement

10 Graph Drawing by Force-Directed PlacementSimulated Annealing Randomisierte Startpositionen Hohe Anfangstemperatur Cooling- Funktion Evtl. Übergang zu einer minderwertigen Anordung Hill climbing Graph Drawing by Force-Directed Placement

11 Graph Drawing by Force-Directed PlacementDavidson und Harel '91 Simulated Annealing Optimierungsfunktion mit gewichteten Termen: Knotenverteilung Nähe zu Grenzen Kantenlängen Kantenkreuzung Sehr langsam Hohe Rechenleistung erforderlich. Graph Drawing by Force-Directed Placement

12 Fruchtermann und Reingold '91Zwei Bedingungen: Nachbarknoten sollen nah beieinander gezeichnet werden Nicht benachbarte Knoten sollen nicht zu nah beieinander gezeichnet werden Betrachtung der anziehenden und abstoßenden Kräfte wie Eades Hauptsache schnell Graph Drawing by Force-Directed Placement

13 Fruchtermann und ReingoldBerechnung der optimalen Distanz k: Bestimmung der anziehenden (attractive) und abstoßenden (repulsive) Kräfte durch: Graph Drawing by Force-Directed Placement

14 Fruchtermann und ReingoldBerechne für jeden Knoten v aus V: Alle abstoßenden Kräfte zu allen anderen Knoten mittels fr. → Θ(|V|2) Berechne zu jeder Kante e aus E: Für beide Knoten jeweils die anziehende Kraft mittels fa. → Θ(|E|) Gesamtkraft auf Knoten berechnen; Geschwindigkeit abhängig von Temperatur Knoten müssen im Rahmen bleiben Graph Drawing by Force-Directed Placement

15 Graph Drawing by Force-Directed PlacementRahmenproblem Sticky vertex Elastische Kollision Weiterrutschen Graph Drawing by Force-Directed Placement

16 Graph Drawing by Force-Directed PlacementDie Rastervariante x x2 x3 x4 Graph Drawing by Force-Directed Placement

17 Graph Drawing by Force-Directed PlacementDie Rastervariante x x2 x3 x4 k Graph Drawing by Force-Directed Placement

18 Graph Drawing by Force-Directed PlacementDie Rastervariante x x2 x3 x4 k Graph Drawing by Force-Directed Placement

19 Graph Drawing by Force-Directed PlacementDie Rastervariante k x x2 x3 x4 k Graph Drawing by Force-Directed Placement

20 Graph Drawing by Force-Directed PlacementDie Rastervariante Abstoßende Kräfte nur zwischen Knoten „in der Nähe“ Keine großen Unterschiede, außer in der Zeit Gleichverteilung der Knoten → Θ(|V|) Graph Drawing by Force-Directed Placement

21 Graph Drawing by Force-Directed PlacementPlanare Graphen Graph Drawing by Force-Directed Placement

22 Graph Drawing by Force-Directed Placement3D Graphen Hier kommt noch die andere Version hin Graph Drawing by Force-Directed Placement

23 Graph Drawing by Force-Directed PlacementLiteratur Thomas M. J. Fruchtermann and Edward M. Reingold „Graph Drawing by Force-directed Placement“ Software-Practice and Experience, Vol. 21 (1 1), (November 1991) Hookes Gesetz Graph Drawing by Force-Directed Placement

24 Graph Drawing by Force-Directed PlacementDanke fürs Zuhören Graph Drawing by Force-Directed Placement