springembedder.java

图像检索的代码b

package at.lux.grapviz;

import java.util.*;

/*
 * This file is part of Caliph & Emir.
 *
 * Caliph & Emir is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Caliph & Emir is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Caliph & Emir; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Copyright statement:
 * --------------------
 * (c) 2002-2004 by Mathias Lux ([e-mail]) and the Know-Center Graz
 * Inffeldgasse 21a, 8010 Graz, Austria
 * http://www.know-center.at
 */

/**
 * Date: 14.09.2004
 * Time: 21:05:09
 *
 * @author Mathias Lux, [e-mail]
 */
public class SpringEmbedder {
    HashMap<Node, HashSet<Node>> node2nodes;
    List<Node> nodeList;
    List<Edge> edgeList;

    // -----------------------------------------------
    // Parameters
    // -----------------------------------------------
    // force function params
    private double c1, c2, c3, c4;
    // when to stop:
    private double stopCondition = 0.00005;
    // or maximum steps:
    private int maxSteps = 5000;
    // with additional steps for finetuning:
    private int additionalSteps = 25;
    // has attracting force in the center
    private boolean hasInvisibleCenterNode = true;
    private boolean edgesRepelNodes = false;

    // -----------------------------------------------
    // internal fields for calculation
    // -----------------------------------------------
    private int countSteps, additionalStepCountdown;
    private double overallMovement;

    public SpringEmbedder(List<Node> nodeList, List<Edge> edgeList) {
        this.nodeList = nodeList;
        this.edgeList = edgeList;
        overallMovement = Double.MAX_VALUE;
        additionalStepCountdown = additionalSteps;
        countSteps = 0;
        init();
    }

    private void init() {
        // init params:
        c1 = 2.0;
        c2 = 1.0;
        c3 = 1.0;
        c4 = 0.1;

        countSteps = 0;

        // init lookup:
        node2nodes = new HashMap<Node, HashSet<Node>>(nodeList.size());
        for (Iterator<? extends Node> iterator = nodeList.iterator(); iterator.hasNext();) {
            node2nodes.put(iterator.next(), new HashSet<Node>());
        }
        for (Iterator<Edge> iterator = edgeList.iterator(); iterator.hasNext();) {
            Edge e = iterator.next();
            node2nodes.get(e.getStartNode()).add(e.getEndNode());
            node2nodes.get(e.getEndNode()).add(e.getStartNode());
        }
    }

    private HashMap<Node, Vector2D> calculateForces() {
        HashMap<Node, Vector2D> result = new HashMap<Node, Vector2D>(nodeList.size());
        overallMovement = 0.0;
        for (Iterator<Node> iterator = nodeList.iterator(); iterator.hasNext();) {
            double force = 0.0;
            Node nodeA = iterator.next();
            Vector2D f = new Vector2D(0.0, 0.0);

            DefaultNode centerNode = new DefaultNode(0.0, 0.0);

            if (hasInvisibleCenterNode) {
                // attracting force from center ...
                double v = (nodeA.distance(centerNode) / c2);
                force =  v * v;
                Vector2D toCenter = nodeA.direction(centerNode);
                toCenter.normalize();
                toCenter.multiply(force);
                f.addVector2D(toCenter);
            }

            if (edgesRepelNodes) {
                List<Node> border = new LinkedList<Node>();
                border.add(new DefaultNode(0.0, nodeA.getY()));
                border.add(new DefaultNode(1.0, nodeA.getY()));
                border.add(new DefaultNode(nodeA.getX(), 0.0));
                border.add(new DefaultNode(nodeA.getX(), 1.0));

                for (Iterator<Node> itBorder = border.iterator(); itBorder.hasNext();) {
                    Node nodeB = itBorder.next();
                    force = 0.0;
                    // these two nodes repel each other
                    force = - c3 / Math.sqrt(nodeA.distance(nodeB));
                    Vector2D vector = nodeA.direction(centerNode);
                    vector.normalize();
                    vector.multiply(force);
                    f.addVector2D(vector);
                }
            }

            for (Iterator<Node> it1 = nodeList.iterator(); it1.hasNext();) {
                Node nodeB = it1.next();
                if (!nodeA.equals(nodeB)) {
                    force = 0.0;
                    if (node2nodes.get(nodeA).contains(nodeB)) {
                        // these two nodes attract each other
                        force = c1 * Math.log(nodeA.distance(nodeB) / c2);
                    } else {
                        // these two nodes repel each other
                        force = -c3 / Math.sqrt(nodeA.distance(nodeB));
                    }
                    Vector2D vector = nodeA.direction(nodeB);
                    vector.normalize();
                    vector.multiply(force);
                    f.addVector2D(vector);
                }
            }
//            f.normalize();
            // here goes the step into the right direction:
            f.multiply(c4);
            overallMovement += f.getLength();
            result.put(nodeA, f);
        }
//        System.out.println(overallMovement);
        return result;
    }

    private void moveVertices(HashMap<Node, Vector2D> forces) {
        for (Iterator<Node> iterator = forces.keySet().iterator(); iterator.hasNext();) {
            Node node = iterator.next();
            node.move(forces.get(node));
        }
    }

    public int step() {
        double lastMovement = overallMovement;
        moveVertices(calculateForces());
//        scaleDown();
        countSteps++;
        // stop when movement is small enough, there are additional steps for
        // for hopping over local minima
        if (Math.abs(overallMovement-lastMovement) < stopCondition) {
            additionalStepCountdown--;
        } else {
            additionalStepCountdown = additionalSteps;
        }
        if ( additionalStepCountdown<0  || countSteps > maxSteps ) return -1;
        return countSteps;
    }

    private void scaleDown() {
        double xMin = 1.0, xMax = 0.0, yMin = 1.0, yMax = 0.0;
        for (Iterator<Node> iterator = nodeList.iterator(); iterator.hasNext();) {
            Node node = iterator.next();
            if (node.getX() < xMin) xMin = node.getX();
            if (node.getX() > xMax) xMax = node.getX();
            if (node.getY() < yMin) yMin = node.getY();
            if (node.getY() > yMax) yMax = node.getY();
        }
        for (Iterator<Node> iterator = nodeList.iterator(); iterator.hasNext();) {
            Node node = iterator.next();
            node.setX((node.getX() - xMin) / (xMax - xMin));
            node.setY((node.getY() - yMin) / (yMax - yMin));
            assert(node.getX() >= 0.0);
            assert(node.getX() <= 1.0);
            assert(node.getY() >= 0.0);
            assert(node.getY() <= 1.0);
        }
    }

    public List<Node> getNodeList() {
        return nodeList;
    }

    public List<Edge> getEdgeList() {
        return edgeList;
    }
}