jcoverage | summary | package | file

Coverage details for edu.uci.ics.jung.visualization.FRLayout

LineHitsSource
1 /*
2  * Copyright (c) 2003, the JUNG Project and the Regents of the University of
3  * California All rights reserved.
4  *
5  * This software is open-source under the BSD license; see either "license.txt"
6  * or http://jung.sourceforge.net/license.txt for a description.
7  */
8 package edu.uci.ics.jung.visualization;
9  
10 import java.awt.geom.Point2D;
11 import java.util.ConcurrentModificationException;
12 import java.util.Iterator;
13  
14 import cern.colt.matrix.DoubleMatrix1D;
15 import cern.colt.matrix.impl.DenseDoubleMatrix1D;
16 import edu.uci.ics.jung.exceptions.FatalException;
17 import edu.uci.ics.jung.graph.Edge;
18 import edu.uci.ics.jung.graph.Graph;
19 import edu.uci.ics.jung.graph.Vertex;
20 import edu.uci.ics.jung.utils.Pair;
21 import edu.uci.ics.jung.utils.UserData;
22  
23 /**
24  * Implements the Fruchterman-Reingold algorithm for node layout.
25  *
26  * @author Scott White, Yan-Biao Boey, Danyel Fisher
27  */
28 public class FRLayout extends AbstractLayout implements LayoutMutable {
29  
301    private static final Object FR_KEY = "edu.uci.ics.jung.FR_Visualization_Key";
31  
32     private double forceConstant;
33  
34     private double temperature;
35  
36     private int currentIteration;
37  
389    private String status = null;
39  
409    private int mMaxIterations = 700;
41  
42     public FRLayout(Graph g) {
439        super(g);
449    }
45  
469    private double attraction_multiplier = 0.75;
47     
48     private double attraction_constant;
49     
509    private double repulsion_multiplier = 0.75;
51     
52     private double repulsion_constant;
53     
54     public void setAttractionMultiplier(double attraction)
55     {
560        this.attraction_multiplier = attraction;
570    }
58     
59     public void setRepulsionMultiplier(double repulsion)
60     {
610        this.repulsion_multiplier = repulsion;
620    }
63     
64     /*
65      * new function for handling updates and changes to the graph
66      */
67     public synchronized void update() {
68         try {
690            for (Iterator iter = getGraph().getVertices().iterator(); iter
700            .hasNext();) {
710                Vertex v = (Vertex) iter.next();
720                Coordinates coord = getCoordinates(v);
73 // Coordinates coord = (Coordinates) v.getUserDatum(getBaseKey());
740                if (coord == null) {
750                    coord = new Coordinates();
760                    v.addUserDatum(getBaseKey(), coord, UserData.REMOVE);
770                    initializeLocation(v, coord, getCurrentSize());
780                    initialize_local_vertex(v);
79                 }
80                 
81             }
820        } catch(ConcurrentModificationException cme) {
830            update();
840        }
850        initialize_local();
860    }
87  
88     /**
89      * Returns the current temperature and number of iterations elapsed, as a
90      * string.
91      */
92     public String getStatus() {
932        return status;
94     }
95  
96     public void forceMove(Vertex picked,double x, double y) {
9750        super.forceMove(picked, x, y);
9850    }
99  
100     protected void initialize_local() {
10110        currentIteration = 0;
10210        temperature = getCurrentSize().getWidth() / 10;
103         
10410        forceConstant =
105             Math
106             .sqrt(getCurrentSize().getHeight()
107                     * getCurrentSize().getWidth()
108                     / getVisibleGraph().numVertices());
109 // / Math.max(getVisibleGraph().numEdges(), getVisibleGraph().numVertices()));
110         
11110        attraction_constant = attraction_multiplier * forceConstant;
11210        repulsion_constant = repulsion_multiplier * forceConstant;
113         
114 // forceConstant = 0.75 * Math
115 // .sqrt(getCurrentSize().getHeight()
116 // * getCurrentSize().getWidth()
117 // / getVisibleGraph().numVertices());
11810    }
119  
1209    private Object key = null;
121  
1229    private double EPSILON = 0.000001D;
123  
124     /**
125      * Returns a visualization-specific key (that is, specific both to this
126      * instance and <tt>AbstractLayout</tt>) that can be used to access
127      * UserData related to the <tt>AbstractLayout</tt>.
128      */
129     public Object getKey() {
130205266        if (key == null) key = new Pair(this, FR_KEY);
131205266        return key;
132     }
133  
134     protected void initialize_local_vertex(Vertex v) {
135500        if (v.getUserDatum(getKey()) == null) {
136450            v.addUserDatum(getKey(), new FRVertexData(), UserData.REMOVE);
137         }
138500    }
139  
140     /**
141      * Moves the iteration forward one notch, calculation attraction and
142      * repulsion between vertices and edges and cooling the temperature.
143      */
144     public synchronized void advancePositions() {
145197        currentIteration++;
146197        status = "VV: " + getVisibleVertices().size() + " IT: "
147                 + currentIteration + " temp: " + temperature;
148         /**
149          * Calculate repulsion
150          */
151         while(true) {
152             
153             try {
154197                for (Iterator iter = getVisibleVertices().iterator(); iter.hasNext();) {
1559466                    Vertex v1 = (Vertex) iter.next();
1569466                    if (isLocked(v1)) continue;
1579466                    calcRepulsion(v1);
158                 }
159197                break;
1600            } catch(ConcurrentModificationException cme) {}
161         }
162  
163         /**
164          * Calculate attraction
165          */
166         while(true) {
167             try {
168197                for (Iterator iter = getVisibleEdges().iterator(); iter.hasNext();) {
16992692                    Edge e = (Edge) iter.next();
170                     
17192692                    calcAttraction(e);
172                 }
173197                break;
1740            } catch(ConcurrentModificationException cme) {}
175         }
176  
177 // double cumulativeChange = 0;
178  
179         while(true) {
180             try {
181                 
182197                for (Iterator iter = getVisibleVertices().iterator(); iter.hasNext();) {
1839466                    Vertex v = (Vertex) iter.next();
1849466                    if (isLocked(v)) continue;
1859466                    calcPositions(v);
186                 }
187197                break;
1880            } catch(ConcurrentModificationException cme) {}
189         }
190197        cool();
191197    }
192  
193     public synchronized void calcPositions(Vertex v) {
1949466        FRVertexData fvd = getFRData(v);
1959466        if(fvd == null) return;
1969466        Coordinates xyd = getCoordinates(v);
1979466        double deltaLength = Math.max(EPSILON, Math.sqrt(fvd.disp
198                 .zDotProduct(fvd.disp)));
199  
2009466        double newXDisp = fvd.getXDisp() / deltaLength
201                 * Math.min(deltaLength, temperature);
202  
2039466        if (Double.isNaN(newXDisp)) { throw new FatalException(
204                 "Unexpected mathematical result in FRLayout:calcPositions [xdisp]"); }
205  
2069466        double newYDisp = fvd.getYDisp() / deltaLength
207                 * Math.min(deltaLength, temperature);
2089466        xyd.addX(newXDisp);
2099466        xyd.addY(newYDisp);
210  
2119466        double borderWidth = getCurrentSize().getWidth() / 50.0;
2129466        double newXPos = xyd.getX();
2139466        if (newXPos < borderWidth) {
2140            newXPos = borderWidth + Math.random() * borderWidth * 2.0;
2159466        } else if (newXPos > (getCurrentSize().getWidth() - borderWidth)) {
2160            newXPos = getCurrentSize().getWidth() - borderWidth - Math.random()
217                     * borderWidth * 2.0;
218         }
219         //double newXPos = Math.min(getCurrentSize().getWidth() - 20.0,
220         // Math.max(20.0, xyd.getX()));
221  
2229466        double newYPos = xyd.getY();
2239466        if (newYPos < borderWidth) {
2240            newYPos = borderWidth + Math.random() * borderWidth * 2.0;
2259466        } else if (newYPos > (getCurrentSize().getHeight() - borderWidth)) {
2260            newYPos = getCurrentSize().getHeight() - borderWidth
227                     - Math.random() * borderWidth * 2.0;
228         }
229         //double newYPos = Math.min(getCurrentSize().getHeight() - 20.0,
230         // Math.max(20.0, xyd.getY()));
231  
2329466        xyd.setX(newXPos);
2339466        xyd.setY(newYPos);
2349466    }
235  
236     public void calcAttraction(Edge e) {
23792692        Vertex v1 = (Vertex) e.getIncidentVertices().iterator().next();
23892692        Vertex v2 = e.getOpposite(v1);
239  
24092692        Point2D p1 = getLocation(v1);
24192692        Point2D p2 = getLocation(v2);
24292692        if(p1 == null || p2 == null) return;
24392692        double xDelta = p1.getX() - p2.getX();
24492692        double yDelta = p1.getY() - p2.getY();
245  
24692692        double deltaLength = Math.max(EPSILON, Math.sqrt((xDelta * xDelta)
247                 + (yDelta * yDelta)));
248  
249 // double force = (deltaLength * deltaLength) / forceConstant;
250         
25192692        double force = (deltaLength * deltaLength) / attraction_constant;
252  
25392692        if (Double.isNaN(force)) { throw new FatalException(
254                 "Unexpected mathematical result in FRLayout:calcPositions [force]"); }
255  
25692692        FRVertexData fvd1 = getFRData(v1);
25792692        FRVertexData fvd2 = getFRData(v2);
258  
25992692        fvd1.decrementDisp((xDelta / deltaLength) * force,
260                 (yDelta / deltaLength) * force);
26192692        fvd2.incrementDisp((xDelta / deltaLength) * force,
262                 (yDelta / deltaLength) * force);
26392692    }
264  
265     public void calcRepulsion(Vertex v1) {
2669466        FRVertexData fvd1 = getFRData(v1);
2679466        if(fvd1 == null) return;
2689466        fvd1.setDisp(0, 0);
269  
270         try {
2719466            for (Iterator iter2 = getVisibleVertices().iterator(); iter2.hasNext();) {
272463316                Vertex v2 = (Vertex) iter2.next();
273463316                if (isLocked(v2)) continue;
274463316                if (v1 != v2) {
275453850                    Point2D p1 = getLocation(v1);
276453850                    Point2D p2 = getLocation(v2);
277453850                    if(p1 == null || p2 == null) continue;
278453850                    double xDelta = p1.getX() - p2.getX();
279453850                    double yDelta = p1.getY() - p2.getY();
280                     
281453850                    double deltaLength = Math.max(EPSILON, Math
282                             .sqrt((xDelta * xDelta) + (yDelta * yDelta)));
283                     
284 // double force = (forceConstant * forceConstant) / deltaLength;
285453850                    double force = (repulsion_constant * repulsion_constant) / deltaLength;
286                     
287453850                    if (Double.isNaN(force)) { throw new FatalException(
288                     "Unexpected mathematical result in FRLayout:calcPositions [repulsion]"); }
289                     
290453850                    fvd1.incrementDisp((xDelta / deltaLength) * force,
291                             (yDelta / deltaLength) * force);
292                 }
293             }
2940        } catch(ConcurrentModificationException cme) {
2950            calcRepulsion(v1);
2969466        }
2979466    }
298  
299     private void cool() {
300197        temperature *= (1.0 - currentIteration / (double) mMaxIterations);
301197    }
302  
303     public void setMaxIterations(int maxIterations) {
3040        mMaxIterations = maxIterations;
3050    }
306  
307     public FRVertexData getFRData(Vertex v) {
308204316        return (FRVertexData) (v.getUserDatum(getKey()));
309     }
310  
311     /**
312      * This one is an incremental visualization.
313      */
314     public boolean isIncremental() {
3152        return true;
316     }
317  
318     /**
319      * Returns true once the current iteration has passed the maximum count,
320      * <tt>MAX_ITERATIONS</tt>.
321      */
322     public boolean incrementsAreDone() {
323204        if (currentIteration > mMaxIterations) {
324 // System.out.println("Reached currentIteration =" + currentIteration + ", maxIterations=" + mMaxIterations);
3250            return true;
326         }
327204        return false;
328     }
329  
330     public static class FRVertexData {
331  
332         private DoubleMatrix1D disp;
333  
334         public FRVertexData() {
335             initialize();
336         }
337  
338         public void initialize() {
339             disp = new DenseDoubleMatrix1D(2);
340         }
341  
342         public double getXDisp() {
343             return disp.get(0);
344         }
345  
346         public double getYDisp() {
347             return disp.get(1);
348         }
349  
350         public void setDisp(double x, double y) {
351             disp.set(0, x);
352             disp.set(1, y);
353         }
354  
355         public void incrementDisp(double x, double y) {
356             disp.set(0, disp.get(0) + x);
357             disp.set(1, disp.get(1) + y);
358         }
359  
360         public void decrementDisp(double x, double y) {
361             disp.set(0, disp.get(0) - x);
362             disp.set(1, disp.get(1) - y);
363         }
364     }
365 }

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.