CIShell Manual : Force Directed with Annotation (prefuse beta)
This page last changed on Apr 08, 2011 by dapolley.
DescriptionSpring embedding algorithms also called FDP (Force Directed Placement) can be used to sort randomly placed nodes into a desirable layout that satisfies the aesthetics for visual presentation (symmetry, non-overlapping etc.) See Eades (1984) and Jones' webpage. FDP (Battista et al., 1984) views nodes as physical bodies and edges as springs connected to the nodes providing forces between them. Nodes move according 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).
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, which 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 information on node movement and instability characteristics to make a predictive extrapolation. In a recent paper, Huang et al. (1998) describe a system that uses a “logical frame” to present a subgraph of the entire graph. Algorithms are provided to smoothly migrate from one logical frame to another. LinksPros & ConsThe FDP method is easy to understand and implement, but is very slow for large graphs. ApplicationsForce directed graph drawing algorithms are increasingly popular in information visualization. They have been used in BEAD (Chalmers, 1992), Narcissus (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?. Some Demo's & Examples: XHDG - X toolkit Hierarchical Directed Graphs Implementation DetailsIn class we will use a java code that was originally implemented by Sun Microsystems, Inc. and was modified by Larry Mongin. In particular, the appearance of the nodes was changed, the forces between these nodes were modified, and several variables like system energy, step bound, iteration step and several functions were added to observe (and interact with nodes during) sorting. Usage HintsThe Spring package can be found on ella in '/home/www/ella/htdocs/classes/L697/code/infovis/gui/spring'. The implementation in the Information Visualization XML Toolkit can be found on ella in '/home/www/ella/htdocs/classes/L697/code/infovis/xmlbridge'. To use only the spring portion of the toolkit you will need an entire copy of the Spring Package and the Information Visualization XML Toolkit, as listed in the above directories on ella. You need to maintain the package (directory) structure of these copied files for it to work with your own code. You will need to use XMLSpring as a visual component just like any other Swing component (initialize it and add it to a container in an applet or application). Please review the following applet Example.java. The demo is also in the Information Visualization XML Toolkit. The demo can be found on ella in '/home/www/ella/htdocs/classes/L697/code/infovis/demo/'. Copy the demo files to a machine with the proper JDK (1.3 with the XML pack or 1.4) and then double click on infovis.jar to open the demo. Click on 'Select File' to select a XML file to visualize and select one of the XML files from the demo. Note: there are 3 files (hierarchy.xml, tabular.xml, list.xml) and their names indictate their structure type so you should know which visualizations can use which XML file. Variations: Change appearance of the nodes, the forces between these nodes, energy, step bound, iteration steps. AcknowledgementsThe java applet was implemented by Yuezheng Zhou. Nihar Sanghvi integrated the code into the software repository. References
See Also |
![]() |
Document generated by Confluence on May 31, 2011 16:37 |