annealinglayoutalgorithm.java

用JGraph编的软件

/******************************************************************************/
/**
 * Performs one round, so thats the main part of the Algorithm.
 * Different to the original Implementation of the Algorithm, this Algorithm
 * doesn't work with aproximativ 30 random Placements per Cell to find the best
 * Position. This Algorithm works with a user defined number of segments. The
 * Circle, the Cells will be placed on, is calculated like the original
 * Implementation tells. But it is splited into a user defined number of
 * segments. Then per cell a random offset is calculated and starting from
 * that offset every segment is checked out, whether there is a better position
 * for the cell. This can be done in a random order of the cells or always in
 * the same order. Temperature is decreased after all cells are checked out
 * for a new position, like in the original. While the original Implementation
 * allows always uphill moves, this Algorithm allows the user to decide to work
 * with or without them.
 * @return If the Algorithm is canceled while performing this method, the
 * method returns <code><b>true</b></code>. 
 */
    private boolean performRound(){
        
        Point2D.Double[] config = getConfig();
        
        double startEnergy      = getGlobalCosts(lambdaList);
        double globalEnergy     = startEnergy;
        double newGlobalEnergy  = globalEnergy * 1.1; //somewhat higher than globalEnergy

        //sequencial order cells are computed (every round the same order)
        int[] sequence = new int[applyCellList.size()];
        if( !computePermutation )
            for( int i = 0; i < applyCellList.size(); i++ )
                sequence[i] = i;
                
                
                
        for( int i = 0; i < applyCellList.size(); i++ ){        
            
            
            if( computePermutation )//random order
                sequence = createPermutation(applyCellList.size());
           
            //random offset
            double offset = Math.random() * 2.0 * Math.PI;
            
            for( int j = 0; j < triesPerCell; j++ ){
                
                double angle = (double)j * ((2.0 * Math.PI)/(double)triesPerCell);
                angle += offset;

                Point2D.Double move = null;                                
                //calculating new move 
                if( isCluster((CellView)applyCellList.get(i)) ){
                    move = new Point2D.Double(  
                        clusterMoveScaleFactor * temperature * Math.cos(angle),
                        clusterMoveScaleFactor * temperature * Math.sin(angle));
                }
                else {
                    move = new Point2D.Double( temperature * Math.cos(angle),
                                               temperature * Math.sin(angle));
                    
                }
//                Point2D.Double randomMove = getRandomVector(temperature);

                //applying new move
                setPosition(sequence[i],config[sequence[i]].x + move.x,
                                        config[sequence[i]].y + move.y);
            
                //calculating the costs for the actual layout
                newGlobalEnergy = getGlobalCosts(lambdaList);
            
                //taking move if costs < previos cost or uphill move possible
                if( newGlobalEnergy < globalEnergy ||
                    (getBolzmanBreak(globalEnergy,newGlobalEnergy) && 
                     uphillMovesAllowed) ){
                
//                    if( isDebugging )
//                        System.out.println("taking new energy : "+globalEnergy+" -> "+newGlobalEnergy+" <<<<<<<<<<<<<<<<<<<<<<<<<");
                
                    globalEnergy = newGlobalEnergy;
                    
                    config[sequence[i]] = new Point2D.Double(
                                                config[sequence[i]].x + move.x,
                                                config[sequence[i]].y + move.y);
                                       
//                    if( isDebugging )         
//                        showApplyCellList();
                
                    break;
                }
                else {
//                    if( isDebugging )
//                        System.out.println("energy = "+globalEnergy+"   new Global Energy = "+newGlobalEnergy+"   temperature = "+temperature);
                    setPosition(sequence[i],
                                config[sequence[i]].x,
                                config[sequence[i]].y);
                }
                   
                //progressdialog update
                dlgProgress.setValue(initProgressValue+(int)(((double)((round*applyCellList.size()*triesPerCell)+(i*triesPerCell)+j)/(double)(maxRounds*applyCellList.size()*triesPerCell))*(100.0-initProgressValue)));
                if( dlgProgress.isCanceled() )
                    break;
            }
            
            //if this rounds runs very good and energy is 5% of starting value
            //then break this round and start next round
            if( globalEnergy == startEnergy * 0.05 )
                break;
            //if cancel is pressed
            if( dlgProgress.isCanceled() )
                break;
        }
        //temperature will be decreased
        temperature *= tempScaleFactor;
        
        round++;//rounds are counted
        
        return dlgProgress.isCanceled();
    }

