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() {
130205426        if (key == null) key = new Pair(this, FR_KEY);
131205426        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();) {
16992772                    Edge e = (Edge) iter.next();
170                     
17192772                    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) {
23792772        Pair endpoints = e.getEndpoints();
23892772        Vertex v1 = (Vertex)endpoints.getFirst();
23992772        Vertex v2 = (Vertex)endpoints.getSecond();
24092772        boolean v1_locked = isLocked(v1);
24192772        boolean v2_locked = isLocked(v2);
242         
243         // if both are locked, nothing to do; return
24492772        if (v1_locked && v2_locked)
2450            return;
246  
24792772        Point2D p1 = getLocation(v1);
24892772        Point2D p2 = getLocation(v2);
24992772        if(p1 == null || p2 == null) return;
25092772        double xDelta = p1.getX() - p2.getX();
25192772        double yDelta = p1.getY() - p2.getY();
252  
25392772        double deltaLength = Math.max(EPSILON, Math.sqrt((xDelta * xDelta)
254                 + (yDelta * yDelta)));
255  
256 // double force = (deltaLength * deltaLength) / forceConstant;
257         
25892772        double force = (deltaLength * deltaLength) / attraction_constant;
259  
26092772        if (Double.isNaN(force)) { throw new FatalException(
261                 "Unexpected mathematical result in FRLayout:calcPositions [force]"); }
262  
26392772        double dx = (xDelta / deltaLength) * force;
26492772        double dy = (yDelta / deltaLength) * force;
265         
26692772        if (!v1_locked)
267         {
26892772            FRVertexData fvd1 = getFRData(v1);
26992772            fvd1.decrementDisp(dx, dy);
270         }
27192772        if (!v2_locked)
272         {
27392772            FRVertexData fvd2 = getFRData(v2);
27492772            fvd2.incrementDisp(dx, dy);
275         }
27692772    }
277  
278     public void calcRepulsion(Vertex v1) {
2799466        FRVertexData fvd1 = getFRData(v1);
2809466        if(fvd1 == null) return;
2819466        fvd1.setDisp(0, 0);
282  
283         try {
2849466            for (Iterator iter2 = getVisibleVertices().iterator(); iter2.hasNext();) {
285463316                Vertex v2 = (Vertex) iter2.next();
286                 // if (isLocked(v2)) continue;
287463316                if (v1 != v2) {
288453850                    Point2D p1 = getLocation(v1);
289453850                    Point2D p2 = getLocation(v2);
290453850                    if(p1 == null || p2 == null) continue;
291453850                    double xDelta = p1.getX() - p2.getX();
292453850                    double yDelta = p1.getY() - p2.getY();
293                     
294453850                    double deltaLength = Math.max(EPSILON, Math
295                             .sqrt((xDelta * xDelta) + (yDelta * yDelta)));
296                     
297 // double force = (forceConstant * forceConstant) / deltaLength;
298453850                    double force = (repulsion_constant * repulsion_constant) / deltaLength;
299                     
300453850                    if (Double.isNaN(force)) { throw new FatalException(
301                     "Unexpected mathematical result in FRLayout:calcPositions [repulsion]"); }
302                     
303453850                    fvd1.incrementDisp((xDelta / deltaLength) * force,
304                             (yDelta / deltaLength) * force);
305                 }
306             }
3070        } catch(ConcurrentModificationException cme) {
3080            calcRepulsion(v1);
3099466        }
3109466    }
311  
312     private void cool() {
313197        temperature *= (1.0 - currentIteration / (double) mMaxIterations);
314197    }
315  
316     public void setMaxIterations(int maxIterations) {
3170        mMaxIterations = maxIterations;
3180    }
319  
320     public FRVertexData getFRData(Vertex v) {
321204476        return (FRVertexData) (v.getUserDatum(getKey()));
322     }
323  
324     /**
325      * This one is an incremental visualization.
326      */
327     public boolean isIncremental() {
3282        return true;
329     }
330  
331     /**
332      * Returns true once the current iteration has passed the maximum count,
333      * <tt>MAX_ITERATIONS</tt>.
334      */
335     public boolean incrementsAreDone() {
336204        if (currentIteration > mMaxIterations) {
337 // System.out.println("Reached currentIteration =" + currentIteration + ", maxIterations=" + mMaxIterations);
3380            return true;
339         }
340204        return false;
341     }
342  
343     public static class FRVertexData {
344  
345         private DoubleMatrix1D disp;
346  
347         public FRVertexData() {
348             initialize();
349         }
350  
351         public void initialize() {
352             disp = new DenseDoubleMatrix1D(2);
353         }
354  
355         public double getXDisp() {
356             return disp.get(0);
357         }
358  
359         public double getYDisp() {
360             return disp.get(1);
361         }
362  
363         public void setDisp(double x, double y) {
364             disp.set(0, x);
365             disp.set(1, y);
366         }
367  
368         public void incrementDisp(double x, double y) {
369             disp.set(0, disp.get(0) + x);
370             disp.set(1, disp.get(1) + y);
371         }
372  
373         public void decrementDisp(double x, double y) {
374             disp.set(0, disp.get(0) - x);
375             disp.set(1, disp.get(1) - y);
376         }
377     }
378 }

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.