gemlayoutalgorithm.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.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>GEM Layout Algorithm</h1>
 * <p>
 * Based on the work of Arne Frick, Andreas Ludwig, Heiko Mehldau: 
 * "A Fast Adaptive Layout Algorithm for Undirected Graphs"; 
 * Extended Abstract and System Demonstration; Faculty of Informatik of 
 * the University Karlsruhe; 1994
 * <p>
 * This Algorithm works by giving every cell a position and a temperature.
 * Then for every cell forces are computed. Every other cell repulses the
 * actual calculated cell away. On the other hand, cells, connected by edges
 * are attracted, until a minimum distance is reached. The result of this 
 * forces is a move of the position of the actual cell in the direction of
 * the force and with the length of the temperature. Then the temperature
 * will be decreased, if the last impulse and the current impulse looks like a
 * rotation or a oscillation. this is done for every cell until the temperature
 * of all cells or the average of the temperature of every cell is until a
 * given minimum value or a maximum of rounds is reached.
 * @author winkler
 */

public class GEMLayoutAlgorithm implements LayoutAlgorithm, GraphModelListener {
    
    /**
     * Key used on every cell. This key indicates that in the cell are 
     * attributes stored by this algorithm. The algorithm itself never asks for
     * this key. This is for others developers only, using this algorithm, to
     * find out, where sometimes approaching attributes come from.
     */     
    public final static String KEY_CAPTION         = "GEM-TEMPORARY-DATA";
    
    /**
     * Key used on every cell. Under this key every cell stores temporary the
     * temperature of itself. Temperature is a indicator how far a cell can move
     * and all temperatures together indicating how long the algorithm will run.
     */
    public final static String KEY_TEMPERATURE     = "Temperature";
    
    /**
     * Key used on every cell. Under this key every cell stores temporary the
     * current force impulse affecting the cell.
     */
    public final static String KEY_CURRENT_IMPULSE = "Current_Impulse";
    
    /**
     * Key used on every cell. Under this key every cell stores temporary the
     * last impulse. This is the value of the previous 
     * {@link #KEY_CURRENT_IMPULSE}.
     */
    public final static String KEY_LAST_IMPULSE    = "Last_Impulse";
    
    /**
     * Key used on every cell. Under this key every cell stores the temporary  
     * position on the display, while the calculation is running. This makes
     * the algorithm faster, than asking the Cell everytime for its position.
     * So the algorithm can anytime be canceled, whithout changing something. 
     */
    public final static String KEY_POSITION        = "Position";

    /**
     * Key used on every cell. Under this key every cell stores the temporary
     * skew gauge. This value is for punish rotations of the cells.
     */    
    public final static String KEY_SKEWGAUGE       = "Skew_Gauge";
    
    /**
     * Key used on every Cell. Under this key every cell stores the cells,
     * that are only one edge away from it. The relatives are stored, after the
     * first time, they are desired and calculated by 
     * {@link #getRelatives(CellView)}.
     */
    public final static String KEY_RELATIVES       = "Relatives";
    
    /**
     * Key used on every Cell. This indicates a weight for the number of edges
     * received by {@link #getNodeWeight(CellView)}
     */
    public final static String KEY_MASSINDEX       = "Mass_Index";
    
    /**
     * 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";
    
    
    /** 
     * List of all nodes in the graph.
     */
    private ArrayList  cellList; 
    
    /** 
     * List of all nodes the algorithm should be done for. 
     */
    private ArrayList  applyCellList;
    
    /** 
     * List of all edges in the graph. This is only needed for the optimization
     * Algorithm.
     */
    private ArrayList  edgeList;
    
    
    /** 
     * needed for comperation with other double values if they are 0.0.
     */
    private double equalsNull = 0.00000000000000001;

    /** 
     * starting value for the temperatures of the cells 
     */
    private double initTemperature;
    