/******************************************************************************/
/**
 * Extracts the Positions of all cells into a array of Positions.
 * @return Array that represents the Positions of the Cells in 
 * {@link #applyCellList}.
 */
    private Point2D.Double[] getConfig(){
        Point2D.Double[] config = new Point2D.Double[applyCellList.size()];
        for( int i = 0; i < applyCellList.size(); i++ ){
            Point2D.Double pos = getPosition((CellView)applyCellList.get(i));
            config[i] = new Point2D.Double(pos.x,pos.y);
        }
        return config;
    }

/******************************************************************************/
/**
 * Calculates the costs of the actual graph by using costfunctions.
 * @param lambda Normalizing and priority values for the costfunctions
 * @return costs for the actual graph
 * @see #costFunctionConfig
 * @see #getBorderline(double)
 * @see #getEdgeCrossing(double)
 * @see #getEdgeDistance(double)
 * @see #getEdgeLength(double)
 * @see #getNodeDistance(double)
 * @see #getNodeDistribution(double)
 */
    private double getGlobalCosts(double[] lambda){
        
        //assert lambda.length != AnnealingLayoutController.COUT_COSTFUNCTION;
        
//        long startTime = System.currentTimeMillis();
        
        double energy = 0.0;
        
        if( (costFunctionConfig & AnnealingLayoutController.COSTFUNCTION_NODE_DISTANCE) != 0 ){
            energy += getNodeDistance(lambda[5]);
        }
        if( (costFunctionConfig & AnnealingLayoutController.COSTFUNCTION_NODE_DISTRIBUTION) != 0 ){
            energy += getNodeDistribution(lambda[0]);
        }
        if( (costFunctionConfig & AnnealingLayoutController.COSTFUNCTION_BORDERLINE) != 0 ){
            energy += getBorderline(lambda[1]);
        }
        if( (costFunctionConfig & AnnealingLayoutController.COSTFUNCTION_EDGE_LENGTH) != 0 ){  
            energy += getEdgeLength(lambda[2]);
        }
        if( (costFunctionConfig & AnnealingLayoutController.COSTFUNCTION_EDGE_CROSSING) != 0 ){
            energy += getEdgeCrossing(1.0,lambda[3]);
        }
        if( (costFunctionConfig & AnnealingLayoutController.COSTFUNCTION_EDGE_DISTANCE) != 0 ){
            energy += getEdgeDistance(lambda[4]);
        }
        
        energy += getAdditionalCosts(costFunctionConfig,lambda);
        
//        time += System.currentTimeMillis()-startTime;    
                    
        return energy;
    }
        
/******************************************************************************/
/**
 * Method for classes that extends this Algorithm. Calls the Costfunctions of
 * the extending class.
 * @return costs generated with the additional costfunctions
 * @see #getGlobalCosts(double[])
 */
    protected double getAdditionalCosts(int cfConfig, double[] lambda){
        return 0.0;
    }

/******************************************************************************/
/**
 * Creates a permutation of the Numbers from 0 to a determined value.
 * @param length Number of Numbers and maximal distance to 0 for the Numbers
 * filling the permutation
 * @return Permutation of the Numbers between 0 and <code>length</code>
 */

    public int[] createPermutation(int length){
        int[] permutation = new int[length];
        for( int i = 0; i < permutation.length; i++ ){
            int newValue = (int)(Math.random()*(double)length);
            for( int j = 0; j < i; j++ )
                if( newValue == permutation[j] ){
                    newValue = (int)(Math.random()*(double)length);
                    j = -1; // wird auf 0 zur點kgesetzt
                }
            permutation[i] = newValue;
        }        
        return permutation;
    }

/******************************************************************************/
/**
 * Calculates a break condition for {@link #performRound()} if uphill moves
 * are allowed. This is computed by a formular from Bolzman:<p>
 * <blockquote><blockquote><code>
 * random < e^(oldEnergy-newEnergy)
 * </code></blockquote></blockquote>
 * @param oldEnergy The Energy before the Energy has increased, so it's the 
 * lower one, of the two values.
 * @param newEnergy The Energy after the Energy has increased, so it's the
 * higher one, of the two values
 * @return sometimes <code><b>true</b></code> when the random number is
 * smaler than <code>e^(oldEnergy-newEnergy)</code>
 */
    private boolean getBolzmanBreak(double oldEnergy, double newEnergy){
        return Math.random() < Math.pow(Math.E,(oldEnergy-newEnergy)/temperature);
    }
    
/******************************************************************************/
/**
 * Calculates the maximal number of rounds, by flattening the actual 
 * {@link #temperature} with the temperature scaling factor 
 * {@link #tempScaleFactor}
 * 
 * @param actualTemperature The Temperature of the actual Graph
 * @return The number of Rounds that have to be performed until 
 * {@link #temperature} falls under {@link #minTemperature}.
 */
    private int getMaxRoundsByTemperature(double actualTemperature){
        return (int)Math.ceil( Math.log(minTemperature/actualTemperature) /
                                Math.log(tempScaleFactor));
    }
    
/******************************************************************************/
/**
 * Costfunction. One criterion for drawing a "nice" graph is to spread the cells
 * out evenly on the drawing space. The distances between the cells need not to 
 * be perfectly uniform, but the graph sould be occupy a reasonable part of
 * the drawing space, and, if possible, the cells shouldn't be overcrowded.
 * This function calculates the sum, over all pairs of cells, of a function
 * that is inverse-proportional to the distance between the cells.
 * 
 * @param lambda A normalizing factor that defines the relativ importance of
 * this criterion compared to others. Increasing lambda relative to the other
 * normalizing factors causes the Algorithm to prefer pictures with smaller 
 * distances between cells.
 * @return costs of this criterion
 */
    private double getNodeDistribution(double lambda){
        double energy = 0.0;
        
        for( int i = 0 ; i < applyCellList.size(); i++ )
            for( int j = 0; j < cellList.size(); j++ ){

                if( applyCellList.get(i) != cellList.get(j) ){
                    double distance = MathExtensions.getEuclideanDistance(
                                    getPosition((CellView)applyCellList.get(i)),
                                    getPosition((CellView)cellList.get(j)));
                                    
                    //prevents from dividing with Zero
                    if( Math.abs(distance) < equalsNull )
                        distance = equalsNull;
            
                    energy += lambda/(distance*distance);
                }
            }
//        System.out.println("NodeDistribution : "+energy);
        return energy;
    }
    
/******************************************************************************/
/**
 * Costfunction. As in physics, truly minimizing the potential energy might
 * result in spreading out the elements indefinitely. To avoid this, and to 
 * reflect the physical limitations of the output device, add this costfunction
 * to the energy function to deal with the borderlines of the drawing space.
 * 
 * @param Increasing lambda relativ to the other lamdas pushes the cells 
 * towards the center, while decreasing it results in using more of the
 * drawing space near the borderlines. 
 * @return costs of this criterion
 */
    private double getBorderline(double lambda){
        double energy = 0.0;
        for( int i = 0; i < applyCellList.size(); i++ ){
            Point2D.Double pos = getPosition((CellView)applyCellList.get(i));
            double t = pos.y-bounds.y;
            double l = pos.x-bounds.x;
            double b = bounds.y+bounds.height-pos.y;
            double r = bounds.x+bounds.width -pos.x;