jcoverage | summary | package | file

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

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  
16 import java.awt.Dimension;
17 import java.util.ConcurrentModificationException;
18 import java.util.Iterator;
19  
20 import edu.uci.ics.jung.algorithms.shortestpath.Distance;
21 import edu.uci.ics.jung.algorithms.shortestpath.UnweightedShortestPath;
22 import edu.uci.ics.jung.graph.Graph;
23 import edu.uci.ics.jung.graph.Vertex;
24 import edu.uci.ics.jung.statistics.GraphStatistics;
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.
30  * Does not respect filter calls, and sometimes crashes when the view changes to it.
31  *
32  * @see "Tomihisa Kamada and Satoru Kawai: An algorithm for drawing general indirect graphs. Information Processing Letters 31(1):7-15, 1989"
33  * @see "Tomihisa Kamada: On visualization of abstract objects and relations. Ph.D. dissertation, Dept. of Information Science, Univ. of Tokyo, Dec. 1988."
34  *
35  * @author Masanori Harada
36  */
37 public class KKLayout extends AbstractLayout {
38  
390    private double EPSILON = 0.1d;
40  
41     private int currentIteration;
420    private int maxIterations = 2000;
430    private String status = "KKLayout";
44  
45     private double L; // the ideal length of an edge
460    private double K = 1; // arbitrary const number
47     private double[][] dm; // distance matrix
48  
490    private boolean adjustForGravity = true;
500    private boolean exchangeVertices = true;
51  
52     private Vertex[] vertices;
53     private Coordinates[] xydata;
54  
55     /**
56      * Retrieves graph distances between vertices of the visible graph
57      */
58     protected Distance distance;
59  
60     /**
61      * The diameter of the visible graph. In other words, the maximum over all pairs
62      * of vertices of the length of the shortest path between a and bf the visible graph.
63      */
64     protected double diameter;
65  
66     /**
67      * A multiplicative factor which partly specifies the "preferred" length of an edge (L).
68      */
690    private double length_factor = 0.9;
70  
71     /**
72      * A multiplicative factor which specifies the fraction of the graph's diameter to be
73      * used as the inter-vertex distance between disconnected vertices.
74      */
750    private double disconnected_multiplier = 0.5;
76     
77     public KKLayout(Graph g)
78     {
790        this(g, new UnweightedShortestPath(g));
800    }
81  
82     public KKLayout(Graph g, Distance distance)
83     {
840        super(g);
850        this.distance = distance;
860    }
87  
88     /**
89      * Sets a multiplicative factor which
90      * partly specifies the "preferred" length of an edge (L).
91      */
92     public void setLengthFactor(double length_factor)
93     {
940        this.length_factor = length_factor;
950    }
96     
97     /**
98      * Sets a multiplicative factor that specifies the fraction of the graph's diameter to be
99      * used as the inter-vertex distance between disconnected vertices.
100      */
101     public void setDisconnectedDistanceMultiplier(double disconnected_multiplier)
102     {
1030        this.disconnected_multiplier = disconnected_multiplier;
1040    }
105     
106     public String getStatus() {
1070        return status + this.getCurrentSize();
108     }
109  
110     public void setMaxIterations(int maxIterations) {
1110        this.maxIterations = maxIterations;
1120    }
113  
114     /**
115      * This one is an incremental visualization.
116      */
117     public boolean isIncremental() {
1180        return true;
119     }
120  
121     /**
122      * Returns true once the current iteration has passed the maximum count.
123      */
124     public boolean incrementsAreDone() {
1250        if (currentIteration > maxIterations) {
1260            return true;
127         }
1280        return false;
129     }
130  
131     protected void initialize_local() {
1320        currentIteration = 0;
1330    }
134  
135     protected void initializeLocations() {
1360        super.initializeLocations();
137  
1380        Dimension d = getCurrentSize();
1390        double height = d.getHeight();
1400        double width = d.getWidth();
141  
1420        int n = getGraph().getVertices().size();
1430        dm = new double[n][n];
1440        vertices = new Vertex[n];
1450        xydata = new Coordinates[n];
146  
147         // assign IDs to all visible vertices
148         while(true) {
149             try {
1500                int index = 0;
1510                for (Iterator iter = getGraph().getVertices().iterator();
1520                iter.hasNext(); ) {
1530                    Vertex v = (Vertex) iter.next();
1540                    Coordinates xyd = getCoordinates(v);
1550                    vertices[index] = v;
1560                    xydata[index] = xyd;
1570                    index++;
158                 }
1590                break;
1600            } catch(ConcurrentModificationException cme) {}
161         }
162  
1630        diameter = GraphStatistics.diameter(getGraph(), distance, true);
164             
1650        double L0 = Math.min(height, width);
1660        L = (L0 / diameter) * length_factor; // length_factor used to be hardcoded to 0.9
167         //L = 0.75 * Math.sqrt(height * width / n);
168  
1690        for (int i = 0; i < n - 1; i++)
170         {
1710            for (int j = i + 1; j < n; j++)
172             {
1730                Number d_ij = distance.getDistance(vertices[i], vertices[j]);
1740                Number d_ji = distance.getDistance(vertices[j], vertices[i]);
1750                double dist = diameter * disconnected_multiplier;
1760                if (d_ij != null)
1770                   dist = Math.min(d_ij.doubleValue(), dist);
1780                if (d_ji != null)
1790                    dist = Math.min(d_ji.doubleValue(), dist);
1800                dm[i][j] = dm[j][i] = dist;
181             }
182         }
1830    }
184  
185     protected void initialize_local_vertex(Vertex v) {
1860    }
187  
188     public void advancePositions() {
1890        currentIteration++;
1900        double energy = calcEnergy();
1910        status = "Kamada-Kawai V=" + getVisibleVertices().size()
192             + "(" + getGraph().numVertices() + ")"
193             + " IT: " + currentIteration
194             + " E=" + energy
195             ;
196  
1970        int n = getVisibleGraph().numVertices();
1980        if (n == 0)
1990            return;
200  
2010        double maxDeltaM = 0;
2020        int pm = -1; // the node having max deltaM
2030        for (int i = 0; i < n; i++) {
2040            if (isLocked(vertices[i]))
2050                continue;
2060            double deltam = calcDeltaM(i);
207             //System.out.println("* i=" + i + " deltaM=" + deltam);
2080            if (maxDeltaM < deltam) {
2090                maxDeltaM = deltam;
2100                pm = i;
211             }
212         }
2130        if (pm == -1)
2140            return;
215  
2160        for (int i = 0; i < 100; i++) {
2170            double[] dxy = calcDeltaXY(pm);
2180            xydata[pm].add(dxy[0], dxy[1]);
2190            double deltam = calcDeltaM(pm);
2200            if (deltam < EPSILON)
2210                break;
222             //if (dxy[0] > 1 || dxy[1] > 1 || dxy[0] < -1 || dxy[1] < -1)
223             // break;
224         }
225  
2260        if (adjustForGravity)
2270            adjustForGravity();
228  
2290        if (exchangeVertices && maxDeltaM < EPSILON) {
2300            energy = calcEnergy();
2310            for (int i = 0; i < n - 1; i++) {
2320                if (isLocked(vertices[i]))
2330                    continue;
2340                for (int j = i + 1; j < n; j++) {
2350                    if (isLocked(vertices[j]))
2360                        continue;
2370                    double xenergy = calcEnergyIfExchanged(i, j);
2380                    if (energy > xenergy) {
2390                        double sx = xydata[i].getX();
2400                        double sy = xydata[i].getY();
2410                        xydata[i].setX(xydata[j].getX());
2420                        xydata[i].setY(xydata[j].getY());
2430                        xydata[j].setX(sx);
2440                        xydata[j].setY(sy);
245                         //System.out.println("SWAP " + i + " with " + j +
246                         // " maxDeltaM=" + maxDeltaM);
2470                        return;
248                     }
249                 }
250             }
251         }
2520    }
253  
254     /**
255      * Shift all vertices so that the center of gravity is located at
256      * the center of the screen.
257      */
258     public void adjustForGravity() {
2590        Dimension d = getCurrentSize();
2600        double height = d.getHeight();
2610        double width = d.getWidth();
2620        double gx = 0;
2630        double gy = 0;
2640        for (int i = 0; i < xydata.length; i++) {
2650            gx += xydata[i].getX();
2660            gy += xydata[i].getY();
267         }
2680        gx /= xydata.length;
2690        gy /= xydata.length;
2700        double diffx = width / 2 - gx;
2710        double diffy = height / 2 - gy;
2720        for (int i = 0; i < xydata.length; i++) {
2730            xydata[i].add(diffx, diffy);
274         }
2750    }
276  
277     /**
278      * Enable or disable gravity point adjusting.
279      */
280     public void setAdjustForGravity(boolean on) {
2810        adjustForGravity = on;
2820    }
283  
284     /**
285      * Returns true if gravity point adjusting is enabled.
286      */
287     public boolean getAdjustForGravity() {
2880        return adjustForGravity;
289     }
290  
291     /**
292      * Enable or disable the local minimum escape technique by
293      * exchanging vertices.
294      */
295     public void setExchangeVertices(boolean on) {
2960        exchangeVertices = on;
2970    }
298  
299     /**
300      * Returns true if the local minimum escape technique by
301      * exchanging vertices is enabled.
302      */
303     public boolean getExchangeVertices() {
3040        return exchangeVertices;
305     }
306  
307     /**
308      * Determines a step to new position of the vertex m.
309      */
310     private double[] calcDeltaXY(int m) {
3110        double dE_dxm = 0;
3120        double dE_dym = 0;
3130        double d2E_d2xm = 0;
3140        double d2E_dxmdym = 0;
3150        double d2E_dymdxm = 0;
3160        double d2E_d2ym = 0;
317  
3180        for (int i = 0; i < vertices.length; i++) {
3190            if (i != m) {
320                 
3210                double dist = dm[m][i];
3220                double l_mi = L * dist;
3230                double k_mi = K / (dist * dist);
3240                double dx = xydata[m].getX() - xydata[i].getX();
3250                double dy = xydata[m].getY() - xydata[i].getY();
3260                double d = Math.sqrt(dx * dx + dy * dy);
3270                double ddd = d * d * d;
328  
3290                dE_dxm += k_mi * (1 - l_mi / d) * dx;
3300                dE_dym += k_mi * (1 - l_mi / d) * dy;
3310                d2E_d2xm += k_mi * (1 - l_mi * dy * dy / ddd);
3320                d2E_dxmdym += k_mi * l_mi * dx * dy / ddd;
3330                d2E_d2ym += k_mi * (1 - l_mi * dx * dx / ddd);
334             }
335         }
336         // d2E_dymdxm equals to d2E_dxmdym.
3370        d2E_dymdxm = d2E_dxmdym;
338  
3390        double denomi = d2E_d2xm * d2E_d2ym - d2E_dxmdym * d2E_dymdxm;
3400        double deltaX = (d2E_dxmdym * dE_dym - d2E_d2ym * dE_dxm) / denomi;
3410        double deltaY = (d2E_dymdxm * dE_dxm - d2E_d2xm * dE_dym) / denomi;
3420        return new double[]{deltaX, deltaY};
343     }
344  
345     /**
346      * Calculates the gradient of energy function at the vertex m.
347      */
348     private double calcDeltaM(int m) {
3490        double dEdxm = 0;
3500        double dEdym = 0;
3510        for (int i = 0; i < vertices.length; i++) {
3520            if (i != m) {
3530                double dist = dm[m][i];
3540                double l_mi = L * dist;
3550                double k_mi = K / (dist * dist);
356  
3570                double dx = xydata[m].getX() - xydata[i].getX();
3580                double dy = xydata[m].getY() - xydata[i].getY();
3590                double d = Math.sqrt(dx * dx + dy * dy);
360  
3610                double common = k_mi * (1 - l_mi / d);
3620                dEdxm += common * dx;
3630                dEdym += common * dy;
364             }
365         }
3660        return Math.sqrt(dEdxm * dEdxm + dEdym * dEdym);
367     }
368  
369     /**
370      * Calculates the energy function E.
371      */
372     private double calcEnergy() {
3730        double energy = 0;
3740        for (int i = 0; i < vertices.length - 1; i++) {
3750            for (int j = i + 1; j < vertices.length; j++) {
3760                double dist = dm[i][j];
3770                double l_ij = L * dist;
3780                double k_ij = K / (dist * dist);
3790                double dx = xydata[i].getX() - xydata[j].getX();
3800                double dy = xydata[i].getY() - xydata[j].getY();
3810                double d = Math.sqrt(dx * dx + dy * dy);
382  
383  
3840                energy += k_ij / 2 * (dx * dx + dy * dy + l_ij * l_ij -
385                                       2 * l_ij * d);
386             }
387         }
3880        return energy;
389     }
390  
391     /**
392      * Calculates the energy function E as if positions of the
393      * specified vertices are exchanged.
394      */
395     private double calcEnergyIfExchanged(int p, int q) {
3960        if (p >= q)
3970            throw new RuntimeException("p should be < q");
3980        double energy = 0; // < 0
3990        for (int i = 0; i < vertices.length - 1; i++) {
4000            for (int j = i + 1; j < vertices.length; j++) {
4010                int ii = i;
4020                int jj = j;
4030                if (i == p) ii = q;
4040                if (j == q) jj = p;
405  
4060                double dist = dm[i][j];
4070                double l_ij = L * dist;
4080                double k_ij = K / (dist * dist);
4090                double dx = xydata[ii].getX() - xydata[jj].getX();
4100                double dy = xydata[ii].getY() - xydata[jj].getY();
4110                double d = Math.sqrt(dx * dx + dy * dy);
412                 
4130                energy += k_ij / 2 * (dx * dx + dy * dy + l_ij * l_ij -
414                                       2 * l_ij * d);
415             }
416         }
4170        return energy;
418     }
419 }

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.