ccvisu
Class MinimizerBarnesHut

java.lang.Object
  ccvisu.Minimizer
      ccvisu.MinimizerBarnesHut

public class MinimizerBarnesHut
extends Minimizer

Minimizer for the (weighted) (edge-repulsion) LinLog energy model, based on the Barnes-Hut algorithm.

Version:

$Revision: 1.31 $; $Date: 2007/12/15 02:03:35 $

Author:

Andreas Noack and Dirk Beyer Created: Andreas Noack, 2004-04-01. Changed: Dirk Beyer: Extended to edge-repulsion, according to the IWPC 2005 paper. Data structures changed to achieve O(n log n) space complexity. Energy model extended to a weighted version. 2006-02-08: Energy model changed to flexible repulsion exponent. Some bug fixes from Andreas integrated.

Nested Class Summary

private class

MinimizerBarnesHut.OctTree Octtree for graph nodes with positions in 3D space.

Field Summary

private float	attrExponent Exponent of the Euclidean distance in the attraction term of the energy model.
private int[][]	attrIndexes Node indexes of the similarity list for each node.
private float[][]	attrValues Similarity values of the similarity lists for each node.
private Position	baryCenter Position of the barycenter of the nodes.
private GraphData	graph The graph that this layout is computed for.
private float	gravitationFactor Factor for the gravitation energy (attraction to the barycenter), 0.0f for no gravitation.
private int	nodeNr Number of nodes.
private MinimizerBarnesHut.OctTree	octTree Octtree for repulsion computation.
private Options	options Options for the minimizer.
private float[]	repu Repulsion vector (node weights).
private float	repuExponent Exponent of the Euclidean distance in the repulsion term of the energy model.
private float	repuFactor Factor for repulsion energy that normalizes average distance between pairs of nodes with maximum similarity to (roughly) 1.
private static float[]	repuStrategy Factors for the repulsion force for pulsing.

Fields inherited from class ccvisu.Minimizer

listeners

Constructor Summary

MinimizerBarnesHut(Options pOpt)
Sets the number of nodes, the similarity matrices (edge weights), and the position matrix.

Method Summary

private float	addRepulsionDir(int index, MinimizerBarnesHut.OctTree tree, Position dir) Computes the direction of the repulsion force from the tree on the specified node.
private void	analyzeDistances() Computes and outputs some statistics.
private void	buildOctTree() Builds the octtree.
private void	computeBaryCenter() Computes the position of the barycenter baryCenter of all nodes.
private float	computeRepuFactor() Computes the factor for repulsion forces repuFactor such that in the energy minimum the average Euclidean distance between pairs of nodes with similarity 1.0 is approximately 1.
private void	getDirection(int index, Position dir) Computes the direction of the total force acting on the specified node.
private float	getDist(Position pos1, Position pos2) Returns the Euclidean distance between the specified positions.
private float	getEnergy(int index) Returns the energy of the specified node.
private float	getRepulsionEnergy(int index, MinimizerBarnesHut.OctTree tree) Returns the repulsion energy between the node with the specified index and the nodes in the octtree.
void	minimizeEnergy() Iteratively minimizes energy using the Barnes-Hut algorithm.

Methods inherited from class ccvisu.Minimizer

addGraphEventListener

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

options

private final Options options

Options for the minimizer.

nodeNr

private final int nodeNr

Number of nodes.

graph

private final GraphData graph

The graph that this layout is computed for. node. fixedPos: The minimizer does not change the position of a node with fixedPos == true. pos: Position matrix (3 dimensions for every node). Is not copied and serves as input and output of minimizeEnergy. If the input is two-dimensional (i.e. pos[i][2] == 0 for all i), the output is also two-dimensional. Random initial positions are appropriate. Preconditions: dimension at least [nodeNr][3]; no two different nodes have the same position The input positions should be scaled such that the average Euclidean distance between connected nodes is roughly 1.

attrIndexes

private final int[][] attrIndexes

Node indexes of the similarity list for each node. Is not copied and not modified by minimizeEnergy. (attrIndexes[i][k] == j) represents the k-th edge of node i, namely (i,j). Omit edges with weight 0.0 (i.e. non-edges). Preconditions: (attrIndexes[i][k] != i) for all i,k (irreflexive); (attrIndexes[i][k1] == j) iff (attrIndexes[j][k2] == i) for all i, j, exists k1, k2 (symmetric).

