|
76
|
1 package sample.graph;
|
|
|
2
|
|
|
3 /*
|
|
|
4 * Copyright (c) 2003 Sun Microsystems, Inc. All Rights Reserved.
|
|
|
5 *
|
|
|
6 * Redistribution and use in source and binary forms, with or without
|
|
|
7 * modification, are permitted provided that the following conditions
|
|
|
8 * are met:
|
|
|
9 *
|
|
|
10 * -Redistributions of source code must retain the above copyright
|
|
|
11 * notice, this list of conditions and the following disclaimer.
|
|
|
12 *
|
|
|
13 * -Redistribution in binary form must reproduct the above copyright
|
|
|
14 * notice, this list of conditions and the following disclaimer in
|
|
|
15 * the documentation and/or other materials provided with the distribution.
|
|
|
16 *
|
|
|
17 * Neither the name of Sun Microsystems, Inc. or the names of contributors
|
|
|
18 * may be used to endorse or promote products derived from this software
|
|
|
19 * without specific prior written permission.
|
|
|
20 *
|
|
|
21 * This software is provided "AS IS," without a warranty of any kind. ALL
|
|
|
22 * EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, INCLUDING
|
|
|
23 * ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE
|
|
|
24 * OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN AND ITS LICENSORS SHALL NOT
|
|
|
25 * BE LIABLE FOR ANY DAMAGES OR LIABILITIES SUFFERED BY LICENSEE AS A RESULT
|
|
|
26 * OF OR RELATING TO USE, MODIFICATION OR DISTRIBUTION OF THE SOFTWARE OR ITS
|
|
|
27 * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR ANY LOST
|
|
|
28 * REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL,
|
|
|
29 * INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY
|
|
|
30 * OF LIABILITY, ARISING OUT OF THE USE OF OR INABILITY TO USE SOFTWARE, EVEN
|
|
|
31 * IF SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
|
|
|
32 *
|
|
|
33 * You acknowledge that Software is not designed, licensed or intended for
|
|
|
34 * use in the design, construction, operation or maintenance of any nuclear
|
|
|
35 * facility.
|
|
|
36 */
|
|
|
37
|
|
|
38 /*
|
|
|
39 * @(#)Graph.java 1.13 03/01/23
|
|
|
40 */
|
|
|
41
|
|
|
42 import java.util.*;
|
|
|
43 import java.awt.*;
|
|
|
44 import java.applet.Applet;
|
|
|
45 import java.awt.event.*;
|
|
|
46
|
|
|
47
|
|
|
48 class Node {
|
|
|
49 double x;
|
|
|
50 double y;
|
|
|
51
|
|
|
52 double dx;
|
|
|
53 double dy;
|
|
|
54
|
|
|
55 boolean fixed;
|
|
|
56
|
|
|
57 String lbl;
|
|
|
58 }
|
|
|
59
|
|
|
60
|
|
|
61 class Edge {
|
|
|
62 int from;
|
|
|
63 int to;
|
|
|
64
|
|
|
65 double len;
|
|
|
66 }
|
|
|
67
|
|
|
68
|
|
|
69 class GraphPanel extends Panel
|
|
|
70 implements Runnable, MouseListener, MouseMotionListener {
|
|
|
71 Graph graph;
|
|
|
72 int nnodes;
|
|
|
73 Node nodes[] = new Node[100];
|
|
|
74
|
|
|
75 int nedges;
|
|
|
76 Edge edges[] = new Edge[200];
|
|
|
77
|
|
|
78 Thread relaxer;
|
|
|
79 boolean stress;
|
|
|
80 boolean random;
|
|
|
81
|
|
|
82 GraphPanel(Graph graph) {
|
|
|
83 this.graph = graph;
|
|
|
84 addMouseListener(this);
|
|
|
85 }
|
|
|
86
|
|
|
87 int findNode(String lbl) {
|
|
|
88 for (int i = 0 ; i < nnodes ; i++) {
|
|
|
89 if (nodes[i].lbl.equals(lbl)) {
|
|
|
90 return i;
|
|
|
91 }
|
|
|
92 }
|
|
|
93 return addNode(lbl);
|
|
|
94 }
|
|
|
95 int addNode(String lbl) {
|
|
|
96 Node n = new Node();
|
|
|
97 n.x = 10 + 380*Math.random();
|
|
|
98 n.y = 10 + 380*Math.random();
|
|
|
99 n.lbl = lbl;
|
|
|
100 nodes[nnodes] = n;
|
|
|
101 return nnodes++;
|
|
|
102 }
|
|
|
103 void addEdge(String from, String to, int len) {
|
|
|
104 Edge e = new Edge();
|
|
|
105 e.from = findNode(from);
|
|
|
106 e.to = findNode(to);
|
|
|
107 e.len = len;
|
|
|
108 edges[nedges++] = e;
|
|
|
109 }
|
|
|
110
|
|
|
111 public void run() {
|
|
|
112 Thread me = Thread.currentThread();
|
|
|
113 while (relaxer == me) {
|
|
|
114 relax();
|
|
|
115 if (random && (Math.random() < 0.03)) {
|
|
|
116 Node n = nodes[(int)(Math.random() * nnodes)];
|
|
|
117 if (!n.fixed) {
|
|
|
118 n.x += 100*Math.random() - 50;
|
|
|
119 n.y += 100*Math.random() - 50;
|
|
|
120 }
|
|
|
121 graph.play(graph.getCodeBase(), "audio/drip.au");
|
|
|
122 }
|
|
|
123 try {
|
|
|
124 Thread.sleep(100);
|
|
|
125 } catch (InterruptedException e) {
|
|
|
126 break;
|
|
|
127 }
|
|
|
128 }
|
|
|
129 }
|
|
|
130
|
|
|
131 synchronized void relax() {
|
|
|
132 for (int i = 0 ; i < nedges ; i++) {
|
|
|
133 Edge e = edges[i];
|
|
|
134 double vx = nodes[e.to].x - nodes[e.from].x;
|
|
|
135 double vy = nodes[e.to].y - nodes[e.from].y;
|
|
|
136 double len = Math.sqrt(vx * vx + vy * vy);
|
|
|
137 len = (len == 0) ? .0001 : len;
|
|
|
138 double f = (edges[i].len - len) / (len * 3);
|
|
|
139 double dx = f * vx;
|
|
|
140 double dy = f * vy;
|
|
|
141
|
|
|
142 nodes[e.to].dx += dx;
|
|
|
143 nodes[e.to].dy += dy;
|
|
|
144 nodes[e.from].dx += -dx;
|
|
|
145 nodes[e.from].dy += -dy;
|
|
|
146 }
|
|
|
147
|
|
|
148 for (int i = 0 ; i < nnodes ; i++) {
|
|
|
149 Node n1 = nodes[i];
|
|
|
150 double dx = 0;
|
|
|
151 double dy = 0;
|
|
|
152
|
|
|
153 for (int j = 0 ; j < nnodes ; j++) {
|
|
|
154 if (i == j) {
|
|
|
155 continue;
|
|
|
156 }
|
|
|
157 Node n2 = nodes[j];
|
|
|
158 double vx = n1.x - n2.x;
|
|
|
159 double vy = n1.y - n2.y;
|
|
|
160 double len = vx * vx + vy * vy;
|
|
|
161 if (len == 0) {
|
|
|
162 dx += Math.random();
|
|
|
163 dy += Math.random();
|
|
|
164 } else if (len < 100*100) {
|
|
|
165 dx += vx / len;
|
|
|
166 dy += vy / len;
|
|
|
167 }
|
|
|
168 }
|
|
|
169 double dlen = dx * dx + dy * dy;
|
|
|
170 if (dlen > 0) {
|
|
|
171 dlen = Math.sqrt(dlen) / 2;
|
|
|
172 n1.dx += dx / dlen;
|
|
|
173 n1.dy += dy / dlen;
|
|
|
174 }
|
|
|
175 }
|
|
|
176
|
|
|
177 Dimension d = getSize();
|
|
|
178 for (int i = 0 ; i < nnodes ; i++) {
|
|
|
179 Node n = nodes[i];
|
|
|
180 if (!n.fixed) {
|
|
|
181 n.x += Math.max(-5, Math.min(5, n.dx));
|
|
|
182 n.y += Math.max(-5, Math.min(5, n.dy));
|
|
|
183 }
|
|
|
184 if (n.x < 0) {
|
|
|
185 n.x = 0;
|
|
|
186 } else if (n.x > d.width) {
|
|
|
187 n.x = d.width;
|
|
|
188 }
|
|
|
189 if (n.y < 0) {
|
|
|
190 n.y = 0;
|
|
|
191 } else if (n.y > d.height) {
|
|
|
192 n.y = d.height;
|
|
|
193 }
|
|
|
194 n.dx /= 2;
|
|
|
195 n.dy /= 2;
|
|
|
196 }
|
|
|
197 repaint();
|
|
|
198 }
|
|
|
199
|
|
|
200 Node pick;
|
|
|
201 boolean pickfixed;
|
|
|
202 Image offscreen;
|
|
|
203 Dimension offscreensize;
|
|
|
204 Graphics offgraphics;
|
|
|
205
|
|
|
206 final Color fixedColor = Color.red;
|
|
|
207 final Color selectColor = Color.pink;
|
|
|
208 final Color edgeColor = Color.black;
|
|
|
209 final Color nodeColor = new Color(250, 220, 100);
|
|
|
210 final Color stressColor = Color.darkGray;
|
|
|
211 final Color arcColor1 = Color.black;
|
|
|
212 final Color arcColor2 = Color.pink;
|
|
|
213 final Color arcColor3 = Color.red;
|
|
|
214
|
|
|
215 public void paintNode(Graphics g, Node n, FontMetrics fm) {
|
|
|
216 int x = (int)n.x;
|
|
|
217 int y = (int)n.y;
|
|
|
218 g.setColor((n == pick) ? selectColor : (n.fixed ? fixedColor : nodeColor));
|
|
|
219 int w = fm.stringWidth(n.lbl) + 10;
|
|
|
220 int h = fm.getHeight() + 4;
|
|
|
221 g.fillRect(x - w/2, y - h / 2, w, h);
|
|
|
222 g.setColor(Color.black);
|
|
|
223 g.drawRect(x - w/2, y - h / 2, w-1, h-1);
|
|
|
224 g.drawString(n.lbl, x - (w-10)/2, (y - (h-4)/2) + fm.getAscent());
|
|
|
225 }
|
|
|
226
|
|
|
227 public synchronized void update(Graphics g) {
|
|
|
228 Dimension d = getSize();
|
|
|
229 if ((offscreen == null) || (d.width != offscreensize.width) || (d.height != offscreensize.height)) {
|
|
|
230 offscreen = createImage(d.width, d.height);
|
|
|
231 offscreensize = d;
|
|
|
232 if (offgraphics != null) {
|
|
|
233 offgraphics.dispose();
|
|
|
234 }
|
|
|
235 offgraphics = offscreen.getGraphics();
|
|
|
236 offgraphics.setFont(getFont());
|
|
|
237 }
|
|
|
238
|
|
|
239 offgraphics.setColor(getBackground());
|
|
|
240 offgraphics.fillRect(0, 0, d.width, d.height);
|
|
|
241 for (int i = 0 ; i < nedges ; i++) {
|
|
|
242 Edge e = edges[i];
|
|
|
243 int x1 = (int)nodes[e.from].x;
|
|
|
244 int y1 = (int)nodes[e.from].y;
|
|
|
245 int x2 = (int)nodes[e.to].x;
|
|
|
246 int y2 = (int)nodes[e.to].y;
|
|
|
247 int len = (int)Math.abs(Math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)) - e.len);
|
|
|
248 offgraphics.setColor((len < 10) ? arcColor1 : (len < 20 ? arcColor2 : arcColor3)) ;
|
|
|
249 offgraphics.drawLine(x1, y1, x2, y2);
|
|
|
250 if (stress) {
|
|
|
251 String lbl = String.valueOf(len);
|
|
|
252 offgraphics.setColor(stressColor);
|
|
|
253 offgraphics.drawString(lbl, x1 + (x2-x1)/2, y1 + (y2-y1)/2);
|
|
|
254 offgraphics.setColor(edgeColor);
|
|
|
255 }
|
|
|
256 }
|
|
|
257
|
|
|
258 FontMetrics fm = offgraphics.getFontMetrics();
|
|
|
259 for (int i = 0 ; i < nnodes ; i++) {
|
|
|
260 paintNode(offgraphics, nodes[i], fm);
|
|
|
261 }
|
|
|
262 g.drawImage(offscreen, 0, 0, null);
|
|
|
263 }
|
|
|
264
|
|
|
265 //1.1 event handling
|
|
|
266 public void mouseClicked(MouseEvent e) {
|
|
|
267 }
|
|
|
268
|
|
|
269 public void mousePressed(MouseEvent e) {
|
|
|
270 addMouseMotionListener(this);
|
|
|
271 double bestdist = Double.MAX_VALUE;
|
|
|
272 int x = e.getX();
|
|
|
273 int y = e.getY();
|
|
|
274 for (int i = 0 ; i < nnodes ; i++) {
|
|
|
275 Node n = nodes[i];
|
|
|
276 double dist = (n.x - x) * (n.x - x) + (n.y - y) * (n.y - y);
|
|
|
277 if (dist < bestdist) {
|
|
|
278 pick = n;
|
|
|
279 bestdist = dist;
|
|
|
280 }
|
|
|
281 }
|
|
|
282 pickfixed = pick.fixed;
|
|
|
283 pick.fixed = true;
|
|
|
284 pick.x = x;
|
|
|
285 pick.y = y;
|
|
|
286 repaint();
|
|
|
287 e.consume();
|
|
|
288 }
|
|
|
289
|
|
|
290 public void mouseReleased(MouseEvent e) {
|
|
|
291 removeMouseMotionListener(this);
|
|
|
292 if (pick != null) {
|
|
|
293 pick.x = e.getX();
|
|
|
294 pick.y = e.getY();
|
|
|
295 pick.fixed = pickfixed;
|
|
|
296 pick = null;
|
|
|
297 }
|
|
|
298 repaint();
|
|
|
299 e.consume();
|
|
|
300 }
|
|
|
301
|
|
|
302 public void mouseEntered(MouseEvent e) {
|
|
|
303 }
|
|
|
304
|
|
|
305 public void mouseExited(MouseEvent e) {
|
|
|
306 }
|
|
|
307
|
|
|
308 public void mouseDragged(MouseEvent e) {
|
|
|
309 pick.x = e.getX();
|
|
|
310 pick.y = e.getY();
|
|
|
311 repaint();
|
|
|
312 e.consume();
|
|
|
313 }
|
|
|
314
|
|
|
315 public void mouseMoved(MouseEvent e) {
|
|
|
316 }
|
|
|
317
|
|
|
318 public void start() {
|
|
|
319 relaxer = new Thread(this);
|
|
|
320 relaxer.start();
|
|
|
321 }
|
|
|
322
|
|
|
323 public void stop() {
|
|
|
324 relaxer = null;
|
|
|
325 }
|
|
|
326
|
|
|
327 }
|
|
|
328
|
|
|
329
|
|
|
330 public class Graph extends Applet implements ActionListener, ItemListener {
|
|
|
331
|
|
|
332 GraphPanel panel;
|
|
|
333 Panel controlPanel;
|
|
|
334
|
|
|
335 Button scramble = new Button("Scramble");
|
|
|
336 Button shake = new Button("Shake");
|
|
|
337 Checkbox stress = new Checkbox("Stress");
|
|
|
338 Checkbox random = new Checkbox("Random");
|
|
|
339
|
|
|
340 public void init() {
|
|
|
341 setLayout(new BorderLayout());
|
|
|
342
|
|
|
343 panel = new GraphPanel(this);
|
|
|
344 add("Center", panel);
|
|
|
345 controlPanel = new Panel();
|
|
|
346 add("South", controlPanel);
|
|
|
347
|
|
|
348 controlPanel.add(scramble); scramble.addActionListener(this);
|
|
|
349 controlPanel.add(shake); shake.addActionListener(this);
|
|
|
350 controlPanel.add(stress); stress.addItemListener(this);
|
|
|
351 controlPanel.add(random); random.addItemListener(this);
|
|
|
352
|
|
|
353 String edges = getParameter("edges");
|
|
|
354 for (StringTokenizer t = new StringTokenizer(edges, ",") ; t.hasMoreTokens() ; ) {
|
|
|
355 String str = t.nextToken();
|
|
|
356 int i = str.indexOf('-');
|
|
|
357 if (i > 0) {
|
|
|
358 int len = 50;
|
|
|
359 int j = str.indexOf('/');
|
|
|
360 if (j > 0) {
|
|
|
361 len = Integer.valueOf(str.substring(j+1)).intValue();
|
|
|
362 str = str.substring(0, j);
|
|
|
363 }
|
|
|
364 panel.addEdge(str.substring(0,i), str.substring(i+1), len);
|
|
|
365 }
|
|
|
366 }
|
|
|
367 Dimension d = getSize();
|
|
|
368 String center = getParameter("center");
|
|
|
369 if (center != null){
|
|
|
370 Node n = panel.nodes[panel.findNode(center)];
|
|
|
371 n.x = d.width / 2;
|
|
|
372 n.y = d.height / 2;
|
|
|
373 n.fixed = true;
|
|
|
374 }
|
|
|
375 }
|
|
|
376
|
|
|
377 public void destroy() {
|
|
|
378 remove(panel);
|
|
|
379 remove(controlPanel);
|
|
|
380 }
|
|
|
381
|
|
|
382 public void start() {
|
|
|
383 panel.start();
|
|
|
384 }
|
|
|
385
|
|
|
386 public void stop() {
|
|
|
387 panel.stop();
|
|
|
388 }
|
|
|
389
|
|
|
390 public void actionPerformed(ActionEvent e) {
|
|
|
391 Object src = e.getSource();
|
|
|
392
|
|
|
393 if (src == scramble) {
|
|
|
394 play(getCodeBase(), "audio/computer.au");
|
|
|
395 Dimension d = getSize();
|
|
|
396 for (int i = 0 ; i < panel.nnodes ; i++) {
|
|
|
397 Node n = panel.nodes[i];
|
|
|
398 if (!n.fixed) {
|
|
|
399 n.x = 10 + (d.width-20)*Math.random();
|
|
|
400 n.y = 10 + (d.height-20)*Math.random();
|
|
|
401 }
|
|
|
402 }
|
|
|
403 return;
|
|
|
404 }
|
|
|
405
|
|
|
406 if (src == shake) {
|
|
|
407 play(getCodeBase(), "audio/gong.au");
|
|
|
408 Dimension d = getSize();
|
|
|
409 for (int i = 0 ; i < panel.nnodes ; i++) {
|
|
|
410 Node n = panel.nodes[i];
|
|
|
411 if (!n.fixed) {
|
|
|
412 n.x += 80*Math.random() - 40;
|
|
|
413 n.y += 80*Math.random() - 40;
|
|
|
414 }
|
|
|
415 }
|
|
|
416 }
|
|
|
417
|
|
|
418 }
|
|
|
419
|
|
|
420 public void itemStateChanged(ItemEvent e) {
|
|
|
421 Object src = e.getSource();
|
|
|
422 boolean on = e.getStateChange() == ItemEvent.SELECTED;
|
|
|
423 if (src == stress) panel.stress = on;
|
|
|
424 else if (src == random) panel.random = on;
|
|
|
425 }
|
|
|
426
|
|
|
427 public String getAppletInfo() {
|
|
|
428 return "Title: GraphLayout \nAuthor: <unknown>";
|
|
|
429 }
|
|
|
430
|
|
|
431 public String[][] getParameterInfo() {
|
|
|
432 String[][] info = {
|
|
|
433 {"edges", "delimited string", "A comma-delimited list of all the edges. It takes the form of 'C-N1,C-N2,C-N3,C-NX,N1-N2/M12,N2-N3/M23,N3-NX/M3X,...' where C is the name of center node (see 'center' parameter) and NX is a node attached to the center node. For the edges connecting nodes to eachother (and not to the center node) you may (optionally) specify a length MXY separated from the edge name by a forward slash."},
|
|
|
434 {"center", "string", "The name of the center node."}
|
|
|
435 };
|
|
|
436 return info;
|
|
|
437 }
|
|
|
438
|
|
|
439 }
|
