Line | Hits | Source |
---|---|---|
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 | * Created on Jul 7, 2003 | |
9 | * | |
10 | */ | |
11 | package edu.uci.ics.jung.visualization; | |
12 | ||
13 | import java.awt.Dimension; | |
14 | import java.awt.geom.Point2D; | |
15 | import java.util.ConcurrentModificationException; | |
16 | import java.util.HashSet; | |
17 | import java.util.Iterator; | |
18 | import java.util.Set; | |
19 | ||
20 | import javax.swing.event.ChangeListener; | |
21 | import javax.swing.event.EventListenerList; | |
22 | ||
23 | import edu.uci.ics.jung.graph.ArchetypeVertex; | |
24 | import edu.uci.ics.jung.graph.Edge; | |
25 | import edu.uci.ics.jung.graph.Graph; | |
26 | import edu.uci.ics.jung.graph.Vertex; | |
27 | import edu.uci.ics.jung.utils.ChangeEventSupport; | |
28 | import edu.uci.ics.jung.utils.DefaultChangeEventSupport; | |
29 | import edu.uci.ics.jung.utils.GraphUtils; | |
30 | import edu.uci.ics.jung.utils.Pair; | |
31 | import edu.uci.ics.jung.utils.UserData; | |
32 | ||
33 | /** | |
34 | * Implements some of the dirty work of writing a layout algorithm, allowing | |
35 | * the user to express their major intent more simply. When writing a <tt>Layout</tt>, | |
36 | * there are many shared tasks: handling tracking locked nodes, applying | |
37 | * filters, and tracing nearby vertices. This package automates all of those. | |
38 | * | |
39 | * @author Danyel Fisher, Scott White | |
40 | */ | |
41 | abstract public class AbstractLayout implements Layout, ChangeEventSupport { | |
42 | ||
43 | 18 | protected ChangeEventSupport changeSupport = |
44 | new DefaultChangeEventSupport(this); | |
45 | ||
46 | /** | |
47 | * a set of vertices that should not move in relation to the | |
48 | * other vertices | |
49 | */ | |
50 | private Set dontmove; | |
51 | ||
52 | 2 | private static final Object BASE_KEY = |
53 | "edu.uci.ics.jung.Base_Visualization_Key"; | |
54 | ||
55 | private Dimension currentSize; | |
56 | private Graph baseGraph; | |
57 | private Graph visibleGraph; | |
58 | protected VertexLocationFunction vertex_locations; | |
59 | ||
60 | /** | |
61 | * Constructor. Initializes the current size to be 100x100, both the graph | |
62 | * and the showing graph to the argument, and creates the <tt>dontmove</tt> | |
63 | * set. | |
64 | * | |
65 | * @param g | |
66 | */ | |
67 | 18 | public AbstractLayout(Graph g) { |
68 | 18 | this.baseGraph = g; |
69 | 18 | this.visibleGraph = g; |
70 | 18 | this.visibleEdges = g.getEdges(); |
71 | 18 | this.visibleVertices = g.getVertices(); |
72 | 18 | this.dontmove = new HashSet(); |
73 | 18 | } |
74 | ||
75 | /** | |
76 | * The set of vertices that have been locked. When running layout, it is | |
77 | * important to check | |
78 | * | |
79 | * <pre> | |
80 | * if (dontmove( v )) { ... } | |
81 | * </pre> | |
82 | * | |
83 | * @return whether this vertex may be legally moved or not | |
84 | * @deprecated As of version 1.7.5, superseded by <code>Layout.isLocked(Vertex)</code>. | |
85 | */ | |
86 | public boolean dontMove(Vertex v) { | |
87 | 0 | return isLocked(v); |
88 | } | |
89 | ||
90 | public boolean isLocked(Vertex v) | |
91 | { | |
92 | 486652 | return dontmove.contains(v); |
93 | } | |
94 | ||
95 | public Iterator getVertexIterator() | |
96 | { | |
97 | 0 | return getVisibleVertices().iterator(); |
98 | } | |
99 | ||
100 | /** | |
101 | * Initializer, calls <tt>intialize_local</tt> and <tt>initializeLocations</tt> | |
102 | * to start construction process. | |
103 | */ | |
104 | public void initialize(Dimension size) | |
105 | { | |
106 | 18 | initialize(size, new RandomVertexLocationDecorator(size)); |
107 | 18 | } |
108 | ||
109 | public void initialize(Dimension size, VertexLocationFunction v_locations) | |
110 | { | |
111 | 18 | this.currentSize = size; |
112 | 18 | this.vertex_locations = v_locations; |
113 | 18 | initialize_local(); |
114 | 18 | initializeLocations(); |
115 | 18 | } |
116 | ||
117 | /** | |
118 | * Initializes all local information, and is called immediately within the | |
119 | * <tt>initialize()</tt> process. The user is responsible for overriding | |
120 | * this method to do any construction that may be necessary: for example, | |
121 | * to initialize local per-edge or graph-wide data. | |
122 | * | |
123 | */ | |
124 | 0 | protected void initialize_local() {} |
125 | ||
126 | /** | |
127 | * may be overridden to do something after initializeLocations call | |
128 | * | |
129 | */ | |
130 | 0 | protected void postInitialize() {} |
131 | ||
132 | /** | |
133 | * Initializes the local information on a single vertex. The user is | |
134 | * responsible for overriding this method to do any vertex-level | |
135 | * construction that may be necessary: for example, to attach vertex-level | |
136 | * information to each vertex. | |
137 | */ | |
138 | protected abstract void initialize_local_vertex(Vertex v); | |
139 | ||
140 | private Object key; | |
141 | ||
142 | private Set visibleVertices; | |
143 | private Set visibleEdges; | |
144 | ||
145 | /** | |
146 | * Returns a visualization-specific key (that is, specific both to this | |
147 | * instance and <tt>AbstractLayout</tt>) that can be used to access | |
148 | * UserData related to the <tt>AbstractLayout</tt>. | |
149 | */ | |
150 | public Object getBaseKey() { | |
151 | 1438896 | if (key == null) |
152 | 18 | key = new Pair(this, BASE_KEY); |
153 | 1438896 | return key; |
154 | } | |
155 | ||
156 | /** | |
157 | * This method calls <tt>initialize_local_vertex</tt> for each vertex, | |
158 | * and also adds initial coordinate information for each vertex. (The | |
159 | * vertex's initial location is set by calling <tt>initializeLocation</tt>. | |
160 | */ | |
161 | protected void initializeLocations() { | |
162 | try { | |
163 | 20 | for (Iterator iter = baseGraph.getVertices().iterator(); |
164 | 1020 | iter.hasNext(); |
165 | ) { | |
166 | 1000 | Vertex v = (Vertex) iter.next(); |
167 | ||
168 | 1000 | Coordinates coord = (Coordinates) v.getUserDatum(getBaseKey()); |
169 | 1000 | if (coord == null) { |
170 | 900 | coord = new Coordinates(); |
171 | 900 | v.addUserDatum(getBaseKey(), coord, UserData.REMOVE); |
172 | } | |
173 | 1000 | if (!dontmove.contains(v)) |
174 | 1000 | initializeLocation(v, coord, currentSize); |
175 | 1000 | initialize_local_vertex(v); |
176 | } | |
177 | 0 | } catch(ConcurrentModificationException cme) { |
178 | 0 | initializeLocations(); |
179 | 20 | } |
180 | ||
181 | 20 | } |
182 | ||
183 | /* ------------------------- */ | |
184 | ||
185 | /** | |
186 | * Sets random locations for a vertex within the dimensions of the space. | |
187 | * If you want to initialize in some different way, override this method. | |
188 | * | |
189 | * @param coord | |
190 | * @param d | |
191 | */ | |
192 | protected void initializeLocation( | |
193 | Vertex v, | |
194 | Coordinates coord, | |
195 | Dimension d) { | |
196 | 1000 | coord.setLocation(vertex_locations.getLocation(v)); |
197 | 1000 | } |
198 | ||
199 | /** | |
200 | * {@inheritDoc}By default, an <tt>AbstractLayout</tt> returns null for | |
201 | * its status. | |
202 | */ | |
203 | public String getStatus() { | |
204 | 0 | return null; |
205 | } | |
206 | ||
207 | /** | |
208 | * Implementors must override this method in order to create a Layout. If | |
209 | * the Layout is the sort that only calculates locations once, this method | |
210 | * may be overridden with an empty method. | |
211 | * <p> | |
212 | * Note that "locked" vertices are not to be moved; however, it is the | |
213 | * policy of the visualization to decide how to handle them, and what to do | |
214 | * with the vertices around them. Prototypical code might include a | |
215 | * clipping like | |
216 | * | |
217 | * <pre> | |
218 | * for (Iterator i = getVertices().iterator(); i.hasNext() ) { Vertex v = (Vertex) i.next(); if (! dontmove.contains( v ) ) { ... // handle the node } else { // ignore the node } } | |
219 | * </pre> | |
220 | * | |
221 | * @see Layout#advancePositions() | |
222 | */ | |
223 | public abstract void advancePositions(); | |
224 | ||
225 | /** | |
226 | * Accessor for the graph that represets all visible vertices. <b>Warning: | |
227 | * </b> This graph consists of vertices that are equivalent to, but are <b> | |
228 | * not the same as</b> the vertices in <tt>getGraph()</tt>, nor the | |
229 | * vertices in <tt>getAllVertices()</tt>. Rather, it returns the | |
230 | * vertices and edges that were passed in during a call to <tt>applyFilter</tt>. | |
231 | * The call <tt>getVisibleGraph().getVertices()</tt>, is almost | |
232 | * indubitably incorrect. | |
233 | * <p> | |
234 | * | |
235 | * @return the current visible graph. | |
236 | * @see #getVisibleEdges | |
237 | * @see #getVisibleVertices | |
238 | */ | |
239 | protected Graph getVisibleGraph() { | |
240 | 10 | return visibleGraph; |
241 | } | |
242 | ||
243 | /** | |
244 | * Returns the current size of the visualization space, accoring to the | |
245 | * last call to resize(). | |
246 | * | |
247 | * @return the current size of the screen | |
248 | */ | |
249 | public Dimension getCurrentSize() { | |
250 | 32783 | return currentSize; |
251 | } | |
252 | ||
253 | /** | |
254 | * Utility method, gets a single vertex from this edge. The utility's | |
255 | * implementation is to get the iterator from the edge's <tt>getIncidentVertices()</tt> | |
256 | * and then return the first element. | |
257 | */ | |
258 | protected Vertex getAVertex(Edge e) { | |
259 | 0 | Vertex v = (Vertex) e.getIncidentVertices().iterator().next(); |
260 | 0 | return v; |
261 | } | |
262 | ||
263 | /** | |
264 | * Returns the Coordinates object that stores the vertex' x and y location. | |
265 | * | |
266 | * @param v | |
267 | * A Vertex that is a part of the Graph being visualized. | |
268 | * @return A Coordinates object with x and y locations. | |
269 | */ | |
270 | public Coordinates getCoordinates(ArchetypeVertex v) { | |
271 | 1367388 | return (Coordinates) v.getUserDatum(getBaseKey()); |
272 | } | |
273 | ||
274 | /** | |
275 | * Returns the x coordinate of the vertex from the Coordinates object. | |
276 | * in most cases you will be better off calling getLocation(Vertex v); | |
277 | * @see edu.uci.ics.jung.visualization.Layout#getX(edu.uci.ics.jung.graph.Vertex) | |
278 | */ | |
279 | public double getX(Vertex v) { | |
280 | 34804 | Coordinates coords = (Coordinates)v.getUserDatum(getBaseKey()); |
281 | 34804 | return coords.getX(); |
282 | } | |
283 | ||
284 | /** | |
285 | * Returns the y coordinate of the vertex from the Coordinates object. | |
286 | * In most cases you will be better off calling getLocation(Vertex v) | |
287 | * @see edu.uci.ics.jung.visualization.Layout#getX(edu.uci.ics.jung.graph.Vertex) | |
288 | */ | |
289 | public double getY(Vertex v) { | |
290 | 34804 | Coordinates coords = (Coordinates)v.getUserDatum(getBaseKey()); |
291 | 34804 | return coords.getY(); |
292 | } | |
293 | ||
294 | /** | |
295 | * @param v a Vertex of interest | |
296 | * @return the location point of the supplied vertex | |
297 | */ | |
298 | public Point2D getLocation(ArchetypeVertex v) { | |
299 | 1355568 | return getCoordinates(v); |
300 | } | |
301 | ||
302 | /** | |
303 | * When a visualization is resized, it presumably wants to fix the | |
304 | * locations of the vertices and possibly to reinitialize its data. The | |
305 | * current method calls <tt>initializeLocations</tt> followed by <tt>initialize_local</tt>. | |
306 | * TODO: A better implementation wouldn't destroy the current information, | |
307 | * but would either scale the current visualization, or move the nodes | |
308 | * toward the new center. | |
309 | */ | |
310 | public void resize(Dimension size) { | |
311 | // are we initialized yet? | |
312 | ||
313 | 2 | if (currentSize == null) { |
314 | 0 | currentSize = size; |
315 | 0 | return; |
316 | } | |
317 | ||
318 | Dimension oldSize; | |
319 | 2 | synchronized (currentSize) { |
320 | 2 | if (currentSize.equals(size)) |
321 | 0 | return; |
322 | 2 | oldSize = currentSize; |
323 | 2 | this.currentSize = size; |
324 | 2 | } |
325 | ||
326 | 2 | int xOffset = (size.width - oldSize.width) / 2; |
327 | 2 | int yOffset = (size.height - oldSize.height) / 2; |
328 | ||
329 | // now, move each vertex to be at the new screen center | |
330 | while(true) { | |
331 | try { | |
332 | 2 | for (Iterator iter = getGraph().getVertices().iterator(); |
333 | 102 | iter.hasNext(); |
334 | ) { | |
335 | 100 | Vertex e = (Vertex) iter.next(); |
336 | 100 | offsetVertex(e, xOffset, yOffset); |
337 | } | |
338 | 2 | break; |
339 | 0 | } catch(ConcurrentModificationException cme) { |
340 | 0 | } |
341 | } | |
342 | ||
343 | // optionally, we may want to restart | |
344 | 2 | } |
345 | ||
346 | /** | |
347 | * @param v | |
348 | * @param xOffset | |
349 | * @param yOffset | |
350 | */ | |
351 | protected void offsetVertex(Vertex v, double xOffset, double yOffset) { | |
352 | 100 | Coordinates c = getCoordinates(v); |
353 | 100 | c.add(xOffset, yOffset); |
354 | 100 | forceMove(v, c.getX(), c.getY()); |
355 | 100 | } |
356 | ||
357 | /** | |
358 | * @see Layout#restart() | |
359 | */ | |
360 | public void restart() { | |
361 | 2 | initialize_local(); |
362 | 2 | initializeLocations(); |
363 | 2 | } |
364 | ||
365 | /** | |
366 | * Gets the vertex nearest to the location of the (x,y) location selected. | |
367 | * Calls the longer form of the call. | |
368 | * @deprecated Use PickSupport instead | |
369 | */ | |
370 | public Vertex getVertex(double x, double y) { | |
371 | 0 | return getVertex(x, y, Math.sqrt(Double.MAX_VALUE - 1000)); |
372 | } | |
373 | ||
374 | /** | |
375 | * Gets the vertex nearest to the location of the (x,y) location selected, | |
376 | * within a distance of <tt>maxDistance</tt>. Iterates through all | |
377 | * visible vertices and checks their distance from the click. Override this | |
378 | * method to provde a more efficient implementation. | |
379 | * @deprecated Use PickSupport instead | |
380 | */ | |
381 | public Vertex getVertex(double x, double y, double maxDistance) { | |
382 | ||
383 | 0 | double minDistance = maxDistance * maxDistance; |
384 | 0 | Vertex closest = null; |
385 | while(true) { | |
386 | try { | |
387 | 0 | for (Iterator iter = getVisibleVertices().iterator(); |
388 | 0 | iter.hasNext(); |
389 | ) { | |
390 | 0 | Vertex v = (Vertex) iter.next(); |
391 | 0 | Point2D p = getLocation(v); |
392 | 0 | double dx = p.getX() - x; |
393 | 0 | double dy = p.getY() - y; |
394 | 0 | double dist = dx * dx + dy * dy; |
395 | 0 | if (dist < minDistance) { |
396 | 0 | minDistance = dist; |
397 | 0 | closest = v; |
398 | } | |
399 | } | |
400 | 0 | break; |
401 | 0 | } catch(ConcurrentModificationException cme) {} |
402 | } | |
403 | 0 | return closest; |
404 | } | |
405 | ||
406 | /** | |
407 | * Gets the edge nearest to the location of the (x,y) location selected. | |
408 | * Calls the longer form of the call. | |
409 | * @deprecated Use PickSupport instead | |
410 | */ | |
411 | public Edge getEdge(double x, double y) { | |
412 | 0 | return getEdge(x, y, Math.sqrt(Double.MAX_VALUE - 1000)); |
413 | } | |
414 | ||
415 | /** | |
416 | * Gets the edge nearest to the location of the (x,y) location selected, | |
417 | * within a distance of <tt>maxDistance</tt>, Iterates through all | |
418 | * visible edges and checks their distance from the click. Override this | |
419 | * method to provide a more efficient implementation. | |
420 | * @deprecated Use PickSupport instead | |
421 | * @param x | |
422 | * @param y | |
423 | * @param maxDistance | |
424 | * @return Edge closest to the click. | |
425 | */ | |
426 | public Edge getEdge(double x, double y, double maxDistance) { | |
427 | ||
428 | 0 | double minDistance = maxDistance * maxDistance; |
429 | 0 | Edge closest = null; |
430 | while(true) { | |
431 | try { | |
432 | 0 | for (Iterator iter = getVisibleEdges().iterator(); iter.hasNext();) { |
433 | 0 | Edge e = (Edge) iter.next(); |
434 | // if anyone uses a hyperedge, this is too complex. | |
435 | 0 | if (e.numVertices() != 2) |
436 | 0 | continue; |
437 | // Could replace all this set stuff with getFrom_internal() etc. | |
438 | 0 | Set vertices = e.getIncidentVertices(); |
439 | 0 | Iterator vertexIterator = vertices.iterator(); |
440 | 0 | Vertex v1 = (Vertex) vertexIterator.next(); |
441 | 0 | Vertex v2 = (Vertex) vertexIterator.next(); |
442 | // Get coords | |
443 | 0 | Point2D p1 = getLocation(v1); |
444 | 0 | Point2D p2 = getLocation(v2); |
445 | 0 | double x1 = p1.getX(); |
446 | 0 | double y1 = p1.getY(); |
447 | 0 | double x2 = p2.getX(); |
448 | 0 | double y2 = p2.getY(); |
449 | // Calculate location on line closest to (x,y) | |
450 | // First, check that v1 and v2 are not coincident. | |
451 | 0 | if (x1 == x2 && y1 == y2) |
452 | 0 | continue; |
453 | 0 | double b = |
454 | ((y - y1) * (y2 - y1) + (x - x1) * (x2 - x1)) | |
455 | / ((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1)); | |
456 | // | |
457 | double distance2; // square of the distance | |
458 | 0 | if (b <= 0) |
459 | 0 | distance2 = (x - x1) * (x - x1) + (y - y1) * (y - y1); |
460 | 0 | else if (b >= 1) |
461 | 0 | distance2 = (x - x2) * (x - x2) + (y - y2) * (y - y2); |
462 | else { | |
463 | 0 | double x3 = x1 + b * (x2 - x1); |
464 | 0 | double y3 = y1 + b * (y2 - y1); |
465 | 0 | distance2 = (x - x3) * (x - x3) + (y - y3) * (y - y3); |
466 | } | |
467 | ||
468 | 0 | if (distance2 < minDistance) { |
469 | 0 | minDistance = distance2; |
470 | 0 | closest = e; |
471 | } | |
472 | } | |
473 | 0 | break; |
474 | 0 | } catch(ConcurrentModificationException cme) {} |
475 | } | |
476 | 0 | return closest; |
477 | } | |
478 | ||
479 | /** | |
480 | * Accessor for the graph that represets all vertices. | |
481 | * | |
482 | * @return the graph that contains all vertices. | |
483 | */ | |
484 | public Graph getGraph() { | |
485 | 2311 | return baseGraph; |
486 | } | |
487 | ||
488 | /** | |
489 | * Returns the set of edges from the original <tt>getGraph</tt> that are | |
490 | * now visible. These edges are equivalent to the ones passed in from the | |
491 | * <tt>Graph</tt> argument to <tt>applyFilter()</tt>. | |
492 | */ | |
493 | public Set getVisibleEdges() { | |
494 | 248 | return visibleEdges; |
495 | } | |
496 | ||
497 | /** | |
498 | * Returns the set of vertices from the original <tt>getGraph</tt> that | |
499 | * are now visible. These vertices are equivalent to the ones passed in | |
500 | * from the <tt>Graph</tt> argument to <tt>applyFilter()</tt>. | |
501 | */ | |
502 | public Set getVisibleVertices() { | |
503 | 10395 | return visibleVertices; |
504 | } | |
505 | ||
506 | /** | |
507 | * Forcibly moves a vertex to the (x,y) location by setting its x and y | |
508 | * locations to the inputted location. Does not add the vertex to the | |
509 | * "dontmove" list, and (in the default implementation) does not make any | |
510 | * adjustments to the rest of the graph. | |
511 | */ | |
512 | public void forceMove(Vertex picked, double x, double y) { | |
513 | 100 | Coordinates coord = getCoordinates(picked); |
514 | 100 | coord.setX(x); |
515 | 100 | coord.setY(y); |
516 | 100 | fireStateChanged(); |
517 | 100 | } |
518 | ||
519 | /** | |
520 | * Adds the vertex to the DontMove list | |
521 | */ | |
522 | public void lockVertex(Vertex v) { | |
523 | 0 | dontmove.add(v); |
524 | 0 | } |
525 | ||
526 | /** | |
527 | * Removes the vertex from the DontMove list | |
528 | */ | |
529 | public void unlockVertex(Vertex v) { | |
530 | 0 | dontmove.remove(v); |
531 | 0 | } |
532 | ||
533 | /** | |
534 | * Applies the filter to the current graph. The default implementation | |
535 | * merely makes fewer vertices available to the <tt>getVisibleVertices</tt> | |
536 | * and <tt>getVisibleEdges</tt> methods. | |
537 | * | |
538 | * @see Layout#applyFilter(Graph g) | |
539 | */ | |
540 | public void applyFilter(Graph g) { | |
541 | 2 | this.visibleGraph = g; |
542 | 2 | this.visibleVertices = |
543 | GraphUtils.getEqualVertices(g.getVertices(), baseGraph); | |
544 | 2 | this.visibleEdges = |
545 | GraphUtils.getEqualEdges(g.getEdges(), baseGraph); | |
546 | 2 | } |
547 | ||
548 | /** | |
549 | * Adds a <code>ChangeListener</code>. | |
550 | * @param l the listener to be added | |
551 | */ | |
552 | public void addChangeListener(ChangeListener l) { | |
553 | 0 | changeSupport.addChangeListener(l); |
554 | 0 | } |
555 | ||
556 | /** | |
557 | * Removes a ChangeListener. | |
558 | * @param l the listener to be removed | |
559 | */ | |
560 | public void removeChangeListener(ChangeListener l) { | |
561 | 0 | changeSupport.removeChangeListener(l); |
562 | 0 | } |
563 | ||
564 | /** | |
565 | * Returns an array of all the <code>ChangeListener</code>s added | |
566 | * with addChangeListener(). | |
567 | * | |
568 | * @return all of the <code>ChangeListener</code>s added or an empty | |
569 | * array if no listeners have been added | |
570 | */ | |
571 | public ChangeListener[] getChangeListeners() { | |
572 | 0 | return changeSupport.getChangeListeners(); |
573 | } | |
574 | ||
575 | /** | |
576 | * Notifies all listeners that have registered interest for | |
577 | * notification on this event type. The event instance | |
578 | * is lazily created. | |
579 | * The primary listeners will be views that need to be repainted | |
580 | * because of changes in this model instance | |
581 | * @see EventListenerList | |
582 | */ | |
583 | public void fireStateChanged() { | |
584 | 100 | changeSupport.fireStateChanged(); |
585 | 100 | } |
586 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |