jcoverage | summary | package | file

Coverage details for edu.uci.ics.jung.visualization.contrib.KKLayoutInt

LineHitsSource
1 /*
2  * Copyright (c) 2003, the JUNG Project and the Regents of the University
3  * of California
4  * All rights reserved.
5  *
6  * This software is open-source under the BSD license; see either
7  * "license.txt" or
8  * http://jung.sourceforge.net/license.txt for a description.
9  */
10 package edu.uci.ics.jung.visualization.contrib;
11 /*
12  * This source is under the same license with JUNG.
13  * http://jung.sourceforge.net/license.txt for a description.
14  */
15 //package edu.uci.ics.jung.visualization;
16 //package org.ingrid.nexas.graph;
17  
18 import java.awt.Dimension;
19 import java.util.ConcurrentModificationException;
20 import java.util.Iterator;
21  
22 import edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath;
23 import edu.uci.ics.jung.graph.Graph;
24 import edu.uci.ics.jung.graph.Vertex;
25 import edu.uci.ics.jung.visualization.AbstractLayout;
26 import edu.uci.ics.jung.visualization.Coordinates;
27  
28 /**
29  * Implements the Kamada-Kawai algorithm for node layout, tweaked to store vertex distances as integers. Uses
30  * less memory than the classic KKLayout, but doesn't respect non-integer edge distances or lengths.
31  * Does not respect filter calls, and sometimes crashes when the view changes to it.
32  *
33  * @see "Tomihisa Kamada and Satoru Kawai: An algorithm for drawing general indirect graphs. Information Processing Letters 31(1):7-15, 1989"
34  * @see "Tomihisa Kamada: On visualization of abstract objects and relations. Ph.D. dissertation, Dept. of Information Science, Univ. of Tokyo, Dec. 1988."
35  *
36  * @author Masanori Harada
37  */
38 public class KKLayoutInt extends AbstractLayout {
39     //private static final Object KK_KEY = "KK_Visualization_Key";
40  
410    private float EPSILON = 0.1f;
42  
43     private int currentIteration;
440    private int maxIterations = 2000;
450    private String status = "KKLayoutInt";
46     //private Pair key;
47  
48     private int L; // the ideal length of an edge
49     private static final double K = 10000; // arbitrary const number
50     private int[] dm; // distance matrix
51  
520    private boolean adjustForGravity = true;
530    private boolean exchangeVertices = true;
54  
55     private Vertex[] vertices;
56     private Coordinates[] xydata;
57  
58     /**
59      * Stores graph distances between vertices of the visible graph
60      */
61     protected UnweightedShortestPath unweightedShortestPaths;
62  
63     /**
64      * The diameter of the visible graph. In other words, length of
65      * the longest shortest path between any two vertices of the visible graph.
66      */
67     protected int diameter;
68  
69     public KKLayoutInt(Graph g) {
700        super(g);
71         //key = new Pair(this, KK_KEY);
720    }
73  
74     public String getStatus() {
750        return status + this.getCurrentSize();
76     }
77  
78     public void setMaxIterations(int maxIterations) {
790        this.maxIterations = maxIterations;
800    }
81  
82     /**
83      * This one is an incremental visualization.
84      */
85     public boolean isIncremental() {
860        return true;
87     }
88  
89     /**
90      * Returns true once the current iteration has passed the maximum count.
91      */
92     public boolean incrementsAreDone() {
930        if (currentIteration > maxIterations) {
940            return true;
95         }
960        return false;
97     }
98  
99     protected void initialize_local() {
1000    }
101  
102     protected void initializeLocations() {
1030        super.initializeLocations();
104  
105         //Random random = new Random(12345L);
106  
1070        Dimension d = getCurrentSize();
1080        int height = d.height;
1090        int width = d.width;
110  
111         //System.out.println("v=" + getGraph().getVertices());
112         //int n = getVisibleGraph().numVertices();
1130        int n = getVisibleVertices().size();
1140        dm = new int[n*n];
1150        vertices = new Vertex[n];
1160        xydata = new Coordinates[n];
1170        unweightedShortestPaths =
118             new UnweightedShortestPath(getVisibleGraph());
119  
120         // assign IDs to all visible vertices
121         while(true) {
122             try {
1230                int index = 0;
1240                for (Iterator iter = getVisibleVertices().iterator();
1250                iter.hasNext(); ) {
1260                    Vertex v = (Vertex) iter.next();
1270                    Coordinates xyd = getCoordinates(v);
128                     
129                     //xyd.setX(random.nextDouble() * width);
130                     //xyd.setY(random.nextDouble() * height);
131                     
1320                    vertices[index] = v;
1330                    xydata[index] = xyd;
1340                    index++;
135                 }
136                 // no cme, break while loop
1370                break;
1380            } catch(ConcurrentModificationException cme) {
139                 // got cme, start over
1400            }
141         }
142  
143         // This is practically fast, but it would be the best if we have an
144         // implementation of All Pairs Shortest Paths(APSP) algorithm.
1450        diameter = 0;
1460        for (int i = 0; i < n - 1; i++) {
1470            for (int j = i + 1; j < n; j++) {
1480                int dist = unweightedShortestPaths.getDistance
149                     (vertices[i], vertices[j]).intValue();
1500                if (dist > diameter)
1510                    diameter = dist;
152             }
153         }
154         
1550          int L0 = height > width ? width : height;
1560          L = L0 / diameter;
157           //L = 0.75 * Math.sqrt(height * width / n);
158  
1590        for (int i = 0; i < n - 1; i++) {
1600            for (int j = i + 1; j < n; j++) {
1610                int dist = getDistance(vertices[i], vertices[j]);
1620                dm[i*n+j] = dist;
1630                dm[j*n+i] = dist;
164             }
165         }
1660    }
167  
168     /**
169      * Gets a distance (a length of the shortest path) between
170      * the specified vertices.
171      * Returned value is used for computing the strength of an embedded spring.
172      * You may override this method to visualize a graph with weighted edges.
173      * <p>
174      * The original Kamada-Kawai algorithm requires a connected graph.
175      * That is, pathes must be exist between
176      * every pair of vertices in the graph. To visualize a non-connected graph,
177      * this method returns (diameter + 1) for vertices that are not connected.
178      * <p>
179      * The default implementation is as follows:
180      * <pre>
181      * int dist = unweightedShortestPaths.getShortestPath(v1, v2);
182      * if (dist < 0)
183      * return diameter + 1;
184      * else
185      * return dist;
186      * </pre>
187      */
188     protected int getDistance(Vertex v1, Vertex v2) {
1890        int dist = unweightedShortestPaths.getDistance(v1, v2).intValue();
1900        if (dist < 0)
1910            return diameter + 1;
192         else
1930            return dist;
194     }
195  
196     protected void initialize_local_vertex(Vertex v) {
1970    }
198  
199     public void advancePositions() {
2000        currentIteration++;
2010        double energy = calcEnergy();
2020        status = "Kamada-Kawai V=" + getVisibleVertices().size()
203             + "(" + getGraph().numVertices() + ")"
204             + " IT: " + currentIteration
205             + " E=" + energy
206             ;
207  
2080        int n = getVisibleGraph().numVertices();
2090        if (n == 0)
2100            return;
211  
2120        double maxDeltaM = 0;
2130        int pm = -1; // the node having max deltaM
2140        for (int i = 0; i < n; i++) {
2150            if (isLocked(vertices[i]))
2160                continue;
2170            double deltam = calcDeltaM(i);
218             //System.out.println("* i=" + i + " deltaM=" + deltam);
2190            if (maxDeltaM < deltam) {
2200                maxDeltaM = deltam;
2210                pm = i;
222             }
223         }
2240        if (pm == -1)
2250            return;
226  
2270        for (int i = 0; i < 100; i++) {
2280            double[] dxy = calcDeltaXY(pm);
2290            xydata[pm].add(dxy[0], dxy[1]);
2300            double deltam = calcDeltaM(pm);
2310            if (deltam < EPSILON)
2320                break;
233             //if (dxy[0] > 1 || dxy[1] > 1 || dxy[0] < -1 || dxy[1] < -1)
234             // break;
235         }
236  
2370        if (adjustForGravity)
2380            adjustForGravity();
239  
2400        if (exchangeVertices && maxDeltaM < EPSILON) {
2410            energy = calcEnergy();
2420            for (int i = 0; i < n - 1; i++) {
2430                if (isLocked(vertices[i]))
2440                    continue;
2450                for (int j = i + 1; j < n; j++) {
2460                    if (isLocked(vertices[j]))
2470                        continue;
2480                    double xenergy = calcEnergyIfExchanged(i, j);
2490                    if (energy > xenergy) {
2500                        double sx = xydata[i].getX();
2510                        double sy = xydata[i].getY();
2520                        xydata[i].setX(xydata[j].getX());
2530                        xydata[i].setY(xydata[j].getY());
2540                        xydata[j].setX(sx);
2550                        xydata[j].setY(sy);
256                         //System.out.println("SWAP " + i + " with " + j +
257                         // " maxDeltaM=" + maxDeltaM);
2580                        return;
259                     }
260                 }
261             }
262         }
2630    }
264  
265     /**
266      * Shift all vertices so that the center of gravity is located at
267      * the center of the screen.
268      */
269     public void adjustForGravity() {
2700        Dimension d = getCurrentSize();
2710        double height = d.getHeight();
2720        double width = d.getWidth();
2730        double gx = 0;
2740        double gy = 0;
2750        for (int i = 0; i < xydata.length; i++) {
2760            gx += xydata[i].getX();
2770            gy += xydata[i].getY();
278         }
2790        gx /= xydata.length;
2800        gy /= xydata.length;
2810        double diffx = width / 2 - gx;
2820        double diffy = height / 2 - gy;
2830        for (int i = 0; i < xydata.length; i++) {
2840            xydata[i].add(diffx, diffy);
285         }
2860    }
287  
288     /**
289      * Enable or disable gravity point adjusting.
290      */
291     public void setAdjustForGravity(boolean on) {
2920        adjustForGravity = on;
2930    }
294  
295     /**
296      * Returns true if gravity point adjusting is enabled.
297      */
298     public boolean getAdjustForGravity() {
2990        return adjustForGravity;
300     }
301  
302     /**
303      * Enable or disable the local minimum escape technique by
304      * exchanging vertices.
305      */
306     public void setExchangeVertices(boolean on) {
3070        exchangeVertices = on;
3080    }
309  
310     /**
311      * Returns true if the local minimum escape technique by
312      * exchanging vertices is enabled.
313      */
314     public boolean getExchangeVertices() {
3150        return exchangeVertices;
316     }
317  
318     /**
319      * Determines a step to new position of the vertex m.
320      */
321     private double[] calcDeltaXY(int m) {
3220        double dE_dxm = 0;
3230        double dE_dym = 0;
3240        double d2E_d2xm = 0;
3250        double d2E_dxmdym = 0;
3260        double d2E_dymdxm = 0;
3270        double d2E_d2ym = 0;
328  
3290        for (int i = 0; i < vertices.length; i++) {
3300            if (i != m) {
3310                int dist = dm[m*vertices.length + i];
3320                int l_mi = L * dist;
3330                double k_mi = K / (dist * dist);
3340                double dx = xydata[m].getX() - xydata[i].getX();
3350                double dy = xydata[m].getY() - xydata[i].getY();
3360                double d = Math.sqrt(dx * dx + dy * dy);
3370                double ddd = d * d * d;
338  
3390                dE_dxm += k_mi * (1 - l_mi / d) * dx;
3400                dE_dym += k_mi * (1 - l_mi / d) * dy;
3410                d2E_d2xm += k_mi * (1 - l_mi * dy * dy / ddd);
3420                d2E_dxmdym += k_mi * l_mi * dx * dy / ddd;
343                 //d2E_dymdxm += k_mi * l_mi * dy * dx / ddd;
3440                d2E_d2ym += k_mi * (1 - l_mi * dx * dx / ddd);
345             }
346         }
347         // d2E_dymdxm equals to d2E_dxmdym.
3480        d2E_dymdxm = d2E_dxmdym;
349  
3500        double denomi = d2E_d2xm * d2E_d2ym - d2E_dxmdym * d2E_dymdxm;
3510        double deltaX = (d2E_dxmdym * dE_dym - d2E_d2ym * dE_dxm) / denomi;
3520        double deltaY = (d2E_dymdxm * dE_dxm - d2E_d2xm * dE_dym) / denomi;
3530        return new double[]{deltaX, deltaY};
354     }
355  
356     /**
357      * Calculates the gradient of energy function at the vertex m.
358      */
359     private double calcDeltaM(int m) {
3600        double dEdxm = 0;
3610        double dEdym = 0;
3620        for (int i = 0; i < vertices.length; i++) {
3630            if (i != m) {
3640                double dist = dm[m*vertices.length + i];
3650                double l_mi = L * dist;
3660                double k_mi = K / (dist * dist);
367  
3680                double dx = xydata[m].getX() - xydata[i].getX();
3690                double dy = xydata[m].getY() - xydata[i].getY();
3700                double d = Math.sqrt(dx * dx + dy * dy);
371  
3720                double common = k_mi * (1 - l_mi / d);
3730                dEdxm += common * dx;
3740                dEdym += common * dy;
375             }
376         }
3770        return Math.sqrt(dEdxm * dEdxm + dEdym * dEdym);
378     }
379  
380     /**
381      * Calculates the energy function E.
382      */
383     private double calcEnergy() {
3840        double energy = 0;
3850        for (int i = 0; i < vertices.length - 1; i++) {
3860            for (int j = i + 1; j < vertices.length; j++) {
3870                double dist = dm[i*vertices.length + i];
3880                double l_ij = L * dist;
3890                double k_ij = K / (dist * dist);
3900                double dx = xydata[i].getX() - xydata[j].getX();
3910                double dy = xydata[i].getY() - xydata[j].getY();
3920                double d = Math.sqrt(dx * dx + dy * dy);
393  
394  
3950                energy += k_ij / 2 * (dx * dx + dy * dy + l_ij * l_ij -
396                                       2 * l_ij * d);
397             }
398         }
3990        return energy;
400     }
401  
402     /**
403      * Calculates the energy function E as if positions of the
404      * specified vertices are exchanged.
405      */
406     private double calcEnergyIfExchanged(int p, int q) {
4070        if (p >= q)
4080            throw new RuntimeException("p should be < q");
4090        double energy = 0; // < 0
4100        for (int i = 0; i < vertices.length - 1; i++) {
4110            for (int j = i + 1; j < vertices.length; j++) {
4120                int ii = i;
4130                int jj = j;
4140                if (i == p) ii = q;
4150                if (j == q) jj = p;
416  
4170                double dist = dm[j*vertices.length + i];
4180                double l_ij = L * dist;
4190                double k_ij = K / (dist * dist);
4200                double dx = xydata[ii].getX() - xydata[jj].getX();
4210                double dy = xydata[ii].getY() - xydata[jj].getY();
4220                double d = Math.sqrt(dx * dx + dy * dy);
423                 
4240                energy += k_ij / 2 * (dx * dx + dy * dy + l_ij * l_ij -
425                                       2 * l_ij * d);
426             }
427         }
4280        return energy;
429     }
430 }

jcoverage | summary | package | file

this report was generated by version 1.0.5 of jcoverage.
visit www.jcoverage.com for updates.

copyright © 2003, jcoverage ltd. all rights reserved.
Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.