org.coolmap.core.util.network

Class MinimizerBarnesHut

java.lang.Object

org.coolmap.core.util.network.MinimizerBarnesHut

public class MinimizerBarnesHut
extends java.lang.Object

Minimizer for the LinLog energy model and its generalizations, for computing two- and three-dimensional graph layouts. Based on the Barnes-Hut algorithm. For more information about the LinLog energy model, see the (freely downloadable) article Andreas Noack: "Energy Models for Graph Clustering", Journal of Graph Algorithms and Applications 11(2):453-480, 2007.

Constructor Summary

Constructors

Constructor and Description
MinimizerBarnesHut(java.util.Collection<Node> nodes, java.util.Collection<Edge> attrEdges, double repuExponent, double attrExponent, double gravFactor) Initializes the attributes.

Method Summary

Modifier and Type	Method and Description
void	minimizeEnergy(java.util.Map<Node,double[]> positions, int nrIterations) Iteratively minimizes energy using the Barnes-Hut algorithm.

Methods inherited from class java.lang.Object

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

Constructor Detail

MinimizerBarnesHut

public MinimizerBarnesHut(java.util.Collection<Node> nodes,
                          java.util.Collection<Edge> attrEdges,
                          double repuExponent,
                          double attrExponent,
                          double gravFactor)

Initializes the attributes.

Parameters:

nodes - nodes with weights specifying their repulsion strengths. More precisely, the repulsion between every pair of different nodes is proportional to the product of their weights. It is recommended to use so-called "edge-repulsion", which means to set the weight of each node to the sum of the weights of its attraction edges. Weights must not be negative.

attrEdges - attraction edges. Omit edges with weight 0.0 (i.e. non-edges). For unweighted graphs use weight 1.0 for all edges. Weights must not be negative. Weights must be symmetric, i.e. the weight from node n1 to node n2 must be equal to the weight from node n2 to node n1.

repuExponent - exponent of the distance in the repulsion energy. Exception: The value 0.0 corresponds to logarithmic repulsion. Is 0.0 in both the LinLog and the Fruchterman-Reingold energy model. Negative values are permitted.

attrExponent - exponent of the distance in the attraction energy. Is 1.0 in the LinLog model (which is used for computing clusters, i.e. dense subgraphs), and 3.0 in standard energy model of Fruchterman and Reingold. Must be greater than repuExponent.

gravFactor - factor for the gravitation energy. Gravitation attracts each node to the barycenter of all nodes, to prevent distances between unconnected graph components from approaching infinity. Typical values are 0.0 if the graph is guaranteed to be connected, and positive values significantly smaller 1.0 (e.g. 0.05) otherwise.

Method Detail

minimizeEnergy

public void minimizeEnergy(java.util.Map<Node,double[]> positions,
                           int nrIterations)

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

Parameters:

positions - position in 3D space for each node. Is not copied and serves as input and output parameter. Each position must be a double[3]. If the input is two-dimensional (i.e. the third array element is 0.0 for all nodes), the output is also two-dimensional. Different nodes with nonzero weights must have different positions. Random initial positions are appropriate.

nrIterations - number of iterations. Choose appropriate values by observing the convergence of energy. A typical value is 100.