    /** 
     * if the temperature of all cells or the average of the temperatures of 
     * all cells is below this value, the algorithm stops
     */
    private double minTemperature;
    
    /** 
     * temperature will never be over this value 
     */
    private double maxTemperature;
    
    /** 
     * the length of the Edges in Pixel, the algorithm tries to keep
     */
    private double prefEdgeLength;
    
    /** 
     * the strength of the gravitation force, directed to the barycenter of the
     * graph, added to all cells. 
     */
    private double gravitation;
    
    /** 
     * length of a force vector with a random direction, added to all cells. 
     */
    private double randomImpulseRange;
    
    /** 
     * opening angle in radiant, that detects oscillations 
     */
    private double alphaOsc;
     
    /** 
     * opening angle in radiant, that detects rotations 
     */
    private double alphaRot;
     
    /** 
     * penalty value for a detected oscillation
     */
    private double sigmaOsc; 
    
    /** 
     * penalty value for a detected rotation 
     */
    private double sigmaRot; 
        
    /**
     * number of rounds until the algorithm will break. This value is 
     * precalculated to a aproximativ value of 4 times the count of Cells in
     * {@link #applyCellList}
     */
    private int    maxRounds;
    
    /**
     * counts the rounds
     */
    private int    countRounds;
    
    /**
     * If the pathlength between an inserted cell and an allready layouted cell
     * is below this value, the allready layouted cell will be layouted again.
     */
    private int    recursionDepth;
    
    /**
     * Describes the distance around a cell, that will be whatched for other
     * cells, intersecting this area. If another cell intersects, a force will
     * be added to the cell, that pushes it away.
     */
    private double overlapDetectWidth;
    
    /**
     * Describes a distance the algorithm tries to keep, when he detects a 
     * overlapping cell. 
     */
    private double overlapPrefDistance;
    
    /**
     * switches the feature to whatch for overlapping on/off
     */
    private boolean avoidOverlapping;
    
    /**
     * describes, what method will be taken, when cells are inserted. Posible
     * values are 
     * {@link GEMLayoutAlgorithm#KEY_LAYOUT_UPDATE_METHOD_NEIGHBORS_ONLY 
     * KEY_LAYOUT_UPDATE_METHOD_NEIGHBORS_ONLY} and
     * {@link GEMLayoutAlgorithm#KEY_LAYOUT_UPDATE_METHOD_PERIMETERS 
     * KEY_LAYOUT_UPDATE_METHOD_PERIMETERS}.
     */
    private String layoutUpdateMethod;

    /**
     * condition for method isFrozen(). decides whether the method returns true
     * when the average of all temperatures or all temperatures are below 
     * {@link #minTemperature}. 
     */
    private boolean shouldEndPerAverage;
    /**
     * condition for the method calculate(). decides whether the algorithm
     * is computed for the cellViews every time in the same sequence
     * or if the cellViews are computed every time in a random sequence.
     */
    private boolean shouldComputePermutation;

    /**
     * Switches the skill of the algorithm to perform the layout update process
     */    
    private boolean isActive  = true;
    
    /**
     * Checks if the algorithm is currently running. If this is the case, no
     * GraphModelEvent will be computed and no new run can be initiated.
     */
    private boolean isRunning = false;
    
    /**
     * a reference to the instance of jgraph
     */
    private JGraph   jgraph;
    
    /**
     * the configuration of this algorithm
     */
    protected Properties config;

    /*
     * shows the progress in performing the algorithm on the graphcells
     */    
    private ProgressDialog dlgProgress =
        new ProgressDialog((Frame) null, "Progress:", false);
        
    /* 
     * to determine a somehow correct percentage value for the progress dialog
     */
    private int[] phaseLength = new int[] { 2, 80, 100};//phase i goes up to
    
    /*
     * to detemine a correct labeled progress dialog
     */
    private String[] phaseName = new String[] { "initialization", 
                                               "performing calculation",