minimizerbarneshut.java

用能量函数布局网络图

		if (dist == 0.0) return 0.0;

		double tmp =   repuFactor * node.weight * tree.weight 
				     * Math.pow(dist, repuExponent-2);
		for (int d = 0; d < nrDims; d++) {
			dir[d] -= (tree.position[d] - position[d]) * tmp;
		}
		return tmp * Math.abs(repuExponent-1);
	}

	/**
	 * Computes the direction of the attraction force on the a node.
	 * @param  node  attracting node
	 * @param  dir   direction of the attraction force acting on the node
	 * 				 is added to this variable (output parameter)
	 * @return approximate second derivation of the attraction energy
	 */
	private double addAttractionDir(final Node node, final double[] dir) {
		double dir2 = 0.0;
        final double[] position = positions.get(node);
		for (Edge edge : attrEdges.get(node)) {
            final double[] position2 = positions.get(edge.endNode);
			final double dist = getDist(position, position2);
			if (dist == 0.0) continue;
			double tmp = edge.weight * Math.pow(dist, attrExponent-2);
			dir2 += tmp * Math.abs(attrExponent-1);
			for (int d = 0; d < nrDims; d++) {
				dir[d] += (position2[d] - position[d]) * tmp;
			}
		}
		return dir2;
	}

	/**
	 * Computes the direction of the gravitation force on the a node.
	 * @param  node  gravitating node
	 * @param  dir   direction of the gravitation force acting on the node
	 * 				 is added to this variable (output parameter)
	 * @return approximate second derivation of the gravitation energy
	 */
	private double addGravitationDir(final Node node, final double[] dir) {
        final double[] position = positions.get(node);
        final double dist = getDist(position, baryCenter);
		double tmp = gravFactor * repuFactor * node.weight * Math.pow(dist, attrExponent-2);
        for (int d = 0; d < nrDims; d++) {
            dir[d] += (baryCenter[d] - position[d]) * tmp;
        }
		return tmp * Math.abs(attrExponent-1);
	}
		
	/**
	 * Computes the direction of the total force acting on a node.
	 * @param  node  node
	 * @param  dir   direction of the total force acting on the node
	 *               (output parameter)
	 */
    private void getDirection(final Node node, final OctTree octTree, final double[] dir) {
        for (int d=0; d<nrDims; d++) dir[d] = 0.0;

		double dir2 = addRepulsionDir(node, octTree, dir);
		dir2 += addAttractionDir(node, dir);
		dir2 += addGravitationDir(node, dir);

		if (dir2 != 0.0) {
			// normalize force vector with second derivation of energy
            for (int d=0; d<nrDims; d++) dir[d] /= dir2;
         
			// ensure that the length of dir is not greater
			// than 1/16 of the octtree width,
            // to prevent the node from leaving the octtree region
            double scale = 1.0;
            for (int d = 0; d < nrDims; d++) {
                double width = octTree.maxPos[d] - octTree.minPos[d];
                if (width > 0.0) scale = Math.min(scale, Math.abs(width/16/dir[d]));
            }
            for (int d=0; d<nrDims; d++) dir[d] *= scale;
		} else {
            for (int d=0; d<nrDims; d++) dir[d] = 0.0;
		}
    }    


	/**
	 * Builds the octtree.
	 */
	private OctTree buildOctTree() {
		// compute mimima and maxima of positions in each dimension
		double[] minPos = { Double.MAX_VALUE, Double.MAX_VALUE, Double.MAX_VALUE };
		double[] maxPos = {-Double.MAX_VALUE,-Double.MAX_VALUE,-Double.MAX_VALUE };
		for (Node node : nodes) {
			if (node.weight == 0.0) continue;
            double[] position = positions.get(node);
			for (int d = 0; d < nrDims; d++) {
				minPos[d] = Math.min(position[d], minPos[d]);
				maxPos[d] = Math.max(position[d], maxPos[d]);
			}
		}
		// provide additional space for moving nodes
        for (int d = 0; d < nrDims; d++) {
            double posDiff = maxPos[d] - minPos[d];
            maxPos[d] += posDiff / 2;
            minPos[d] -= posDiff / 2;
        }
		
		// add nodes with non-zero weight to the octtree
		OctTree result = new OctTree(null, new double[nrDims], minPos, maxPos);
		for (Node node : nodes) result.addNode(node, positions.get(node), 0);
		return result;
	}

    /** 
     * Computes the position of the barycenter of all nodes
     * and stores it in the attribute <code>baryCenter</code>.
     */
    private void computeBaryCenter() {
        for (int d=0; d<nrDims; d++) baryCenter[d] = 0.0;
		double weightSum = 0.0;
        for (Node node : nodes) {
			weightSum += node.weight;
			double[] position = positions.get(node);
            for (int d=0; d<nrDims; d++) baryCenter[d] += node.weight * position[d];
        }
		if (weightSum > 0.0) {
            for (int d=0; d<nrDims; d++) baryCenter[d] /= weightSum;
		}
    }

	/**
	 * Computes and outputs some statistics. 
	 */
	private void printStatistics(final OctTree octTree) {
        System.out.println("Number of nodes: " + nodes.size());
		double attrSum = 0.0;
		for (Node node : nodes) {
			for (Edge edge : attrEdges.get(node)) {
				attrSum += edge.weight;
			}
		}
		System.out.println("Overall attraction: " + attrSum);
		double meanAttrEnergy = 0.0;
		for (Node node : nodes) meanAttrEnergy += getAttractionEnergy(node);
		meanAttrEnergy = (attrExponent == 0.0)
			? Math.exp(meanAttrEnergy / attrSum)
			: Math.pow(meanAttrEnergy * attrExponent / attrSum, 1.0 / attrExponent); 
		System.out.println("Weighted mean of attraction energy: " + meanAttrEnergy);
		
		double repuSum = 0.0, repuSquareSum = 0.0;
		for (Node node : nodes) {
			repuSum += node.weight;
			repuSquareSum += node.weight * node.weight;
		}
		repuSum = repuSum*repuSum - repuSquareSum;
		System.out.println("Overall repulsion: " + repuSum);
		double meanRepuEnergy = 0.0;
		for (Node node : nodes) meanRepuEnergy += getRepulsionEnergy(node, octTree);
		meanRepuEnergy /= repuFactor; 
		meanRepuEnergy = (repuExponent == 0.0) 
			? Math.exp(-meanRepuEnergy / repuSum)
			: Math.pow(-meanRepuEnergy * repuExponent / repuSum, 1.0 / repuExponent); 
		System.out.println("Weighted mean of repulsion energy: " + meanRepuEnergy);
		
		System.out.println("Mean attraction / mean repulsion: " + meanAttrEnergy / meanRepuEnergy);
	}


	/**
	 * Octtree for graph nodes with positions in 3D space.
	 * Contains all graph nodes that are located in a given cuboid in 3D space.
	 * 
	 * @author Andreas Noack
	 */
	static class OctTree {
        /** Maximum depth of tree nodes. */
        protected static final int MAX_DEPTH = 18;
		/** For leafs, the corresponding graph node; for non-leafs <code>null</code>. */
		protected Node node;
		/** Children of this tree node. */
		protected OctTree[] children = new OctTree[8];
        /** Number of children of this tree node. */
        protected int childCount = 0;
		/** Barycenter of the contained graph nodes. */
		protected double[] position;
		/** Total weight of the contained graph nodes. */
		protected double weight;
		/** Minimum coordinates of the cuboid in each of the 3 dimensions. */
		protected double[] minPos;
		/** Maximum coordinates of the cuboid in each of the 3 dimensions. */
		protected double[] maxPos;
		
		/**
		 * Creates an octtree containing exactly one graph node.
		 *  
		 * @param node     graph node
		 * @param position position of the graph node
		 * @param minPos   minimum coordinates of the cuboid
		 * @param maxPos   maximum coordinates of the cuboid
		 */
		public OctTree(Node node, double[] position, double[] minPos, double[] maxPos) {
			this.node = node;
			this.position = new double[] { position[0], position[1], position[2] };
			this.weight = node != null ? node.weight : 0.0;
			this.minPos = minPos;
			this.maxPos = maxPos;
		}
		
		/**
		 * Adds a graph node to the octtree.
		 * 
		 * @param newNode  graph node
		 * @param newPos   position of the graph node
		 * @param depth    depth of this tree node in the octtree
		 */
		public void addNode(Node newNode, double[] newPos, int depth) {
			if (newNode.weight == 0.0) return;

			if (node != null) {
				addNode2(node, position, depth);
				node = null;
			}

			for (int d = 0; d < 3; d++) {
				position[d] = (weight*position[d] + newNode.weight*newPos[d]) / (weight+newNode.weight);
			}
			weight += newNode.weight;
			
			addNode2(newNode, newPos, depth);
		}
		
		/**
		 * Adds a graph node to the octtree, 
		 * without changing the position and weight of the root.
		 * 
		 * @param newNode  graph node
		 * @param newPos   position of the graph node
		 * @param depth    depth of this tree node in the octtree
		 */
		protected void addNode2(Node newNode, double[] newPos, int depth) {
            if (depth == MAX_DEPTH) {
                if (children.length == childCount) {
                    OctTree[] oldChildren = children;
                    children = new OctTree[2*children.length];
                    System.arraycopy(oldChildren, 0, children, 0, oldChildren.length);
                }
                children[childCount++] = new OctTree(newNode, newPos, newPos, newPos);
                return;
            }
            
			int childIndex = 0;
			for (int d = 0; d < 3; d++) {
				if (newPos[d] > (minPos[d]+maxPos[d])/2) {
					childIndex += 1 << d;
				}
			}
			
			if (children[childIndex] == null) {
				double[] newMinPos = new double[3]; 			
				double[] newMaxPos = new double[3];
				for (int d = 0; d < 3; d++) {
					if ((childIndex & 1<<d) == 0) {
						newMinPos[d] = minPos[d];
						newMaxPos[d] = (minPos[d] + maxPos[d]) / 2;
					} else {
						newMinPos[d] = (minPos[d] + maxPos[d]) / 2;
						newMaxPos[d] = maxPos[d];
					}
				}
                
                childCount++;
				children[childIndex] = new OctTree(newNode, newPos, newMinPos, newMaxPos);
			} else {
				children[childIndex].addNode(newNode, newPos, depth+1);
			}
		}

		/**
		 * Removes a graph node from the octtree. 
		 * 
		 * @param oldNode  graph node
		 * @param oldPos   position of the graph node
		 * @param depth    current depth
		 */
        public void removeNode(Node oldNode, double[] oldPos, int depth) {
            if (oldNode.weight == 0.0) return;

            if (weight <= oldNode.weight) {
                weight = 0.0;
                node = null;
                for (int i = 0; i < children.length; i++) children[i] = null;
                childCount = 0;
                return;
            }
            
            for (int d = 0; d < 3; d++) {
                position[d] = (weight*position[d] - oldNode.weight*oldPos[d]) / (weight-oldNode.weight);
            }
            weight -= oldNode.weight;

            if (depth == MAX_DEPTH) {
                int childIndex = 0;
                while (children[childIndex].node != oldNode) childIndex++; 
                childCount--;
                for (int i = childIndex; i < childCount; i++) {
                    children[i] = children[i+1];
                }
                children[childCount] = null;
            } else {
                int childIndex = 0;
                for (int d = 0; d < 3; d++) {
                    if (oldPos[d] > (minPos[d]+maxPos[d])/2) {
                        childIndex += 1 << d;
                    }
                }
                children[childIndex].removeNode(oldNode, oldPos, depth+1);
                if (children[childIndex].weight == 0.0) {
                    children[childIndex] = null;
                    childCount--;
                }
            }
        }

        /**
		 * Returns the maximum extension of the octtree.
		 * 
		 * @return maximum over all dimensions of the extension of the octtree
		 */
		public double width() {
			double width = 0.0;
			for (int d = 0; d < 3; d++) {
				if (maxPos[d] - minPos[d] > width) {
					width = maxPos[d] - minPos[d];
				}
			}
			return width;
		}

        /**
         * Returns the height of the octtree.
         * 
         * @return height of the octtree
         */
        public int getHeight() {
            int height = -1;
            for (OctTree child : children) {
                if (child != null) { 
                    height = Math.max(height, child.getHeight());
                }
            }
            return height+1;
        }
	}

}