jcoverage | summary | package | file

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

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.event.ComponentAdapter;
11 import java.awt.event.ComponentEvent;
12 import java.awt.geom.Point2D;
13 import java.util.ConcurrentModificationException;
14 import java.util.Iterator;
15  
16 import edu.uci.ics.jung.graph.Edge;
17 import edu.uci.ics.jung.graph.Graph;
18 import edu.uci.ics.jung.graph.Vertex;
19 import edu.uci.ics.jung.utils.Pair;
20 import edu.uci.ics.jung.utils.UserData;
21  
22 /**
23  * The SpringLayout package represents a visualization of a set of nodes. The
24  * SpringLayout, which is initialized with a Graph, assigns X/Y locations to
25  * each node. When called <code>relax()</code>, the SpringLayout moves the
26  * visualization forward one step.
27  *
28  * @author Danyel Fisher
29  * @author Joshua O'Madadhain
30  */
31 public class SpringLayout extends AbstractLayout implements LayoutMutable {
32  
331    private static final Object SPRING_KEY = "temp_edu.uci.ics.jung.Spring_Visualization_Key";
349    protected double stretch = 0.70;
35     protected LengthFunction lengthFunction;
369    protected int repulsion_range = 100;
379    protected double force_multiplier = 1.0 / 3.0;
38  
39     /**
40      * Returns the status.
41      */
42     public String getStatus() {
432        return null;
44     }
45  
46     /**
47      * Constructor for a SpringLayout for a raw graph with associated
48      * dimension--the input knows how big the graph is. Defaults to the unit
49      * length function.
50      */
51     public SpringLayout(Graph g) {
529        this(g, UNITLENGTHFUNCTION);
539    }
54  
55     /**
56      * Constructor for a SpringLayout for a raw graph with associated component.
57      *
58      * @param g
59      * the input Graph
60      * @param f
61      * the length function
62      */
63     public SpringLayout(Graph g, LengthFunction f) {
649        super(g);
659        this.lengthFunction = f;
669    }
67  
68     /**
69      * @return the current value for the stretch parameter
70      * @see #setStretch(double)
71      */
72     public double getStretch()
73     {
740        return stretch;
75     }
76     
77     /**
78      * <p>Sets the stretch parameter for this instance. This value
79      * specifies how much the degrees of an edge's incident vertices
80      * should influence how easily the endpoints of that edge
81      * can move (that is, that edge's tendency to change its length).</p>
82      *
83      * <p>The default value is 0.70. Positive values less than 1 cause
84      * high-degree vertices to move less than low-degree vertices, and
85      * values > 1 cause high-degree vertices to move more than
86      * low-degree vertices. Negative values will have unpredictable
87      * and inconsistent results.</p>
88      * @param stretch
89      */
90     public void setStretch(double stretch)
91     {
920        this.stretch = stretch;
930    }
94     
95     /**
96      * @return the current value for the node repulsion range
97      * @see #setRepulsionRange(int)
98      */
99     public int getRepulsionRange()
100     {
1010        return repulsion_range;
102     }
103  
104     /**
105      * Sets the node repulsion range (in drawing area units) for this instance.
106      * Outside this range, nodes do not repel each other. The default value
107      * is 100. Negative values are treated as their positive equivalents.
108      * @param range
109      */
110     public void setRepulsionRange(int range)
111     {
1120        this.repulsion_range = range;
1130    }
114     
115     /**
116      * @return the current value for the edge length force multiplier
117      * @see #setForceMultiplier(double)
118      */
119     public double getForceMultiplier()
120     {
1210        return force_multiplier;
122     }
123     
124     /**
125      * Sets the force multiplier for this instance. This value is used to
126      * specify how strongly an edge "wants" to be its default length
127      * (higher values indicate a greater attraction for the default length),
128      * which affects how much its endpoints move at each timestep.
129      * The default value is 1/3. A value of 0 turns off any attempt by the
130      * layout to cause edges to conform to the default length. Negative
131      * values cause long edges to get longer and short edges to get shorter; use
132      * at your own risk.
133      */
134     public void setForceMultiplier(double force)
135     {
1360        this.force_multiplier = force;
1370    }
138     
139     protected void initialize_local() {
140         try {
14110        for (Iterator iter = getGraph().getEdges().iterator(); iter.hasNext();) {
1425000            Edge e = (Edge) iter.next();
1435000            SpringEdgeData sed = getSpringData(e);
1445000            if (sed == null) {
1454500                sed = new SpringEdgeData(e);
1464500                e.addUserDatum(getSpringKey(), sed, UserData.REMOVE);
147             }
1485000            calcEdgeLength(sed, lengthFunction);
149         }
1500        } catch(ConcurrentModificationException cme) {
1510            initialize_local();
15210        }
15310    }
154  
1559    Object key = null;
156  
157     public Object getSpringKey() {
15880068        if (key == null) key = new Pair(this, SPRING_KEY);
15980068        return key;
160     }
161  
162     /**
163      * (non-Javadoc)
164      *
165      * @see edu.uci.ics.jung.visualization.AbstractLayout#initialize_local_vertex(edu.uci.ics.jung.graph.Vertex)
166      */
167     protected void initialize_local_vertex(Vertex v) {
168500        SpringVertexData vud = getSpringData(v);
169500        if (vud == null) {
170450            vud = new SpringVertexData();
171450            v.addUserDatum(getSpringKey(), vud, UserData.REMOVE);
172         }
173500    }
174  
175     /* ------------------------- */
176  
177     protected void calcEdgeLength(SpringEdgeData sed, LengthFunction f) {
1785000        sed.length = f.getLength(sed.e);
1795000    }
180  
181     /* ------------------------- */
182  
183  
184     /**
185      * Relaxation step. Moves all nodes a smidge.
186      */
187     public void advancePositions() {
188         try {
18945        for (Iterator iter = getVisibleVertices().iterator(); iter.hasNext();) {
1902154            Vertex v = (Vertex) iter.next();
1912154            SpringVertexData svd = getSpringData(v);
1922154            if (svd == null) {
1930                continue;
194             }
1952154            svd.dx /= 4;
1962154            svd.dy /= 4;
1972154            svd.edgedx = svd.edgedy = 0;
1982154            svd.repulsiondx = svd.repulsiondy = 0;
199         }
2000        } catch(ConcurrentModificationException cme) {
2010            advancePositions();
20245        }
203  
20445        relaxEdges();
20545        calculateRepulsion();
20645        moveNodes();
20745    }
208  
209     protected Vertex getAVertex(Edge e) {
21021020        Vertex v = (Vertex) e.getIncidentVertices().iterator().next();
21121020        return v;
212     }
213  
214     protected void relaxEdges() {
215         try {
21645        for (Iterator i = getVisibleEdges().iterator(); i.hasNext();) {
21721020            Edge e = (Edge) i.next();
218  
21921020            Vertex v1 = getAVertex(e);
22021020            Vertex v2 = e.getOpposite(v1);
221  
22221020            Point2D p1 = getLocation(v1);
22321020            Point2D p2 = getLocation(v2);
22421020            if(p1 == null || p2 == null) continue;
22521020            double vx = p1.getX() - p2.getX();
22621020            double vy = p1.getY() - p2.getY();
22721020            double len = Math.sqrt(vx * vx + vy * vy);
228             
22921020            SpringEdgeData sed = getSpringData(e);
23021020            if (sed == null) {
2310                continue;
232             }
23321020            double desiredLen = sed.length;
234  
235             // round from zero, if needed [zero would be Bad.].
23621020            len = (len == 0) ? .0001 : len;
237  
23821020            double f = force_multiplier * (desiredLen - len) / len;
239  
24021020            f = f * Math.pow(stretch, (v1.degree() + v2.degree() - 2));
241  
242             // the actual movement distance 'dx' is the force multiplied by the
243             // distance to go.
24421020            double dx = f * vx;
24521020            double dy = f * vy;
246             SpringVertexData v1D, v2D;
24721020            v1D = getSpringData(v1);
24821020            v2D = getSpringData(v2);
249  
25021020            sed.f = f;
251  
25221020            v1D.edgedx += dx;
25321020            v1D.edgedy += dy;
25421020            v2D.edgedx += -dx;
25521020            v2D.edgedy += -dy;
256         }
2570        } catch(ConcurrentModificationException cme) {
2580            relaxEdges();
25945        }
26045    }
261  
262     protected void calculateRepulsion() {
263         try {
26445        for (Iterator iter = getGraph().getVertices().iterator(); iter
2652295                .hasNext();) {
2662250            Vertex v = (Vertex) iter.next();
2672250            if (isLocked(v)) continue;
268  
2692250            SpringVertexData svd = getSpringData(v);
2702250            if(svd == null) continue;
2712250            double dx = 0, dy = 0;
272  
2732250            for (Iterator iter2 = getGraph().getVertices().iterator(); iter2
274114750                    .hasNext();) {
275112500                Vertex v2 = (Vertex) iter2.next();
276112500                if (v == v2) continue;
277110250                Point2D p = getLocation(v);
278110250                Point2D p2 = getLocation(v2);
279110250                if(p == null || p2 == null) continue;
280110250                double vx = p.getX() - p2.getX();
281110250                double vy = p.getY() - p2.getY();
282110250                double distance = vx * vx + vy * vy;
283110250                if (distance == 0) {
2840                    dx += Math.random();
2850                    dy += Math.random();
286110250                } else if (distance < repulsion_range * repulsion_range) {
28785358                    double factor = 1;
28885358                    dx += factor * vx / Math.pow(distance, 2);
28985358                    dy += factor * vy / Math.pow(distance, 2);
290                 }
291             }
2922250            double dlen = dx * dx + dy * dy;
2932250            if (dlen > 0) {
2942250                dlen = Math.sqrt(dlen) / 2;
2952250                svd.repulsiondx += dx / dlen;
2962250                svd.repulsiondy += dy / dlen;
297             }
298         }
2990        } catch(ConcurrentModificationException cme) {
3000            calculateRepulsion();
30145        }
30245    }
303  
304     protected void moveNodes() {
305  
30645        synchronized (getCurrentSize()) {
307             try {
30845                for (Iterator i = getVisibleVertices().iterator(); i.hasNext();) {
3092154                    Vertex v = (Vertex) i.next();
3102154                    if (isLocked(v)) continue;
3112154                    SpringVertexData vd = getSpringData(v);
3122154                    if(vd == null) continue;
3132154                    Coordinates xyd = getCoordinates(v);
314                     
3152154                    vd.dx += vd.repulsiondx + vd.edgedx;
3162154                    vd.dy += vd.repulsiondy + vd.edgedy;
317                     
318                     // keeps nodes from moving any faster than 5 per time unit
3192154                    xyd.addX(Math.max(-5, Math.min(5, vd.dx)));
3202154                    xyd.addY(Math.max(-5, Math.min(5, vd.dy)));
321                     
3222154                    int width = getCurrentSize().width;
3232154                    int height = getCurrentSize().height;
324                     
3252154                    if (xyd.getX() < 0) {
326114                        xyd.setX(0);
3272040                    } else if (xyd.getX() > width) {
328107                        xyd.setX(width);
329                     }
3302154                    if (xyd.getY() < 0) {
331139                        xyd.setY(0);
3322015                    } else if (xyd.getY() > height) {
33399                        xyd.setY(height);
334                     }
335                     
336                 }
3370            } catch(ConcurrentModificationException cme) {
3380                moveNodes();
33945            }
34045        }
34145    }
342  
343     public SpringVertexData getSpringData(Vertex v) {
34449098        return (SpringVertexData) (v.getUserDatum(getSpringKey()));
345     }
346  
347     public SpringEdgeData getSpringData(Edge e) {
348         try {
34926020            return (SpringEdgeData) (e.getUserDatum(getSpringKey()));
3500        } catch (ClassCastException cce) {
3510            System.out.println(e.getUserDatum(getSpringKey()).getClass());
3520            throw cce;
353         }
354     }
355  
356     public double getLength(Edge e) {
3570        return ((SpringEdgeData) e.getUserDatum(getSpringKey())).length;
358     }
359  
360     /* ---------------Length Function------------------ */
361  
362     /**
363      * If the edge is weighted, then override this method to show what the
364      * visualized length is.
365      *
366      * @author Danyel Fisher
367      */
368     public static interface LengthFunction {
369  
370         public double getLength(Edge e);
371     }
372  
373     /**
374      * Returns all edges as the same length: the input value
375      * @author danyelf
376      */
377     public static final class UnitLengthFunction implements LengthFunction {
378  
379         int length;
380  
381         public UnitLengthFunction(int length) {
382             this.length = length;
383         }
384  
385         public double getLength(Edge e) {
386             return length;
387         }
388     }
389  
3901    public static final LengthFunction UNITLENGTHFUNCTION = new UnitLengthFunction(
391             30);
392  
393     /* ---------------User Data------------------ */
394  
395     protected static class SpringVertexData {
396  
397         public double edgedx;
398  
399         public double edgedy;
400  
401         public double repulsiondx;
402  
403         public double repulsiondy;
404  
405         public SpringVertexData() {
406         }
407  
408         /** movement speed, x */
409         public double dx;
410  
411         /** movement speed, y */
412         public double dy;
413     }
414  
415     protected static class SpringEdgeData {
416  
417         public double f;
418  
419         public SpringEdgeData(Edge e) {
420             this.e = e;
421         }
422  
423         Edge e;
424  
425         double length;
426     }
427  
428     /* ---------------Resize handler------------------ */
429  
430     public class SpringDimensionChecker extends ComponentAdapter {
431  
432         public void componentResized(ComponentEvent e) {
433             resize(e.getComponent().getSize());
434         }
435     }
436  
437     /**
438      * This one is an incremental visualization
439      */
440     public boolean isIncremental() {
4412        return true;
442     }
443  
444     /**
445      * For now, we pretend it never finishes.
446      */
447     public boolean incrementsAreDone() {
44852        return false;
449     }
450  
451     /**
452      * @see edu.uci.ics.jung.visualization.LayoutMutable#update()
453      */
454     public void update() {
455         try {
4560        for (Iterator iter = getGraph().getVertices().iterator(); iter
4570                .hasNext();) {
4580            Vertex v = (Vertex) iter.next();
4590            Coordinates coord = (Coordinates) v.getUserDatum(getBaseKey());
4600            if (coord == null) {
4610                coord = new Coordinates();
4620                v.addUserDatum(getBaseKey(), coord, UserData.REMOVE);
4630                initializeLocation(v, coord, getCurrentSize());
4640                initialize_local_vertex(v);
465             }
466         }
4670        } catch(ConcurrentModificationException cme) {
4680            update();
4690        }
4700        initialize_local();
4710    }
472  
473 }

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.