Забыли?

?

# Force Directed Methods and Spring Algorithm

код для вставкиСкачать
```Force-Directed Methods
вЂ” Drawing Undirected Graphs
Force-Directed Methods
вЂў Use a physical analogy to draw graphs
вЂ“ How does the natural вЂњdrawвЂќ a graph?
вЂў View a graph as a system of objects with forces acting
between them.
вЂў Assumption: a balanced system gives a good layout
вЂў Specifically, a system configuration with locally minimal
energy:
вЂ“ The sum of the forces on each object is zero.
Force-Directed Methods
вЂў Vertex:
вЂ“ Object of the system;
вЂ“ Interacting with each other based on вЂњsomeвЂќ force(s).
вЂў Edge:
вЂ“ A different type of object;
вЂ“ Not interacting with each other;
вЂ“ Add new force(s) to vertex object.
вЂў Equilibrium configuration: the sum of forces on each
vertex object is zero
There are many force directed methods. In general, they
have two parts: model & algorithm
вЂў The model: a force system defined by vertices &
edges
вЂў The algorithm: a technique for finding an equilibrium
state, that is the sum of the forces on each vertex is
zero (force system); or
вЂ“ a technique for finding a configuration with locally minimal
energy (energy system)
Spring Methods
вЂў Vertex:
вЂ“ Electrically charged particles;
вЂ“ Repel each other.
вЂў Edge:
вЂ“ Spring that connect particles;
вЂ“ Attraction force when longer than the natural length;
вЂ“ Repulsion force when shorter than the natural length.
1.
2.
A Larger Example
6
Many Variations
1.
2.
3.
4.
5.
6.
Spring & electrical force
Barycenter method
Force simulating graph theoretic distance
Magnetic field
General energy function
Constraints
1. Springs & Electrical Forces
вЂў Use a combination of spring & electrical forces
вЂ“ Edge: modeled as spring
вЂ“ Vertex: equally charged particles which repel each other
вЂў The force on v : F(v) = ОЈ f u,v + ОЈ g u,v
(u,v)пѓЋE
(u,v)пѓЋVxV
вЂў f u,v : force on v by the spring between u an v
: follow HookвЂ™s law (proportional to the difference
between the distance between u and v and the zeroenergy length of the spring)
вЂў g u,v : Electrical repulsion exerted on v by vertex u
вЂў d(p,q) : Euclidean distance between points p and q
вЂў pv = (xv, yv): position of vertex v
вЂў x component of the force on v
пѓҐk
( u , v )пѓЋ E
1
uv
( d ( p u , p v ) пЂ­ l uv )
xv пЂ­ xu
d ( pu , pv )
пЂ«
пѓҐ
( u , v )пѓЋV п‚ґV
xv пЂ­ xu
2
k uv
( d ( p u , p v ))
2
пѓ—
d ( pu , pv )
lu,v : natural (zero energy) length of the spring between u
and v
: if the spring has natural length lu,v, no force is exerted;
k1u,v : stiffness of the spring between u and v
: the larger k1u,v , the more tendency for the distance between u
and v to be close to lu,v.
k2u,v : the strength of the electrical repulsion between u
and v
Aim of the force model design:
вЂў Spring force:
вЂ“ Ensure the distance between adjacent vertices u and v is
approximately equal to lu,v.
вЂў Electrical force:
вЂ“ Ensure vertices not too close to each other.
вЂў One may choose parameters luv k1u,v k2u,v to customize
for specific applications.
вЂў There are many technique to find an equilibrium
configuration (or minimum energy).
вЂў Simple algorithm
вЂ“ Initially at random location
вЂ“ At each iteration:
вЂў Force F(v) on each vertex is computed
вЂў Each vertex v is moved in the direction of F(v) by a small
amount proportional to the magnitude of F(v)
вЂ“ Stops when equilibrium is achieved or some conditions are
met.
вЂў Not the fastest, but allow smooth animation.
вЂў Calculating attractive forces only between neighbors:
O(|E|)
вЂў Calculating repulsive forces between all pair of
vertices: O(|V|2)
вЂ“ Bottleneck of the algorithm in general
вЂњLogarithmic springвЂќ
вЂў Rather than HookвЂ™s law, the spring force is calculated as:
F (v ) пЂЅ k
1
uv
пѓ¦ d ( pu , pv )
log пѓ§пѓ§
l uv
пѓЁ
пѓ¶ xv пЂ­ xu
пѓ·
пѓ· d(p , p )
u
v
пѓё
вЂў Hook Law (linear) spring is too strong when the vertices
are far
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
вЂў
Relatively simple & easy to implement
Good flexibility
Handle domain constraints
Smooth evolution of the drawing into the final configuration
helps preserving the userвЂ™s mental map
Can be extended to 3D
Often able to display symmetries
Works well in practice for small graphs with regular
structure
Show some clustering structure
вЂў Slow running time
вЂў Results are acceptable, but not brilliant
вЂў Few theoretical results on the quality of the drawings
produced
вЂў Difficult to extend to orthogonal & polyline drawings
вЂў Limited constraint satisfaction capability
2. Barycenter Method [Tutte60,63]
вЂў Use springs with natural length 0, and attractive force
proportional to the length
вЂў Pin down the vertices of the external face to form a given convex
polygon (position constraint)
вЂў Let the system goвЂ¦
пѓҐ
k
1
uv
( d ( p u , p v ) пЂ­ l uv )
( u , v )пѓЋ E
xv пЂ­ xu
пѓҐ
пЂ«
d ( pu , pv )
( u , v )пѓЋV п‚ґV
вЂў luv = 0, k1u,v = 1, no electrical force
пѓҐ
( u , v )пѓЋ E
d ( pu , pv ) пѓ—
xv пЂ­ xu
d ( pu , pv )
пЂЅ
пѓҐ (x
( u , v )пѓЋ E
вЂў Trivial solution pv = 0 for all v
v
пЂ­ xu )
2
k uv
( d ( p u , p v ))
2
пѓ—
xv пЂ­ xu
d ( pu , pv )
вЂў Partition V into two sets: fixed vertex (at least 3, nailed down) and
free vertex
вЂў To achieve equilibrium, choose pv so that Fx(v) = 0 for all free
vertices;
вЂ“ Similarly, choose pv so that Fy(v) = 0 for all free vertices.
Therefore,
Fx (v ) пЂЅ
пѓҐ (x
( u , v )пѓЋ E
v
пЂ­ x u ) пЂЅ deg( x ) пѓ— x v пЂ­
пѓҐx
wпѓЋ N 0 ( v )
вЂў Where deg(v) is the degree of v,
вЂўN0(v): set of fixed neighbor of v;
вЂўN1(v): set of free neighbor of v.
*
w
пЂ­
пѓҐx
uпѓЋ N 1 ( v )
u
пЂЅ0
deg( v ) x v пЂ­
пѓҐ
xu пЂЅ
uпѓЋ N 1 ( v )
пѓҐ
x w , deg( v ) y v пЂ­
*
wпѓЋ N 0 ( v )
пѓҐ
yu пЂЅ
uпѓЋ N 1 ( v )
пѓҐ
*
yw
wпѓЋ N 0 ( v )
вЂў The equations are linear.
вЂў The number of equations and the number of
unknownvariables are both equal to the number of
free vertices.
вЂў Solving them equals to placing each free vertex at the
barycenter of its neighbours.
вЂ“ So the name вЂ�barycenter methodвЂ™.
Algorithm Barycenter-Draw
Input: partition of V,
V0: at least 3 fixed vertices
V1: set of free vertices
Strictly convex polygon P with V0 vertices
Output: position pv
1. Place each vertex u in V0 at a vertex of P and each free
vertex at the origin
2. Repeat
For each free vertex v do
xv = _____
1
S xu
deg(v) (u,v)пѓЋE
yv = _____
1
S yu
deg(v) (u,v)пѓЋE
Until xv and yv converge for all free vertices v
An Example
3. Force Simulating Graph Theoretic Distance
вЂў Model graph-theoretic distance with Euclidean distance
вЂ“ The forces try to place vertices so that their geometric
distance in the drawing is proportional to their graph
theoretic distance
вЂў For each pair of vertices (u, v), Оґ(u,v) is the graph-theoretic
distance between them;
вЂ“ Number of edges on a shortest path between u and v.
вЂў Aim: find a drawing such that for each pair of vertices, the
Euclidean distance d(pu, pv) is approximately proportional
to Оґ(u,v)
вЂ“ i.e. system has a force proportional to d(pu, pv) - d(u,v)
вЂў Potential energy in the spring between u and v:
ВЅ kuv (d(pu, pv) - d(u,v))2
вЂў Choose stiffness parameter: springs between vertices that
have small graph theoretic distance are stronger
kuv = k / d(u,v)2
вЂў Thus, energy in (u, v): h = k/2 (d(pu, pv)/d(u,v) вЂ“ 1)2
вЂў Energy in the whole drawing is the sum of individual
energies:
h = k/2 S (d(pu, pv)/d(u,v) вЂ“ 1)2
u п‚№v пѓЋE
вЂў Algorithm seek a position pv=(xv, yv), for each vertex v to
minimize h
вЂў п‚¶ h / п‚¶ xv = 0, п‚¶ h / п‚¶ yv = 0, v пѓЋ V : non linear equation
вЂ“ Partial derivatives with respect to each xv and yv are zero
вЂў However, iterative approach can solve the equation
вЂў At each step, a vertex is moved to a position that
minimizes energy, while other vertices remain fixed
вЂў Choose a vertex that has the largest force acting on it,
that is
2
пѓ¦ п‚¶h
пѓ¦ п‚¶h пѓ¶
пѓ§
пѓ· пЂ« пѓ§пѓ§
пѓЁ п‚¶x пѓё
пѓЁ п‚¶y
is maximized for all v in V.
пѓ¶
пѓ·пѓ·
пѓё
2
4. Magnetic Fields [SM95]
вЂў Variations:
вЂ“ Some or all of the springs are magnetized
вЂ“ There is a global magnetic field that acts on the spring
вЂ“ Magnetic field can be used to control the orientation of edges
вЂў 3 types of magnetic fields
вЂ“ Parallel: all magnetic forces operate in the same direction
вЂ“ Concentric: the force operates in concentric circles
вЂў The three basic magnetic fields can be combined
вЂ“ encourage orthogonal edges with a combination of parallel
forces in the horizontal & vertical directions
вЂў The springs can be magnetized in two ways:
вЂ“ Unidirectional: the spring tends to align with direction of the
magnetic field
вЂ“ Bidirectional: the spring tends to align with the magnetic field,
but in either direction
вЂў A spring may not be magnetized at all
вЂў The magnetic field induces a torsion or rotational force
on the magnetic springs.
вЂў For a unidirectionally magnetized spring representing
(u,v), the force is proportional to d(pu, pv) aq b
d(pu, pv): Euclidean distance between pu and pv
q: angle between the magnetic field and the line from pu to pv
a and b are constant
Unidirectional magnetic spring
Оё
Direction of the magnetic field
вЂў The magnetic forces are combined with the spring &
electrical force
вЂў Algorithm to find equilibrium:
вЂ“ initially random position and at each iteration move the vertex
to lower energy position
вЂў Can handle directed graphs (unidirectional springs with
one of the 3 fields)
вЂ“ arcs point downward: downward parallel field
вЂ“ Counterclockwise: concentric field
вЂў Can be applied to orthogonal drawings: combined
vertical & horizontal field with bidirectional springs
вЂў Applied with success to mixed graphs (graph with both
directed & undirected edges)
Two Examples
Vertical magnetic field
Vertical and horizontal
magnetic field
5. General Energy Function
вЂў Most of the energy function h is a simple continuous
function of the location of vertices. However, many of
aesthetic criteria are not continuous
вЂў Including discrete energy function
вЂ“ The number of edge crossings
вЂ“ The number of horizontal & vertical edges
вЂ“ The number of bends in edges
вЂў general energy function
h пЂЅ l 1 h 1 + l 2 h 2 + вЂ¦ + lk h k
п‚– hi : a measure for an aesthetic criterion
вЂ“ May include spring, electrical, magnetic energy
[Davidson & Harel 96] energy function for
straight line drawings
h пЂЅ l1 h 1 + l2 h 2 + l3 h 3 + l4 h 4
h1 = Su,vпѓЋV (1/ (d(pu, pv))2 ) : similar to electrical repulsion
(vertices do not come too close together)
h2 пЂЅ
пѓҐ
(( 1 / ru ) пЂ« (1 / l u ) пЂ« (1 / t u ) пЂ« (1 / bu ))
2
2
2
2
u пѓЋV
ru, lu, tu, bu: Euclidean distance between vertex u and
the four side lines of rectangular area (vertices do not
come too close to the border of the screen)
h3 = S(u,v)пѓЋE (d(pu, pv))2 : edges do not become too long
h4 : the number of edge crossings in the drawing
вЂў Flexibility of general energy function: allow variety of
вЂ“ [BBS97]: user can choose & adjust system parameters
вЂ“ [Mendonca94]: how these coefficients can be automatically
вЂў Main problem: computationally expensive to find a
minimum energy state (very slow)
вЂ“ simulated annealing [DH96]вЂ¦..
вЂ“ Genetic algorithm [BBS97]вЂ¦
вЂў Flexibility ensures popularity
[Davidson & Harel 96]
simulated annealing
вЂў Energy function takes into account vertex distribution,
edge-lengths, and edge-crossings
вЂў Given drawing region acts as wall
вЂў Simulated annealing: flexible optimization technique
вЂў Efficiency: very slow
вЂў 30 nodes and 50 edges
вЂў Able to deal with optimization problem in a discrete
configuration space
вЂў Aim: to minimize (or maximize) the cost function
вЂў Using 3 different energy functions
6. Constraints
вЂў Force-directed methods can be extended to support
several types of constraints
6.1. Position constraints
6.2. Fixed-subgraph constraints
6.3. Constraints that can be expressed by force or energy
function
6.1. Position constraints
вЂў assign to a vertex a
topologically connected
region where the vertex
should remain
вЂ“ Single point: a vertex nail
down at a specific location
вЂ“ Horizontal line: group of
vertices arranged on a
layer
вЂ“ A circle: set of vertices to
be restricted to a distinct
region
вЂў [Ostry96]: constraints
vertices to curves and 3D
surfaces
6.2. Fixed subgraph constraints
вЂў Assign prescribed drawing to a subgraph .
вЂў May be translated or rotated, but not deformed.
вЂў Considering the subgraph as a rigid body.
вЂў For example, barycenter method is a force-directed
method that constrains a set of vertices (fixed
external vertices) to a polygon.
6.3. Constraints expressed by forces
вЂў Constraints expressed by forces
вЂ“ Orientation of directed edges: magnetic spring
вЂ“ Geometric clustering of special set of vertices
вЂ“ Alignment of vertices
вЂў Clustering can be achieved [ECH97]
вЂ“ For each set C of vertices, add a dummy attractor vertex vC
вЂ“ Add attractive forces between an attractor vC and each vertex in
C.
вЂ“ Add repulsive forces between pairs of attractors and between
attractors and vertices not in any cluster.
Remark
вЂў Improve the efficiency
вЂ“ [FR91]: amenable force functions
вЂ“ [FLM95, Tun92]: use randomization in S.A.
вЂ“ [Ost96]: the equations describing the minimal energy states
are stiff for some graphs of low connectivity.
вЂ“ [HS95]: use combinatorial preprocessing step, good initial
layout
вЂў [BHR96] empirical analysis
вЂ“ [FR91],[KK89],[DH96],[Tun92],[FLM95]
вЂ“ No winner, try several methods and then choose the best
Faster Spring methods
вЂў Problem: Spring methods are too slow for huge graphs
Computing
the forces
takes
time
1. pu = some initial position for each node u;
2. Repeat
2.1 Fu := 0 for each node u;
2.2 For each pair u,v of nodes
2.2.1 calculate the force fuv betwe
en u and v;
2.2.2 Fu += fuv;
2.2.3 Fv += fuv;
2.3 For each node u, pu += eFu;
Until pu converges for all u;
вЂў It is feasible to use
1. a spring method, then
2. a geometric clustering method
to obtain a good graph clustering.
Graph
Clustered
Graph
вЂў A tree data structure
вЂў Each internal node has up to
four children.
вЂў Most often used to partition a
two dimensional
вЂ“ Recursively subdividing it into
contains one point.
вЂў In general, recursively partition
the space into 2d subspace
equally, where d is the
dimension
вЂ“ Known as Octree for 3D
Barnes-Hutt method
вЂў A method of computing forces between
stars.
вЂ“ Use Quadtree to cluster the stars
вЂ“ Use the forces between the clusters to
approximate the forces between individual
stars.
root
a
d
c
c
TL
b
e
a
b
BR
d
BL
f
e
f
Barnes-Hutt method
вЂў The contents of a subtree of can be
approximated by a mass at the centroid.
root
a
d
c
c
TL
b
es
a
b
BR
s
d
BL
f
e
f
Barnes-Hutt method
вЂў The force that the subtree s exerts on the star x
can approximate the sum of the forces that the
nodes in s exert on x.
root
a
d
c
c
TL
b
es
a
b
BR
s
d
BL
f
e
f
To compute the force on star x, we proceed from the
root toward the leaves.
ComputeForce(star x; treenode t)
If the approximation is good
then return the approximation;
else return SsComputeForce(x, s), where
the sum is over all children s of t.
A simple method can be used to determine whether the
approximation is good; it depends on the mass of nodes and the
distance between x and s.
w(t) / d(x,t) < c,
w(t) the width of t; d(x,t) the distance between x and t, and c is a
constant.
вЂў The Barnes-Hutt method is faster than the usual
spring algorithm.
1. px = some initial position for each
star x;
2. Repeat
In practice,
computing all the
forces takes
O(n log n) time
2.2 Foreach star x
ComputeForce(x,root);
2.3 Foreach star x, px += eFx;
Until px converges for all x;
вЂў At each iteration, the node movements introduced in the previous
вЂ“ Makes the quadtre clustering (a geometric clustering) better reflects the
graph clustering.
1. pu = some initial position for each
node u;
2. Repeat
Some nodes
migrate from one
cluster to the
next
2.2 Foreach node u
ComputeForce(u,root);
2.3 Foreach node u, pu += eFu;
Until pu converges for all u;
вЂў Observations
вЂ“ The Quadtree provides a clustering of the data
вЂ“ If the data is well clustered, then BH runs faster
вЂў The approximated force is then more accurate
вЂ“ The spring algorithm tends to cluster the data
вЂў This means that we can:
вЂ“ Use Barnes-Hutt to compute the clusters as well as the drawing
вЂ“ Use the quadtree as the clustering for the clustered graph
Experimental
Result
The error is the difference between
the approximated force vector and
the original one
Visual abstraction
Can we use other natural system
analogy?
```
###### Документ
Категория
Презентации
Просмотров
10
Размер файла
1 014 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа