Misc. Prefuse Information

These notes are taken from the javadocs provided with Prefuse or from the main 2005 paper, and most of them are authored by Jeffrey Heer. The full index for the Prefuse package can be found here.

Main Paper

[prefuse: a toolkit for interactive information visualization http://jheer.org/publications/2005-prefuse-CHI.pdf], by Jeffrey Heer, Stuart K. Card, and James A. Landay.

The Force Field and Related Objects

Force Simulation

prefuse includes an extensible and configurable library for force-based physics simulations. This consists of a set of force functions, including n-body forces (e.g., gravity), spring forces, and drag forces. To support real- time interaction, n-body force calculations use the Barnes- Hut algorithm [2] to compute the otherwise quadratic calculation in log-linear time. The force simulation supports various numerical integration schemes, with trade-offs in efficiency and accuracy, to update velocity and position values. The provided modules abstract the mathematical details of these techniques (e.g., 4 th Order Runge-Kutta) from toolkit users. Users can also write custom force functions and add them to the simulator

Force

The Force function computes an n-body force such as gravity, anti-gravity, or the results of electric charges. This function implements the the Barnes-Hut algorithm for efficient n-body force simulations, using a quad-tree with aggregated mass values to compute the n-body force in O(N log N) time, where N is the number of ForceItems.

The algorithm used is that of J. Barnes and P. Hut, in their research paper A Hierarchical O(n log n) force calculation algorithm, Nature, v.324, December 1986. For more details on the algorithm, see one of the following links --

• James Demmel's UC Berkeley lecture notes
• Description of the Barnes-Hut algorithm
• Joshua Barnes' recent implementation

ForceFieldLayout

The ForceFieldLayout is a Layout that positions graph elements based on a physics simulation of interacting forces; by default, nodes repel each other, edges act as springs, and drag forces (similar to air resistance) are applied. This algorithm can be run for multiple iterations for a run-once layout computation or repeatedly run in an animated fashion for a dynamic and interactive layout.

The running time of this layout algorithm is the greater of O(N log N) and O(E), where N is the number of nodes and E the number of edges. The addition of custom force calculation modules may, however, increase this value.

The ForceSimulator used to drive this layout can be set explicitly, allowing any number of custom force directed layouts to be created through the user's selection of included Force components. Each node in the layout is mapped to a ForceItem instance and each edge to a Spring instance for storing the state of the simulation. See the prefuse.util.force package for more.

N-Body Force

Parameters:

• gravConstant - the gravitational constant to use. Nodes will attract each other if this value is positive, and will repel each other if it is negative.
• minDistance - the distance within which two particles will interact. If -1, the value is treated as infinite.
• theta - the Barnes-Hut parameter theta, which controls when an aggregated mass is used rather than drilling down to individual item mass values.