Onderzoeksmethoden Force directed graph drawing

Onderzoeksmethoden
Force directed graph drawing
Gebaseerd op materiaal
van
Hans Bodlaender
1
Grafen
  Grafen G=(V,E)
  V is verzameling
knopen (“nodes”,
“vertices”)
  E is verzameling
kanten (“edges”)
•  Een kant is een
verzameling van
twee verschillende
knopen
2
  V={1,2,3}
  E={ {1,2}, {2,3}}
2
1
3
Toepassingen van grafen
  Grafen als model voor o.a.:
  Wegennetwerken
  Landschappen in computer games
  Linkstructuur van website
  Vriendschapsrelaties uit sociaal netwerk
  Klassediagram van object georienteerd programma
  Etc. etc.
3
Tekenen van grafen
  Wens om een graaf te tekenen op het platte vlak zodat
  “mooi”
  “duidelijk”
  Veel methoden
  We bekijken in dit project het force-directed graph drawing
algoritme. Die methode laat nog veel keuzes open,
instellen parameters….
  Force-directed methoden toegepast binnen
  Geografische informatie systemen
  Computer vision
  Motion planning
4
Tekening van graaf
(met rechte lijnen)
 Iedere knoop
heeft een x en
een y coordinaat
 Elke kant is een
rechte lijn tussen
de twee knopen
 Lijnen kunnen
kruisen
Zelfde graaf, twee verschillende tekeningen
5
Force directed
Veren en magneten
  Inspiratie: natuurkundige wetten
  Iedere knoop wordt “gezien als” een magneet: knopen
stoten elkaar af
  Iedere kant wordt “gezien als” een veer: kracht die veer
naar “juiste lengte” wil trekken
6
Idee van methode
  Elke knoop heeft
een positie (xcoordinaat, ycoordinaat)
  Op elke knoop
wordt een kracht
uitgeoefend
  Hangt af van
afstanden naar
andere knopen en
lengte van kanten
met die knoop als
een eindpunt
7
  Herhaal totdat
tekening niet heel
erg veranderd
  Voor elke knoop v
reken kracht uit op v
  Verplaats v
evenredig met de
kracht op v
Keuzes
  Kies voor elke kant {u,v} in de graaf waardes:
  Stijfheid suv
  Gewenste lengte luv
  Kies voor elk paar knopen u en v
  De afstotende werking (repulsie) van u en v ruv
  Misschien wil je al die waarden hetzelfde nemen, misschien
niet?
8
Kracht op knoop
  Noteer: d(u,v) = Euclidische afstand van u naar v
  xv : x-coordinaat van v
  yv : x-coordinaat van v
  Kracht op knoop v in x-richting Px(v):
xv − xu
ruv
s uv ∗ (d(u, v) − l uv ) ∗
+
∗ (x v − x u )
3
d(u, v) u:u ≠ v (d(u, v))
u:{u , v}∈E
∑
∑
Soortgelijke formule voor Py(v)
Staan ook in info op website.
9
Krachten op knopen
afstoten
aantrekken
10
Algoritme (schets)
  Maak een eerste locatie voor alle punten
  Herhaal totdat (stopcriterum geldt):
  Voor alle knopen v, bereken Px(v) en Py(v)
  Voor elke knoop v
•  xv += c * Px(v)
•  yv += c * Py(v)
  c is een kleine constante
11
Vragen
 Algoritme heeft veel keuzes open:
waarden van parameters (stijfheid,
gewenste lengtes, repulsies, waarde
van c, begintekening, stopcriterium)
 Wat is een goede invulling van die
keuzes?
 En wat bedoelen we met die vraag?
12

Download Report