Line | Hits | Source |
---|---|---|
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; | |
11 | ||
12 | import java.util.ConcurrentModificationException; | |
13 | import java.util.Iterator; | |
14 | import java.util.Set; | |
15 | import java.util.Vector; | |
16 | ||
17 | import cern.colt.matrix.DoubleMatrix1D; | |
18 | import cern.colt.matrix.impl.DenseDoubleMatrix1D; | |
19 | import edu.uci.ics.jung.graph.Graph; | |
20 | import edu.uci.ics.jung.graph.Vertex; | |
21 | import edu.uci.ics.jung.utils.Pair; | |
22 | import edu.uci.ics.jung.utils.UserData; | |
23 | ||
24 | /** | |
25 | * Implements a self-organizing map layout algorithm, based on Meyer's | |
26 | * self-organizing graph methods. | |
27 | * | |
28 | * @author Yan Biao Boey | |
29 | */ | |
30 | public class ISOMLayout extends AbstractLayout { | |
31 | ||
32 | 0 | private static final Object ISOM_KEY = |
33 | "edu.uci.ics.jung.ISOM_Visualization_Key"; | |
34 | ||
35 | 0 | private Object key = null; |
36 | public Object getIsomKey() { | |
37 | 0 | if (key == null) |
38 | 0 | key = new Pair(this, ISOM_KEY); |
39 | 0 | return key; |
40 | } | |
41 | ||
42 | private int maxEpoch; | |
43 | private int epoch; | |
44 | ||
45 | private int radiusConstantTime; | |
46 | private int radius; | |
47 | private int minRadius; | |
48 | ||
49 | private double adaption; | |
50 | private double initialAdaption; | |
51 | private double minAdaption; | |
52 | ||
53 | protected GraphElementAccessor elementAccessor; | |
54 | ||
55 | // private double factor; | |
56 | private double coolingFactor; | |
57 | ||
58 | //private double temperature; | |
59 | //private int initialJumpRadius; | |
60 | //private int jumpRadius; | |
61 | ||
62 | //private int delay; | |
63 | ||
64 | //private ISOMVertexData temp; | |
65 | private Vector queue; | |
66 | 0 | private String status = null; |
67 | ||
68 | /** | |
69 | * Returns the current number of epochs and execution status, as a string. | |
70 | */ | |
71 | public String getStatus() { | |
72 | 0 | return status; |
73 | } | |
74 | ||
75 | // private boolean trace; | |
76 | // private boolean done; | |
77 | ||
78 | public ISOMLayout(Graph g) { | |
79 | 0 | super(g); |
80 | 0 | elementAccessor = new RadiusGraphElementAccessor(this); |
81 | 0 | queue = new Vector(); |
82 | // trace = false; | |
83 | 0 | } |
84 | ||
85 | protected void initialize_local() { | |
86 | // done = false; | |
87 | ||
88 | 0 | maxEpoch = 2000; |
89 | 0 | epoch = 1; |
90 | ||
91 | 0 | radiusConstantTime = 100; |
92 | 0 | radius = 5; |
93 | 0 | minRadius = 1; |
94 | ||
95 | 0 | initialAdaption = 90.0D / 100.0D; |
96 | 0 | adaption = initialAdaption; |
97 | 0 | minAdaption = 0; |
98 | ||
99 | //factor = 0; //Will be set later on | |
100 | 0 | coolingFactor = 2; |
101 | ||
102 | //temperature = 0.03; | |
103 | //initialJumpRadius = 100; | |
104 | //jumpRadius = initialJumpRadius; | |
105 | ||
106 | //delay = 100; | |
107 | 0 | } |
108 | ||
109 | /** | |
110 | * (non-Javadoc) | |
111 | * @see edu.uci.ics.jung.visualization.AbstractLayout#initialize_local_vertex(edu.uci.ics.jung.graph.Vertex) | |
112 | */ | |
113 | protected void initialize_local_vertex(Vertex v) { | |
114 | 0 | ISOMVertexData vd = getISOMVertexData(v); |
115 | 0 | if (vd == null) { |
116 | 0 | vd = new ISOMVertexData(); |
117 | 0 | v.addUserDatum(getIsomKey(), vd, UserData.REMOVE); |
118 | } | |
119 | 0 | vd.visited = false; |
120 | 0 | } |
121 | ||
122 | /** | |
123 | * Advances the current positions of the graph elements. | |
124 | */ | |
125 | public void advancePositions() { | |
126 | 0 | status = "epoch: " + epoch + "; "; |
127 | 0 | if (epoch < maxEpoch) { |
128 | 0 | adjust(); |
129 | 0 | updateParameters(); |
130 | 0 | status += " status: running"; |
131 | ||
132 | } else { | |
133 | 0 | status += "adaption: " + adaption + "; "; |
134 | 0 | status += "status: done"; |
135 | // done = true; | |
136 | } | |
137 | 0 | } |
138 | ||
139 | ISOMVertexData tempISOM; | |
140 | Coordinates tempXYD; | |
141 | ||
142 | private synchronized void adjust() { | |
143 | //Generate random position in graph space | |
144 | 0 | tempISOM = new ISOMVertexData(); |
145 | 0 | tempXYD = new Coordinates(); |
146 | ||
147 | // creates a new XY data location | |
148 | 0 | tempXYD.setX(10 + Math.random() * getCurrentSize().getWidth()); |
149 | 0 | tempXYD.setY(10 + Math.random() * getCurrentSize().getHeight()); |
150 | ||
151 | //Get closest vertex to random position | |
152 | 0 | Vertex winner = elementAccessor.getVertex(tempXYD.getX(), tempXYD.getY()); |
153 | ||
154 | while(true) { | |
155 | try { | |
156 | 0 | for (Iterator iter = getVisibleVertices().iterator(); |
157 | 0 | iter.hasNext(); |
158 | ) { | |
159 | 0 | Vertex v = (Vertex) iter.next(); |
160 | 0 | ISOMVertexData ivd = getISOMVertexData(v); |
161 | 0 | ivd.distance = 0; |
162 | 0 | ivd.visited = false; |
163 | } | |
164 | 0 | break; |
165 | 0 | } catch(ConcurrentModificationException cme) {} |
166 | } | |
167 | 0 | adjustVertex(winner); |
168 | 0 | } |
169 | ||
170 | private synchronized void updateParameters() { | |
171 | 0 | epoch++; |
172 | 0 | double factor = Math.exp(-1 * coolingFactor * (1.0 * epoch / maxEpoch)); |
173 | 0 | adaption = Math.max(minAdaption, factor * initialAdaption); |
174 | //jumpRadius = (int) factor * jumpRadius; | |
175 | //temperature = factor * temperature; | |
176 | 0 | if ((radius > minRadius) && (epoch % radiusConstantTime == 0)) { |
177 | 0 | radius--; |
178 | } | |
179 | 0 | } |
180 | ||
181 | private synchronized void adjustVertex(Vertex v) { | |
182 | 0 | queue.removeAllElements(); |
183 | 0 | ISOMVertexData ivd = getISOMVertexData(v); |
184 | 0 | ivd.distance = 0; |
185 | 0 | ivd.visited = true; |
186 | 0 | queue.add(v); |
187 | Vertex current; | |
188 | ||
189 | 0 | while (!queue.isEmpty()) { |
190 | 0 | current = (Vertex) queue.remove(0); |
191 | 0 | ISOMVertexData currData = getISOMVertexData(current); |
192 | 0 | Coordinates currXYData = getCoordinates(current); |
193 | ||
194 | 0 | double dx = tempXYD.getX() - currXYData.getX(); |
195 | 0 | double dy = tempXYD.getY() - currXYData.getY(); |
196 | 0 | double factor = adaption / Math.pow(2, currData.distance); |
197 | ||
198 | 0 | currXYData.addX(factor * dx); |
199 | 0 | currXYData.addY(factor * dy); |
200 | ||
201 | 0 | if (currData.distance < radius) { |
202 | 0 | Set s = current.getNeighbors(); |
203 | while(true) { | |
204 | try { | |
205 | 0 | for (Iterator iter = s.iterator(); iter.hasNext();) { |
206 | 0 | Vertex child = (Vertex) iter.next(); |
207 | 0 | ISOMVertexData childData = getISOMVertexData(child); |
208 | 0 | if (childData != null && !childData.visited) { |
209 | 0 | childData.visited = true; |
210 | 0 | childData.distance = currData.distance + 1; |
211 | 0 | queue.addElement(child); |
212 | } | |
213 | } | |
214 | 0 | break; |
215 | 0 | } catch(ConcurrentModificationException cme) {} |
216 | } | |
217 | } | |
218 | } | |
219 | 0 | } |
220 | ||
221 | public ISOMVertexData getISOMVertexData(Vertex v) { | |
222 | 0 | return (ISOMVertexData) (v.getUserDatum(getIsomKey())); |
223 | } | |
224 | ||
225 | /** | |
226 | * This one is an incremental visualization. | |
227 | * @return <code>true</code> is the layout algorithm is incremental, <code>false</code> otherwise | |
228 | */ | |
229 | public boolean isIncremental() { | |
230 | 0 | return true; |
231 | } | |
232 | ||
233 | /** | |
234 | * For now, we pretend it never finishes. | |
235 | * @return <code>true</code> is the increments are done, <code>false</code> otherwise | |
236 | */ | |
237 | public boolean incrementsAreDone() { | |
238 | 0 | return false; |
239 | } | |
240 | ||
241 | public static class ISOMVertexData { | |
242 | public DoubleMatrix1D disp; | |
243 | ||
244 | int distance; | |
245 | boolean visited; | |
246 | ||
247 | public ISOMVertexData() { | |
248 | initialize(); | |
249 | } | |
250 | ||
251 | public void initialize() { | |
252 | disp = new DenseDoubleMatrix1D(2); | |
253 | ||
254 | distance = 0; | |
255 | visited = false; | |
256 | } | |
257 | ||
258 | public double getXDisp() { | |
259 | return disp.get(0); | |
260 | } | |
261 | ||
262 | public double getYDisp() { | |
263 | return disp.get(1); | |
264 | } | |
265 | ||
266 | public void setDisp(double x, double y) { | |
267 | disp.set(0, x); | |
268 | disp.set(1, y); | |
269 | } | |
270 | ||
271 | public void incrementDisp(double x, double y) { | |
272 | disp.set(0, disp.get(0) + x); | |
273 | disp.set(1, disp.get(1) + y); | |
274 | } | |
275 | ||
276 | public void decrementDisp(double x, double y) { | |
277 | disp.set(0, disp.get(0) - x); | |
278 | disp.set(1, disp.get(1) - y); | |
279 | } | |
280 | } | |
281 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |