annealinglayoutalgorithm.java

用JGraph编的软件

package org.jgraph.layout;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Frame;
import java.awt.Rectangle;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
import java.util.Properties;

import org.jgraph.JGraph;
import org.jgraph.event.GraphModelEvent;
import org.jgraph.event.GraphModelListener;
import org.jgraph.graph.CellMapper;
import org.jgraph.graph.CellView;
import org.jgraph.graph.EdgeView;
import org.jgraph.graph.GraphConstants;
import org.jgraph.graph.GraphModel;
import org.jgraph.graph.VertexView;
import org.jgraph.utils.MathExtensions;


/**
 * <h1>Simulated Annealing Layout Algorithm</h1><p>
 * Implemented from the paper: "Drawing Graphs Nicely Using Simulated Annealing"
 * from Ron Davidson and David Harel. ACM Transactions on Graphics, Vol. 15, 
 * No. 4, October 1996, Pages 301-331.
 * @author winkler
 * @version 1.0
 * Date of creation: 11.04.2003 - 12:39:58
 */
public class AnnealingLayoutAlgorithm implements LayoutAlgorithm, GraphModelListener {

    public final static String KEY_CAPTION   = "Annealing Layoutalgorithm Attributes";    
    public final static String KEY_POSITION  = "Position";
    public final static String KEY_RELATIVES = "Relatives";
    
    public final static String CF_KEY_EDGE_DISTANCE_RELEVANT_EDGES = "costfunction edge distance key for relevant edges";
    
    /**
     * Key used only with clusters. Under this key a cluster has an ArrayList.
     * This list is filled with the clustered vertices.
     * @see #clusterGraph()
     * @see #moveVerticeToCluster(CellView,CellView)
     */
    public final static String KEY_CLUSTERED_VERTICES = "Clustered Vertices";
    /**
     * Key used only with clusters. Under this key vertices have the cluster
     * they belong to.
     * @see #clusterGraph()
     * @see #moveVerticeToCluster(CellView,CellView)
     */
    public final static String KEY_CLUSTER            = "Cluster";
    /**
     * Key used only with clusters. Under this key a cluster has a boolean value
     * indicating that this vertice is a cluster (clusters are 
     * VertexView-instances like every other cell).
     * @see #clusterGraph() 
     * @see #isCluster()
     */
    public final static String KEY_IS_CLUSTER         = "is Cluster";
    /**
     * Key used only with clusters. Under this key every cluster has a position,
     * which represents the position of the cluster, right after the clustering
     * process. After the layout update process is finished, the move, resulting
     * of subtracting the position under {@link #KEY_POSITION} from the 
     * position under this value, will be performed to all vertices in the 
     * cluster. By holding the initial position here clustering becomes 
     * possible.
     * 
     * @see #clusterGraph()
     * @see #declusterGraph()
     */
    public final static String KEY_CLUSTER_INIT_POSITION = "initial Position of the Cluster";
    
    /**
     * Key for loading configuration values. Indicates to load values for a
     * normal run.
     */
    protected final static int CONFIG_KEY_RUN           = 0;
    /**
     * Key for loading configuration values. Indicates to load values for a
     * layout update.
     */
    protected final static int CONFIG_KEY_LAYOUT_UPDATE = 1;

    /**
     * actual temperature
     */
    private double    temperature;
    /**
     * starting temperature
     */
    private double    initTemperature;
    /**
     * when {@link #temperature} reaches this value, the algorithm finishes its
     * calculation.
     */
    private double    minTemperature;
    /**
     * value for costfunctions {@link #getNodeDistribution()} and
     * {@link #getEdgeDistribution()}. Determines, how long the edges have to
     * be.
     */
    private double    minDistance;
    /**
     * {@link #temperature} will be multiplied with this value every round
     */
    private double    tempScaleFactor;
    /**
     * maximum number of rounds, if algorithm doesn't stop earlier, by 
     * temperature decreasement.
     */
    private int        maxRounds;
    /**
     * normalizing and priority factors for the costfunctions
     */
    protected double[]  lambdaList;
    /**
     * the drawing area, the graph should be layouted in.
     */
    private Rectangle bounds;
    /**
     * determines, if the cells of the graph are computed every time in the
     * same order or a random order, calculated every round.
     */
    private boolean   computePermutation;
    /**
     * determines, if the only allowed moves for cells of the graph are moves, 
     * that cost less. 
     */
    private boolean   uphillMovesAllowed;
    /**
     * Indicates, if the algorithm should also run on Updates in the graph.
     */
    private boolean   isLayoutUpdateEnabled;
    
