Message-ID: <2089692956.1627.1618838514603.JavaMail.root@wiki.cns.iu.edu> Subject: Exported From Confluence MIME-Version: 1.0 Content-Type: multipart/related; boundary="----=_Part_1626_1882636283.1618838514603" ------=_Part_1626_1882636283.1618838514603 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Content-Location: file:///C:/exported.html Force Directed with Annotation (prefuse beta)

# Force Directed with Annotation (prefuse beta)

###### Des= cription
=20

Spring embedding algorithms also called FDP (Force Directed Placement) c= an be used to sort randomly placed nodes into a desirable layout that satis= fies the aesthetics for visual presentation (symmetry, non-overlapping etc.= ) See Eades (1984) and Jones' webpage.

=20

FDP (Battista et al., 1984) views nodes as physical bodies and edges as = springs connected to the nodes providing forces between them. Nodes move ac= cording to the forces on them until a local energy minimum is achieved. In = addition to the imaginary springs, other forces can be added to the system = in order to produce different effects (see table). Many visual examples of = these force models can be found in Battista et al. (1984).

=20
=20 =20 =20 =20 =20 =20 =20 =20 =20 =20 =20 =20 =20 =20 =20 =20 =20 =20 =20 =20
 Force Model Formula Example of Usage Spring Force F =3D k(1-a) k- stiffness o= f spring a- natural length of spring Assigning different k and a to different edg= es to separate nodes by different distances. Gravity Force F =3D g/r2 g- associated wi= th mass of node, usually equals 1. Apply gravity force between node pairs to pr= event node overlapping. Electrical and Magnetic Force F =3D eE F =3D qB E- electric field strength B- mag= netic field strength Changes nodes distribution along a direction= . FDP was extended to three dimensions by Kumar & Fowler (1996). =20
=20

A simple algorithm to find the equilibrium configuration is to trace the= move of each node according to Newton's 2nd law. This takes time O n3, whi= ch makes it unsuitable for large data sets. Rob Forbes (1987) proposed two = methods that were able to accelerate convergence of a FDP problem 3-4 times= . One stabilizes the derivative of the repulsion force and the other uses i= nformation on node movement and instability characteristics to make a predi= ctive extrapolation. In a recent paper, Huang et al. (1998) describe a syst= em that uses a "logical frame" to present a subgraph of the entire graph. A= lgorithms are provided to smoothly migrate from one logical frame to anothe= r.

=20
=20
=20
###### Pros &= ; Cons
=20

The FDP method is easy to understand and implement, but is very slow for= large graphs.

=20
###### Applicatio= ns
=20

Force directed graph drawing algorithms are increasingly popular in info= rmation visualization. They have been used in BEAD (Chalmers, 1992), Narcis= sus (Hendley, 1995), SHriMP (Simple Hierarchical Multi-Perspective views) (= Storey, 1995) and SPIRE (Hetzler et al., 1998) see (Young, 1996). They can/= have also been used to generate graphical representations of Pathfinder networks<= /a>?.

=20

Some Demo's & Examples:

=20
=20
###### I= mplementation Details
=20

In class we will use a java code that was originally implemented by Sun = Microsystems, Inc. and was modified by Larry Mongin. In particular, the app= earance of the nodes was changed, the forces between these nodes were modif= ied, and several variables like system energy, step bound, iteration step a= nd several functions were added to observe (and interact with nodes during)= sorting.

=20
###### Acknow= ledgements
=20

The java applet was implemented by Yuezheng Zhou. Nihar Sanghvi integrat= ed the code into the software repository.

=20
###### See Als= o
=20

The license could not be verified: License Certificate has expired!=20 Generate a Free license now.

------=_Part_1626_1882636283.1618838514603--