ccvisu
Class MinimizerBarnesHut

java.lang.Object
  extended by ccvisu.Minimizer
      extended by 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.8 $; $Date: 2006/11/25 10:41:07 $
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 energy.
private  int[][] attrIndexes
          Node indexes of the similarity lists.
private  float[][] attrValues
          Similarity values of the similarity lists.
private  float[] baryCenter
          Position of the barycenter of the nodes.
private  boolean[] fixedPos
          The minimizer does not change the position for nodes with entry true.
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  float[][] pos
          Position in 3-dimensional space for every node.
private  float[] repu
          Repulsion vector.
private  float repuExponent
          Exponent of the Euclidean distance in the repulsion energy.
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
listener
 
Constructor Summary
MinimizerBarnesHut(int nodeNr, int[][] attrIndexes, float[][] attrValues, float[] repu, float[][] pos, boolean[] fixedPos, float attrExp, float repuExp, float gravitationFactor)
          Sets the number of nodes, the similarity matrices (edge weights), and the position matrix.
 
Method Summary
private  float addRepulsionDir(int index, MinimizerBarnesHut.OctTree tree, float[] 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, float[] dir)
          Computes the direction of the total force acting on the specified node.
private  float getDist(float[] pos1, float[] pos2)
          Returns the Euclidean distance between the specified positions.
private  float getDistToBaryCenter(int i)
          Returns the Euclidean distance between node i and the baryCenter.
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(int nrIterations)
          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

nodeNr

private int nodeNr
Number of nodes.


pos

private float[][] pos
Position in 3-dimensional space for every node.


fixedPos

private boolean[] fixedPos
The minimizer does not change the position for nodes with entry true.


attrIndexes

private int[][] attrIndexes
Node indexes of the similarity lists.


attrValues

private float[][] attrValues
Similarity values of the similarity lists.


repu

private float[] repu
Repulsion vector.


attrExponent

private float attrExponent
Exponent of the Euclidean distance in the attraction energy.


repuExponent

private float repuExponent
Exponent of the Euclidean distance in the repulsion energy.


baryCenter

private float[] 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(int nodeNr,
                          int[][] attrIndexes,
                          float[][] attrValues,
                          float[] repu,
                          float[][] pos,
                          boolean[] fixedPos,
                          float attrExp,
                          float repuExp,
                          float gravitationFactor)
Sets the number of nodes, the similarity matrices (edge weights), and the position matrix.

Parameters:
nodeNr - number of nodes.
attrIndexes - Node indexes of the similarity list for each node. Is not copied and not modified by this class. (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 - Similarity values of the similarity lists for each node. Is not copied and not modified by this class. 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 - Repulsion vector (node weights). Is not copied and not modified by this class. For for node repulsion use 1.0f for all nodes. Preconditions: dimension at least [nodeNr]; repu[i] >= 1 for all i.
pos - Position matrix. 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.
fixedPos - The minimizer does not change the position of a node i with fixedPos[i] == true.
attrExp - Exponent of the 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.)
repuExp - Exponent of the 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.
gravitationFactor - Factor for the gravitation energy (attraction to the barycenter). 0.0f for no gravitation.
Method Detail

minimizeEnergy

public void minimizeEnergy(int nrIterations)
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
Parameters:
nrIterations - Number of iterations. Choose appropriate values by observing the convergence of energy.

getDist

private float getDist(float[] pos1,
                      float[] pos2)
Returns the Euclidean distance between the specified positions.

Returns:
Euclidean distance between the specified positions.

getDistToBaryCenter

private float getDistToBaryCenter(int i)
Returns the Euclidean distance between node i and the baryCenter.

Returns:
Euclidean distance between node i and the baryCenter.

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,
                              float[] 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,
                          float[] 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.