    /**
     * Indicates what costfunctions to use for calculating the costs of the 
     * graph. The bits of this Integer switches the functions. Possible Values
     * are <br>
     * <blockquote><blockquote>
     * {@link AnnealingLayoutAlgorithm#COSTFUNCTION_NODE_DISTRIBUTION 
     * COSTFUNCTION_NODE_DISTRIBUTION}<br>
     * {@link AnnealingLayoutAlgorithm#COSTFUNCTION_NODE_DISTANCE
     * COSTFUNCTION_NODE_DISTANCE}<br>
     * {@link AnnealingLayoutAlgorithm#COSTFUNCTION_BORDERLINE
     * COSTFUNCTION_BORDERLINE}<br>
     * {@link AnnealingLayoutAlgorithm#COSTFUNCTION_EDGE_DISTANCE
     * COSTFUNCTION_EDGE_DISTANCE}<br>
     * {@link AnnealingLayoutAlgorithm#COSTFUNCTION_EDGE_CROSSING
     * COSTFUNCTION_EDGE_CROSSING}<br>
     * {@link AnnealingLayoutAlgorithm#COSTFUNCTION_EDGE_DISTRIBUTION
     * COSTFUNCTION_EDGE_DISTRIBUTION}
     * </blockquote></blockquote>
     */
    private int       costFunctionConfig;
    
    /**
     * counts the rounds 
     */
    private int       round;
    /**
     * determines, in how many segments the circle around cells is divided,
     * to find a new position for the cell.
     */
    private int       triesPerCell;
    
    /**
     * the list of all cells of the graph
     */
    protected ArrayList cellList;
    /**
     * the list of all edges of the graph
     */
    protected ArrayList edgeList;
    /**
     * the list of all cells, a new layout should be calculated for
     */
    protected ArrayList applyCellList;
    
    /**
     * the JGraph
     */
    private JGraph    jgraph;
    
    /**
     * if this algorithm is a optimizing algorithm, this value indicates the
     * offset for the progress dialog, else it is 0
     */
    private int       initProgressValue = 0;
    
    /**
     * holds the configuration of the algorithm, gained by the controller
     */
    protected Properties presetConfig;
    
    /**
     * for debugging purpose. 
     */
    private long      time = 0;

    /**
     * the progress dialog
     */
    private ProgressDialog dlgProgress =
        new ProgressDialog((Frame) null, "Progress:", false);
        
    /**
     * for debugging purpose
     */
    private boolean isDebugging = false;
    /**
     * indicates if the algorihm is performing a calculation. this prevents from
     * entering the method {@link #graphChanged(GraphModelEvent) 
     * graphChanged(...)} more than once at a time.
     */
    private boolean isRunning   = false;
        
        
    /**
     * the number of edges, neighbors of inserted cells are away,
     * to be also layouted again.
     */   
    private int       luRecursionDepth;
    /**
     * if a cell has a lower distance to a inserted cell, after the cell gained 
     * its initial position, it will be layouted too
     */
    private double    luPerimeterRadius;
    /**
     * if more than one cell is inserted and the initial position of other 
     * inserted cells is inside {@link #luPerimeterRadius} around a initial
     * position of a inserted cell, than {@link #luPerimeterRadius} will be
     * increased by this value.
     */
    private double    luPerimeterRadiusInc;
    /**
     * determines how the neighborhood is handled, when a layout update
     * should be performed. Possible values are:<p>
     * <blockquote><blockquote>
     * {@link AnnealingLayoutController#KEY_LAYOUT_UPDATE_METHOD_NEIGHBORS_ONLY
     * KEY_LAYOUT_UPDATE_METHOD_NEIGHBORS_ONLY}<br>
     * {@link AnnealingLayoutController#KEY_LAYOUT_UPDATE_METHOD_PERIMETER
     * KEY_LAYOUT_UPDATE_METHOD_PERIMETER}<br>
     * </blockquote></blockquote>
     */
    private String    luMethod;
    
    /**
     * prevents from dividing with zero and from creating to high costs
     */
    private double equalsNull = 0.05;
    
    /**
     * Switches clustering for the layout update process on/off
     */
    private boolean         isClusteringEnabled;
    
    /**
     * Scales movement of clusters. It is recommendet to take
     * a value between 1.0 and 0.0. This garanties, that clusters move slower
     * than other cells. That rises the chance of getting a good looking layout
     * after the calculation.
     */
    private double          clusterMoveScaleFactor;
    
    /**
     * Effects, how many clusters are created, when the layout update process
     * starts. This affects the initial number of clusters, which is the number
     * of cells available minus the number of cells to layout. The result of
     * that term is divided by this factor, to get the maximum number of 
     * clusters. After this calculation, the clustering algorithm tries to
     * minimize the number of clusters, so there might be less clusters than 
     * the maximum number.
     */
    private double          clusteringFactor;

/******************************************************************************/
	/**
	 * Constructor for SimulatedAnnealingAlgorithm.
	 */
	public AnnealingLayoutAlgorithm() {
	}

/******************************************************************************/
	/**
     * Runs the Algorithm
	 * @see org.jgraph.layout.LayoutAlgorithm#perform(JGraph, boolean, Properties)
	 */
	public void perform(
		JGraph graph,
		boolean applyToAll,
		Properties configuration) {
            
        isRunning = true;
            
//        System.out.println("now running Simulated Annealing");