attrValues

private final float[][] attrValues

Similarity values of the similarity lists for each node. Is not copied and not modified by minimizeEnergy. For each (attrIndexes[i][k] == j), (attrValues[i][k] == w) represents the weight w of edge (i,j). For unweighted graphs use only 1.0f as edge weight. Preconditions: exists k1: (attrIndexes[i][k1] == j) and (attrValues[i][k1] == w) iff exists k2: (attrIndexes[j][k2] == i) and (attrValues[j][k2] == w) (symmetric).

repu

private final float[] repu

Repulsion vector (node weights). Is not copied and not modified by minimizeEnergy. For for node repulsion use 1.0f for all nodes. Preconditions: dimension at least [nodeNr]; repu[i] >= 1 for all i.

attrExponent

private float attrExponent

Exponent of the Euclidean distance in the attraction term of the energy model. 1.0f for the LinLog models, 3.0f for the energy version of the Fruchterman-Reingold model. If 0.0f, the log of the distance is taken instead of a constant fun. (Value 0.0f not yet tested.)

repuExponent

private float repuExponent

Exponent of the Euclidean distance in the repulsion term of the energy model. 0.0f for the LinLog models, 0.0f for the energy version of the Fruchterman-Reingold model. If 0.0f, the log of the distance is taken instead of a constant fun.

baryCenter

private Position baryCenter

Position of the barycenter of the nodes.

gravitationFactor

private float gravitationFactor

Factor for the gravitation energy (attraction to the barycenter), 0.0f for no gravitation.

repuFactor

private float repuFactor

Factor for repulsion energy that normalizes average distance between pairs of nodes with maximum similarity to (roughly) 1.

repuStrategy

private static final float[] repuStrategy

Factors for the repulsion force for pulsing.

octTree

private MinimizerBarnesHut.OctTree octTree

Octtree for repulsion computation.

Constructor Detail

MinimizerBarnesHut

public MinimizerBarnesHut(Options pOpt)

Sets the number of nodes, the similarity matrices (edge weights), and the position matrix.

Method Detail

minimizeEnergy

public void minimizeEnergy()

Iteratively minimizes energy using the Barnes-Hut algorithm. Starts from the positions in pos, and stores the computed positions in pos.

Specified by:

minimizeEnergy in class Minimizer

getDist

private float getDist(Position pos1,
                      Position pos2)

Returns the Euclidean distance between the specified positions.

Returns:

Euclidean distance between the specified positions.

getRepulsionEnergy

private float getRepulsionEnergy(int index,
                                 MinimizerBarnesHut.OctTree tree)

Returns the repulsion energy between the node with the specified index and the nodes in the octtree.

Parameters:

index - Index of the repulsing node.

tree - Octtree containing repulsing nodes.

Returns:

Repulsion energy between the node with the specified index and the nodes in the octtree.

getEnergy

private float getEnergy(int index)

Returns the energy of the specified node.

Parameters:

index - Index of a node.

Returns:

Energy of the node.

addRepulsionDir

private float addRepulsionDir(int index,
                              MinimizerBarnesHut.OctTree tree,
                              Position dir)

Computes the direction of the repulsion force from the tree on the specified node.

Parameters:

index - Index of the repulsed node.

tree - Repulsing octtree.

dir - Direction of the repulsion force acting on the node is added to this variable (output parameter).

Returns:

Approximate second derivation of the repulsion energy.

getDirection

private void getDirection(int index,
                          Position dir)

Computes the direction of the total force acting on the specified node.

Parameters:

index - Index of a node.

dir - Direction of the total force acting on the node (output parameter).

buildOctTree

private void buildOctTree()

Builds the octtree.

computeRepuFactor

private float computeRepuFactor()

Computes the factor for repulsion forces repuFactor such that in the energy minimum the average Euclidean distance between pairs of nodes with similarity 1.0 is approximately 1.

computeBaryCenter

private void computeBaryCenter()

Computes the position of the barycenter baryCenter of all nodes.

analyzeDistances

private void analyzeDistances()

Computes and outputs some statistics.