|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectccvisu.Minimizer
ccvisu.MinimizerBarnesHut
public class MinimizerBarnesHut
Minimizer for the (weighted) (edge-repulsion) LinLog energy model, based on the Barnes-Hut algorithm.
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 |
---|
private int nodeNr
private float[][] pos
private boolean[] fixedPos
private int[][] attrIndexes
private float[][] attrValues
private float[] repu
private float attrExponent
private float repuExponent
private float[] baryCenter
private float gravitationFactor
private float repuFactor
private static final float[] repuStrategy
private MinimizerBarnesHut.OctTree octTree
Constructor Detail |
---|
public MinimizerBarnesHut(int nodeNr, int[][] attrIndexes, float[][] attrValues, float[] repu, float[][] pos, boolean[] fixedPos, float attrExp, float repuExp, float gravitationFactor)
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 |
---|
public void minimizeEnergy(int nrIterations)
pos
,
and stores the computed positions in pos
.
minimizeEnergy
in class Minimizer
nrIterations
- Number of iterations. Choose appropriate values
by observing the convergence of energy.private float getDist(float[] pos1, float[] pos2)
private float getDistToBaryCenter(int i)
private float getRepulsionEnergy(int index, MinimizerBarnesHut.OctTree tree)
index
- Index of the repulsing node.tree
- Octtree containing repulsing nodes.
private float getEnergy(int index)
index
- Index of a node.
private float addRepulsionDir(int index, MinimizerBarnesHut.OctTree tree, float[] dir)
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).
private void getDirection(int index, float[] dir)
index
- Index of a node.dir
- Direction of the total force acting on the node
(output parameter).private void buildOctTree()
private float computeRepuFactor()
repuFactor
such that in the energy minimum the average Euclidean distance
between pairs of nodes with similarity 1.0 is approximately 1.
private void computeBaryCenter()
baryCenter
of all nodes.
private void analyzeDistances()
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |