|
1 /*************************************************************************** |
|
2 Title: GraphBrowser/Graph.java |
|
3 ID: $Id$ |
|
4 Author: Stefan Berghofer, TU Muenchen |
|
5 Copyright 1997 TU Muenchen |
|
6 |
|
7 This class contains the core of the layout algorithm and methods for |
|
8 drawing and PostScript output. |
|
9 ***************************************************************************/ |
|
10 |
|
11 package GraphBrowser; |
|
12 |
|
13 import java.util.*; |
|
14 import java.awt.*; |
|
15 import java.io.*; |
|
16 |
|
17 class ParseError extends Exception { |
|
18 public ParseError(String s) { super(s); } |
|
19 } |
|
20 |
|
21 public class Graph { |
|
22 /**** parameters for layout ****/ |
|
23 |
|
24 public int box_height=0; |
|
25 public int box_height2; |
|
26 public int box_width; |
|
27 public int box_width2; |
|
28 public int box_hspace; |
|
29 |
|
30 Vector vertices=new Vector(10,10); |
|
31 Vector splines=new Vector(10,10); |
|
32 Vector numEdges=new Vector(10,10); |
|
33 Vertex []vertices2; |
|
34 |
|
35 public int min_x=0,min_y=0,max_x=10,max_y=10; |
|
36 |
|
37 /********************************************************************/ |
|
38 /* clone graph object */ |
|
39 /********************************************************************/ |
|
40 |
|
41 public Object clone() { |
|
42 Graph gr=new Graph(); |
|
43 Enumeration e1; |
|
44 int i; |
|
45 |
|
46 gr.splines=(Vector)(splines.clone()); |
|
47 |
|
48 e1=vertices.elements(); |
|
49 while (e1.hasMoreElements()) |
|
50 gr.addVertex((Vertex)(((Vertex)(e1.nextElement())).clone())); |
|
51 |
|
52 for (i=0;i<vertices.size();i++) { |
|
53 Vertex vx1=(Vertex)(gr.vertices.elementAt(i)); |
|
54 e1=((Vertex)(vertices.elementAt(i))).getChildren(); |
|
55 while (e1.hasMoreElements()) { |
|
56 Vertex vx2=(Vertex)(gr.vertices.elementAt(vertices.indexOf(e1.nextElement()))); |
|
57 vx1.addChild(vx2); |
|
58 } |
|
59 } |
|
60 |
|
61 gr.vertices2 = new Vertex[vertices.size()]; |
|
62 gr.vertices.copyInto(gr.vertices2); |
|
63 |
|
64 gr.min_x=min_x;gr.max_x=max_x; |
|
65 gr.min_y=min_y;gr.max_y=max_y; |
|
66 |
|
67 return gr; |
|
68 } |
|
69 |
|
70 Graph() {} |
|
71 |
|
72 /********************************************************************/ |
|
73 /* Read graph from stream */ |
|
74 /********************************************************************/ |
|
75 |
|
76 public Graph(InputStream s,TreeNode tn) throws IOException, ParseError { |
|
77 StreamTokenizer tok=new StreamTokenizer(s); |
|
78 String name,dir,vertexID; |
|
79 Vertex ve1,ve2; |
|
80 boolean children,unfoldDir; |
|
81 int index=0; |
|
82 |
|
83 tok.nextToken(); |
|
84 while (tok.ttype!=StreamTokenizer.TT_EOF) { |
|
85 if (tok.ttype!=StreamTokenizer.TT_WORD && tok.ttype!='"') |
|
86 throw new ParseError("expected: vertex name\nfound : "+tok.toString()); |
|
87 name=tok.sval; |
|
88 tok.nextToken(); |
|
89 if (tok.ttype!=StreamTokenizer.TT_WORD && tok.ttype!='"') |
|
90 throw new ParseError("expected: vertex identifier\nfound : "+tok.toString()); |
|
91 vertexID=tok.sval; |
|
92 tok.nextToken(); |
|
93 if (tok.ttype!=StreamTokenizer.TT_WORD && tok.ttype!='"') |
|
94 throw new ParseError("expected: directory name\nfound : "+tok.toString()); |
|
95 dir=tok.sval; |
|
96 tok.nextToken(); |
|
97 if (tok.ttype=='+') { |
|
98 unfoldDir=true; |
|
99 tok.nextToken(); |
|
100 } else |
|
101 unfoldDir=false; |
|
102 if (tok.ttype!=StreamTokenizer.TT_WORD && tok.ttype!='"') |
|
103 throw new ParseError("expected: path name\nfound : "+tok.toString()); |
|
104 ve1=findVertex(vertexID); |
|
105 if (ve1==null) { |
|
106 ve1=new NormalVertex(""); |
|
107 ve1.setID(vertexID); |
|
108 ve1.setNumber(index++); |
|
109 addVertex(ve1); |
|
110 } |
|
111 ve1.setPath(tok.sval); |
|
112 ve1.setDir(dir); |
|
113 ve1.setLabel(name); |
|
114 tn.insertNode(name,dir,tok.sval,ve1.getNumber(),unfoldDir); |
|
115 tok.nextToken(); |
|
116 if (tok.ttype=='<') { |
|
117 children=true; |
|
118 tok.nextToken(); |
|
119 } else if (tok.ttype=='>') { |
|
120 children=false; |
|
121 tok.nextToken(); |
|
122 } else children=true; |
|
123 while (tok.ttype!=';') { |
|
124 if (tok.ttype!=StreamTokenizer.TT_WORD && tok.ttype!='"') |
|
125 throw new ParseError("expected: child vertex identifier or ';'\nfound : "+tok.toString()); |
|
126 ve2=findVertex(tok.sval); |
|
127 if (ve2==null) { |
|
128 ve2=new NormalVertex(""); |
|
129 ve2.setID(tok.sval); |
|
130 ve2.setNumber(index++); |
|
131 addVertex(ve2); |
|
132 } |
|
133 if (children) |
|
134 ve1.addChild(ve2); |
|
135 else |
|
136 ve1.addParent(ve2); |
|
137 tok.nextToken(); |
|
138 } |
|
139 tok.nextToken(); |
|
140 } |
|
141 vertices2 = new Vertex[vertices.size()]; |
|
142 vertices.copyInto(vertices2); |
|
143 } |
|
144 |
|
145 /*** Find vertex with identifier vertexID ***/ |
|
146 |
|
147 public Vertex findVertex(String vertexID) { |
|
148 Enumeration e1=vertices.elements(); |
|
149 Vertex v1; |
|
150 |
|
151 while (e1.hasMoreElements()) { |
|
152 v1=(Vertex)(e1.nextElement()); |
|
153 if ((v1.getID()).equals(vertexID)) |
|
154 return v1; |
|
155 } |
|
156 return null; |
|
157 } |
|
158 |
|
159 public void addVertex(Vertex v) { |
|
160 vertices.addElement(v); |
|
161 v.setGraph(this); |
|
162 } |
|
163 |
|
164 public void removeVertex(Vertex v) { |
|
165 vertices.removeElement(v); |
|
166 } |
|
167 |
|
168 public Enumeration getVertices() { |
|
169 return vertices.elements(); |
|
170 } |
|
171 |
|
172 /********************************************************************/ |
|
173 /* graph layout */ |
|
174 /********************************************************************/ |
|
175 |
|
176 public void layout(Graphics g) { |
|
177 splines.removeAllElements(); |
|
178 hasseDiagram(); |
|
179 Vector layers=min_crossings(insert_dummies((Vector)(sort().elementAt(0)))); |
|
180 setParameters(g); |
|
181 init_coordinates(layers); |
|
182 pendulum(layers); |
|
183 rubberband(layers); |
|
184 calcSplines(layers); |
|
185 calcBoundingBox(); |
|
186 } |
|
187 |
|
188 /********************************************************************/ |
|
189 /* set layout parameters */ |
|
190 /********************************************************************/ |
|
191 |
|
192 public void setParameters(Graphics g) { |
|
193 Enumeration e1=vertices.elements(); |
|
194 int h,w; |
|
195 h=w=Integer.MIN_VALUE; |
|
196 |
|
197 while (e1.hasMoreElements()) { |
|
198 Dimension dim=((Vertex)(e1.nextElement())).getLabelSize(g); |
|
199 h=Math.max(h,dim.height); |
|
200 w=Math.max(w,dim.width); |
|
201 } |
|
202 box_height=h+4; |
|
203 box_height2=box_height/2; |
|
204 box_width=w+8; |
|
205 box_width2=box_width/2; |
|
206 box_hspace=box_width+20; |
|
207 } |
|
208 |
|
209 /********************************************************************/ |
|
210 /* topological sorting */ |
|
211 /********************************************************************/ |
|
212 |
|
213 public Vector sort() { |
|
214 Vector todo=(Vector)(vertices.clone()); |
|
215 Vector layers=new Vector(10,10); |
|
216 Vector todo2; |
|
217 Enumeration e1,e2; |
|
218 Vertex v,v2; |
|
219 |
|
220 e1=vertices.elements(); |
|
221 while (e1.hasMoreElements()) |
|
222 ((Vertex)(e1.nextElement())).setDegree(0); |
|
223 |
|
224 e1=vertices.elements(); |
|
225 while (e1.hasMoreElements()) { |
|
226 v=(Vertex)(e1.nextElement()); |
|
227 e2=v.getChildren(); |
|
228 while (e2.hasMoreElements()) { |
|
229 v2=(Vertex)(e2.nextElement()); |
|
230 todo.removeElement(v2); |
|
231 v2.setDegree(1+v2.getDegree()); |
|
232 } |
|
233 } |
|
234 while (!todo.isEmpty()) { |
|
235 layers.addElement(todo); |
|
236 todo2=new Vector(10,10); |
|
237 e1=todo.elements(); |
|
238 while (e1.hasMoreElements()) { |
|
239 e2=((Vertex)(e1.nextElement())).getChildren(); |
|
240 while (e2.hasMoreElements()) { |
|
241 v=(Vertex)(e2.nextElement()); |
|
242 v.setDegree(v.getDegree()-1); |
|
243 if (v.getDegree()==0) { |
|
244 todo2.addElement(v); |
|
245 v.setDegree(layers.size()); |
|
246 } |
|
247 } |
|
248 } |
|
249 todo=todo2; |
|
250 } |
|
251 return layers; |
|
252 } |
|
253 |
|
254 /********************************************************************/ |
|
255 /* compute hasse diagram */ |
|
256 /********************************************************************/ |
|
257 |
|
258 public void hasseDiagram() { |
|
259 Enumeration e1,e2; |
|
260 Vertex vx1,vx2; |
|
261 |
|
262 /** construct adjacence matrix **/ |
|
263 |
|
264 int vs=vertices.size(); |
|
265 boolean adj[][]=new boolean[vs][vs]; |
|
266 boolean adj2[][]=new boolean[vs][vs]; |
|
267 int i,j,k; |
|
268 |
|
269 e1=getVertices(); |
|
270 for (i=0;i<vs;i++) { |
|
271 vx1=(Vertex)(e1.nextElement()); |
|
272 e2=vx1.getChildren(); |
|
273 while (e2.hasMoreElements()) { |
|
274 vx2=(Vertex)(e2.nextElement()); |
|
275 j=vertices.indexOf(vx2); |
|
276 adj[i][j]=true; |
|
277 adj2[i][j]=true; |
|
278 } |
|
279 } |
|
280 |
|
281 /** compute transitive closure R+ **/ |
|
282 |
|
283 for (k=0;k<vs;k++) |
|
284 for (i=0;i<vs;i++) |
|
285 if (adj[i][k]) |
|
286 for (j=0;j<vs;j++) |
|
287 adj[i][j] = adj[i][j] || adj[k][j]; |
|
288 |
|
289 /** compute R \ (R+)^2 **/ |
|
290 |
|
291 for (i=0;i<vs;i++) |
|
292 for (j=0;j<vs;j++) |
|
293 if (adj2[i][j]) { |
|
294 vx1=(Vertex)(vertices.elementAt(i)); |
|
295 vx2=(Vertex)(vertices.elementAt(j)); |
|
296 for (k=0;k<vs;k++) |
|
297 if (adj[i][k] && adj[k][j]) { |
|
298 vx1.removeChild(vx2); |
|
299 break; |
|
300 } |
|
301 } |
|
302 } |
|
303 |
|
304 /********************************************************************/ |
|
305 /* insert dummy vertices */ |
|
306 /********************************************************************/ |
|
307 |
|
308 public Vector insert_dummies(Vector v) { |
|
309 Vector layers2=new Vector(10,10); |
|
310 int n_edges; |
|
311 |
|
312 do { |
|
313 Enumeration e1=v.elements(),e2; |
|
314 Vector next=new Vector(10,10); |
|
315 |
|
316 layers2.addElement(v); |
|
317 n_edges=0; |
|
318 while (e1.hasMoreElements()) { |
|
319 Vertex v1=(Vertex)(e1.nextElement()); |
|
320 e2=v1.getChildren(); |
|
321 while (e2.hasMoreElements()) { |
|
322 n_edges++; |
|
323 Vertex v2=(Vertex)(e2.nextElement()); |
|
324 if (v2.getDegree()!=v1.getDegree()+1) { |
|
325 Vertex v3=new DummyVertex(); |
|
326 v3.addChild(v2); |
|
327 v3.setDegree(v1.getDegree()+1); |
|
328 v1.removeChild(v2); |
|
329 v1.addChild(v3); |
|
330 next.addElement(v3); |
|
331 addVertex(v3); |
|
332 } else if (next.indexOf(v2)<0) next.addElement(v2); |
|
333 } |
|
334 } |
|
335 v=next; |
|
336 numEdges.addElement(new Integer(n_edges)); |
|
337 } while (!v.isEmpty()); |
|
338 return layers2; |
|
339 } |
|
340 |
|
341 /********************************************************************/ |
|
342 /* calculation of crossings */ |
|
343 /********************************************************************/ |
|
344 |
|
345 public int count_crossings(Vector layers,int oldcr) { |
|
346 int i,j,y1,y2,cr=0,l; |
|
347 for (l=0;l<layers.size()-1;l++) { |
|
348 Vector v1=(Vector)(layers.elementAt(l)); |
|
349 for (i=0;i<v1.size();i++) { |
|
350 Enumeration e2=((Vertex)(v1.elementAt(i))).getChildren(); |
|
351 while (e2.hasMoreElements()) { |
|
352 y1=((Vector)(layers.elementAt(l+1))).indexOf(e2.nextElement()); |
|
353 for (j=0;j<i;j++) { |
|
354 Enumeration e3=((Vertex)(v1.elementAt(j))).getChildren(); |
|
355 while (e3.hasMoreElements()) { |
|
356 y2=((Vector)(layers.elementAt(l+1))).indexOf(e3.nextElement()); |
|
357 if (y1<y2) { |
|
358 cr++; |
|
359 if (cr>=oldcr) return cr; |
|
360 } |
|
361 } |
|
362 } |
|
363 } |
|
364 } |
|
365 } |
|
366 return cr; |
|
367 } |
|
368 |
|
369 /********************************************************************/ |
|
370 /* calculation of crossings where vertices vx1 and vx2 are involved */ |
|
371 /* vx1 and vx2 must be in same layer and vx1 is left from vx2 */ |
|
372 /********************************************************************/ |
|
373 |
|
374 public int count_crossings_2(Vector layers,Vertex vx1,Vertex vx2,int oldcr) { |
|
375 int i,cr=0,l=vx1.getDegree(); |
|
376 Vertex va,vb; |
|
377 Vector layer; |
|
378 Enumeration e1,e2; |
|
379 |
|
380 if (l>0) { |
|
381 layer=(Vector)(layers.elementAt(l-1)); |
|
382 e1=vx1.getParents(); |
|
383 while (e1.hasMoreElements()) { |
|
384 va=(Vertex)(e1.nextElement()); |
|
385 i=layer.indexOf(va); |
|
386 e2=vx2.getParents(); |
|
387 while (e2.hasMoreElements()) { |
|
388 vb=(Vertex)(e2.nextElement()); |
|
389 if (layer.indexOf(vb)<i) { |
|
390 cr++; |
|
391 if (cr>=oldcr) return cr; |
|
392 } |
|
393 } |
|
394 } |
|
395 } |
|
396 if (l<layers.size()-1) { |
|
397 layer=(Vector)(layers.elementAt(l+1)); |
|
398 e1=vx1.getChildren(); |
|
399 while (e1.hasMoreElements()) { |
|
400 va=(Vertex)(e1.nextElement()); |
|
401 i=layer.indexOf(va); |
|
402 e2=vx2.getChildren(); |
|
403 while (e2.hasMoreElements()) { |
|
404 vb=(Vertex)(e2.nextElement()); |
|
405 if (layer.indexOf(vb)<i) { |
|
406 cr++; |
|
407 if (cr>=oldcr) return cr; |
|
408 } |
|
409 } |
|
410 } |
|
411 } |
|
412 return cr; |
|
413 } |
|
414 |
|
415 /********************************************************************/ |
|
416 /* reduction of crossings by exchanging adjacent vertices */ |
|
417 /********************************************************************/ |
|
418 |
|
419 public void exchangeVertices(Vector layers,int oldcr) { |
|
420 int i,l,c1,c2; |
|
421 Vertex vx1,vx2; |
|
422 Vector v1; |
|
423 |
|
424 for (l=0;l<layers.size();l++) { |
|
425 v1=(Vector)(layers.elementAt(l)); |
|
426 for (i=0;i<v1.size()-1;i++) { |
|
427 vx1=(Vertex)(v1.elementAt(i)); |
|
428 vx2=(Vertex)(v1.elementAt(i+1)); |
|
429 c1=count_crossings_2(layers,vx1,vx2,oldcr); |
|
430 c2=count_crossings_2(layers,vx2,vx1,c1); |
|
431 if (c2<c1) { |
|
432 v1.setElementAt(vx2,i); |
|
433 v1.setElementAt(vx1,i+1); |
|
434 } |
|
435 } |
|
436 } |
|
437 } |
|
438 |
|
439 /********************************************************************/ |
|
440 /* minimization of crossings */ |
|
441 /********************************************************************/ |
|
442 |
|
443 public Vector min_crossings(Vector layers) { |
|
444 int n,i,l,k,z=0,cr2,cr=count_crossings(layers,Integer.MAX_VALUE); |
|
445 boolean topdown=true,first=true; |
|
446 Enumeration e1,e2; |
|
447 Vector v1,v2,layers2=null,best=layers; |
|
448 Vertex vx1,vx2; |
|
449 n=0; |
|
450 while (n<3 && cr>0) { |
|
451 if (topdown) { |
|
452 /** top-down-traversal **/ |
|
453 |
|
454 layers2=new Vector(10,10); |
|
455 for (l=0;l<layers.size();l++) { |
|
456 v1=(Vector)(layers.elementAt(l)); |
|
457 if (l==0) layers2.addElement(v1.clone()); |
|
458 else { |
|
459 v2=new Vector(10,10); |
|
460 layers2.addElement(v2); |
|
461 e1=v1.elements(); |
|
462 while (e1.hasMoreElements()) { |
|
463 vx1=(Vertex)(e1.nextElement()); |
|
464 k=0;z=0; |
|
465 e2=vx1.getParents(); |
|
466 while (e2.hasMoreElements()) { |
|
467 k+=((Vector)(layers2.elementAt(l-1))).indexOf(e2.nextElement()); |
|
468 z++; |
|
469 } |
|
470 if (z>0) |
|
471 vx1.setWeight(((double)(k))/z); |
|
472 else if (first) |
|
473 vx1.setWeight(Double.MAX_VALUE); |
|
474 for (i=0;i<v2.size();i++) |
|
475 if (vx1.getWeight()<((Vertex)(v2.elementAt(i))).getWeight()) break; |
|
476 if (i==v2.size()) v2.addElement(vx1); |
|
477 else v2.insertElementAt(vx1,i); |
|
478 } |
|
479 } |
|
480 } |
|
481 } else { |
|
482 /** bottom-up-traversal **/ |
|
483 |
|
484 layers2=new Vector(10,10); |
|
485 for (l=layers.size()-1;l>=0;l--) { |
|
486 v1=(Vector)(layers.elementAt(l)); |
|
487 if (l==layers.size()-1) layers2.addElement(v1.clone()); |
|
488 else { |
|
489 v2=new Vector(10,10); |
|
490 layers2.insertElementAt(v2,0); |
|
491 e1=v1.elements(); |
|
492 while (e1.hasMoreElements()) { |
|
493 vx1=(Vertex)(e1.nextElement()); |
|
494 k=0;z=0; |
|
495 e2=vx1.getChildren(); |
|
496 while (e2.hasMoreElements()) { |
|
497 k+=((Vector)(layers2.elementAt(1))).indexOf(e2.nextElement()); |
|
498 z++; |
|
499 } |
|
500 if (z>0) |
|
501 vx1.setWeight(((double)(k))/z); |
|
502 else if (first) |
|
503 vx1.setWeight(Double.MAX_VALUE); |
|
504 for (i=0;i<v2.size();i++) |
|
505 if (vx1.getWeight()<((Vertex)(v2.elementAt(i))).getWeight()) break; |
|
506 if (i==v2.size()) v2.addElement(vx1); |
|
507 else v2.insertElementAt(vx1,i); |
|
508 } |
|
509 } |
|
510 } |
|
511 } |
|
512 //exchangeVertices(layers2,cr); |
|
513 topdown=!topdown; |
|
514 first=false; |
|
515 layers=layers2; |
|
516 |
|
517 cr2=count_crossings(layers2,cr); |
|
518 if (cr2<cr) { |
|
519 best=layers2; |
|
520 cr=cr2; |
|
521 } else n++; |
|
522 } |
|
523 |
|
524 while (true) { |
|
525 exchangeVertices(best,cr); |
|
526 cr2=count_crossings(best,cr); |
|
527 if (cr2<cr) |
|
528 cr=cr2; |
|
529 else |
|
530 break; |
|
531 } |
|
532 |
|
533 return best; |
|
534 } |
|
535 |
|
536 /********************************************************************/ |
|
537 /* set initial coordinates */ |
|
538 /********************************************************************/ |
|
539 |
|
540 public void init_coordinates(Vector layers) { |
|
541 int y=0; |
|
542 Enumeration e1=layers.elements(); |
|
543 Enumeration e3=numEdges.elements(); |
|
544 while (e1.hasMoreElements()) { |
|
545 Vector v1=(Vector)(e1.nextElement()); |
|
546 Enumeration e2=v1.elements(); |
|
547 int x=box_width2; |
|
548 while (e2.hasMoreElements()) { |
|
549 Vertex ve=(Vertex)(e2.nextElement()); |
|
550 ve.setX(x); |
|
551 ve.setY(y); |
|
552 x+=box_hspace; |
|
553 } |
|
554 y+=box_height+Math.max(35,7*(((Integer)(e3.nextElement())).intValue())); |
|
555 } |
|
556 } |
|
557 |
|
558 /********************************************************************/ |
|
559 /* pendulum method */ |
|
560 /********************************************************************/ |
|
561 |
|
562 public void pendulum(Vector layers) { |
|
563 Vector layers2=new Vector(10,10); |
|
564 Enumeration e1=layers.elements(),e2; |
|
565 int i,j,d1,d2,k,offset,dsum; |
|
566 Region r1,r2; |
|
567 boolean change; |
|
568 |
|
569 while (e1.hasMoreElements()) { |
|
570 e2=((Vector)(e1.nextElement())).elements(); |
|
571 Vector layer=new Vector(10,10); |
|
572 layers2.addElement(layer); |
|
573 while (e2.hasMoreElements()) { |
|
574 Region r=new Region(this); |
|
575 r.addVertex((Vertex)(e2.nextElement())); |
|
576 layer.addElement(r); |
|
577 } |
|
578 } |
|
579 for (k=0;k<10;k++) { |
|
580 dsum=0; |
|
581 for (j=1;j<layers2.size();j++) { |
|
582 Vector l=(Vector)(layers2.elementAt(j)); |
|
583 if (l.size()>=2) { |
|
584 do { |
|
585 change=false; |
|
586 d1=((Region)(l.firstElement())).pred_deflection(); |
|
587 for (i=0;i<l.size()-1;i++) { |
|
588 r1=(Region)(l.elementAt(i)); |
|
589 r2=(Region)(l.elementAt(i+1)); |
|
590 d2=r2.pred_deflection(); |
|
591 if (r1.touching(r2) && (d1 <= 0 && d2 < d1 || |
|
592 d2 > 0 && d1 > d2 || d1 > 0 && d2 < 0)) { |
|
593 r1.combine(r2); |
|
594 l.removeElement(r2); |
|
595 change=true; |
|
596 d2=r1.pred_deflection(); |
|
597 } |
|
598 d1=d2; |
|
599 } |
|
600 } while (change); |
|
601 } |
|
602 for (i=0;i<l.size();i++) { |
|
603 r1=(Region)(l.elementAt(i)); |
|
604 d1=r1.pred_deflection(); |
|
605 offset=d1; |
|
606 if (d1<0 && i>0) offset=-Math.min( |
|
607 ((Region)(l.elementAt(i-1))).spaceBetween(r1),-d1); |
|
608 if (d1>=0 && i<l.size()-1) offset=Math.min( |
|
609 r1.spaceBetween((Region)(l.elementAt(i+1))),d1); |
|
610 r1.move(offset); |
|
611 dsum+=Math.abs(d1); |
|
612 } |
|
613 } |
|
614 if (dsum==0) break; |
|
615 } |
|
616 } |
|
617 |
|
618 /********************************************************************/ |
|
619 /* rubberband method */ |
|
620 /********************************************************************/ |
|
621 |
|
622 public void rubberband(Vector layers) { |
|
623 Enumeration e1,e2; |
|
624 int i,n,k,d,d2; |
|
625 Vector v; |
|
626 Vertex vx; |
|
627 |
|
628 for (k=0;k<10;k++) { |
|
629 e1=layers.elements(); |
|
630 while (e1.hasMoreElements()) { |
|
631 v=(Vector)(e1.nextElement()); |
|
632 for (i=0;i<v.size();i++) { |
|
633 n=0;d=0; |
|
634 vx=(Vertex)(v.elementAt(i)); |
|
635 e2=vx.getChildren(); |
|
636 while (e2.hasMoreElements()) { |
|
637 d+=((Vertex)(e2.nextElement())).getX()-vx.getX(); |
|
638 n++; |
|
639 } |
|
640 e2=vx.getParents(); |
|
641 while (e2.hasMoreElements()) { |
|
642 d+=((Vertex)(e2.nextElement())).getX()-vx.getX(); |
|
643 n++; |
|
644 } |
|
645 d2=(n!=0?d/n:0); |
|
646 |
|
647 if (d<0 && (i==0 || ((Vertex)(v.elementAt(i-1))).rightX()+box_hspace-box_width < vx.leftX()+d2) || |
|
648 d>0 && (i==v.size()-1 || ((Vertex)(v.elementAt(i+1))).leftX()-box_hspace+box_width > vx.rightX()+d2)) |
|
649 vx.setX(vx.getX()+d2); |
|
650 } |
|
651 } |
|
652 } |
|
653 } |
|
654 |
|
655 /**** Intersection point of two lines (auxiliary function for calcSplines) ****/ |
|
656 /**** Calculate intersection point of line which is parallel to line (p1,p2) ****/ |
|
657 /**** and leads through p5, with line (p3,p4) ****/ |
|
658 |
|
659 Point intersect(Point p1,Point p2,Point p3,Point p4,Point p5) { |
|
660 float x=0,y=0,s1=0,s2=0; |
|
661 |
|
662 if (p1.x!=p2.x) |
|
663 s1=((float)(p2.y-p1.y))/(p2.x-p1.x); |
|
664 if (p3.x!=p4.x) |
|
665 s2=((float)(p4.y-p3.y))/(p4.x-p3.x); |
|
666 if (p1.x==p2.x) { |
|
667 x=p5.x; |
|
668 y=s2*(p5.x-p3.x)+p3.y; |
|
669 } else if (p3.x==p4.x) { |
|
670 x=p3.x; |
|
671 y=s1*(p3.x-p5.x)+p5.y; |
|
672 } else { |
|
673 x=(p5.x*s1-p3.x*s2+p3.y-p5.y)/(s1-s2); |
|
674 y=s2*(x-p3.x)+p3.y; |
|
675 } |
|
676 return new Point(Math.round(x),Math.round(y)); |
|
677 } |
|
678 |
|
679 /**** Calculate control points (auxiliary function for calcSplines) ****/ |
|
680 |
|
681 Points calcPoint(Point p1,Point p2,Point p3,int lboxx,int rboxx,int boxy) { |
|
682 |
|
683 /*** Points p1 , p2 , p3 define a triangle which encloses the spline. ***/ |
|
684 /*** Check if adjacent boxes (specified by lboxx,rboxx and boxy) ***/ |
|
685 /*** collide with the spline. In this case p1 and p3 are shifted by an ***/ |
|
686 /*** appropriate offset before they are returned ***/ |
|
687 |
|
688 int xh1,xh2,bx=0,by=0; |
|
689 boolean pt1 = boxy >= p1.y && boxy <= p3.y || boxy >= p3.y && boxy <= p1.y; |
|
690 boolean pt2 = boxy+box_height >= p1.y && boxy+box_height <= p3.y || |
|
691 boxy+box_height >= p3.y && boxy+box_height <= p1.y; |
|
692 boolean move = false; |
|
693 Point b; |
|
694 |
|
695 xh1 = p1.x+(boxy-p1.y)*(p3.x-p1.x)/(p3.y-p1.y); |
|
696 xh2 = p1.x+(boxy+box_height-p1.y)*(p3.x-p1.x)/(p3.y-p1.y); |
|
697 |
|
698 if (xh1 <= lboxx && pt1 && xh2 <= lboxx && pt2) { |
|
699 move = true; |
|
700 bx = lboxx; |
|
701 by = boxy + (xh1 < xh2 ? 0 : box_height ) ; |
|
702 } else if (xh1 >= rboxx && pt1 && xh2 >= rboxx && pt2) { |
|
703 move = true; |
|
704 bx = rboxx; |
|
705 by = boxy + (xh1 > xh2 ? 0 : box_height ) ; |
|
706 } else if ( (xh1 <= lboxx || xh1 >= rboxx) && pt1) { |
|
707 move = true; |
|
708 bx = (xh1 <= lboxx ? lboxx : rboxx ) ; |
|
709 by = boxy; |
|
710 } else if ( (xh2 <= lboxx || xh2 >= rboxx) && pt2) { |
|
711 move = true; |
|
712 bx = (xh2 <= lboxx ? lboxx : rboxx ) ; |
|
713 by = boxy+box_height; |
|
714 } |
|
715 b=new Point(bx,by); |
|
716 if (move) return new Points(intersect(p1,p3,p1,p2,b),intersect(p1,p3,p2,p3,b)); |
|
717 else return new Points(p1,p3); |
|
718 } |
|
719 |
|
720 /********************************************************************/ |
|
721 /* calculate splines */ |
|
722 /********************************************************************/ |
|
723 |
|
724 public void calcSplines(Vector layers) { |
|
725 Enumeration e2,e1=vertices.elements(); |
|
726 Vertex vx1,vx2,vx3; |
|
727 Vector pos,layer; |
|
728 int x1,y1,x2,y2,x3,y3,xh,k,leftx,rightx,spc; |
|
729 |
|
730 while (e1.hasMoreElements()) { |
|
731 vx1=(Vertex)(e1.nextElement()); |
|
732 if (!vx1.isDummy()) { |
|
733 e2=vx1.getChildren(); |
|
734 while (e2.hasMoreElements()) { |
|
735 vx2=(Vertex)(e2.nextElement()); |
|
736 if (vx2.isDummy()) { |
|
737 vx3=vx2; |
|
738 /**** convert edge to spline ****/ |
|
739 pos=new Vector(10,10); |
|
740 x1=vx1.getX(); |
|
741 y1=vx1.getY()+box_height; |
|
742 |
|
743 do { |
|
744 /*** calculate position of control points ***/ |
|
745 x2=vx2.getX(); |
|
746 y2=vx2.getY(); |
|
747 layer=(Vector)(layers.elementAt(vx2.getDegree())); |
|
748 k=layer.indexOf(vx2); |
|
749 vx2=(Vertex)((vx2.getChildren()).nextElement()); |
|
750 x3=vx2.getX(); |
|
751 y3=vx2.getY(); |
|
752 // spc=(box_hspace-box_width)/3; |
|
753 // spc=box_height*3/4; |
|
754 spc=0; |
|
755 leftx = k==0 /* || ((Vertex)(layer.elementAt(k-1))).isDummy() */ ? |
|
756 Integer.MIN_VALUE: |
|
757 ((Vertex)(layer.elementAt(k-1))).rightX()+spc; |
|
758 rightx = k==layer.size()-1 /* || ((Vertex)(layer.elementAt(k+1))).isDummy() */ ? |
|
759 Integer.MAX_VALUE: |
|
760 ((Vertex)(layer.elementAt(k+1))).leftX()-spc; |
|
761 xh=x2+box_height*(x3-x2)/(y3-y2); |
|
762 if (!(x2<=x3 && xh>=rightx || x2>x3 && xh<=leftx)) { |
|
763 /* top control point */ |
|
764 pos.addElement(new Integer(1)); |
|
765 y1=y2; |
|
766 } else { |
|
767 xh=x1+(y2-y1)*(x2-x1)/(y2+box_height-y1); |
|
768 if (!(x2<=x1 && xh>=rightx || x2>x1 && xh<=leftx)) |
|
769 /* bottom control point */ |
|
770 pos.addElement(new Integer(2)); |
|
771 else |
|
772 /* two control points needed */ |
|
773 pos.addElement(new Integer(3)); |
|
774 y1=y2+box_height; |
|
775 } |
|
776 x1=x2; |
|
777 } while (vx2.isDummy()); |
|
778 pos.addElement(new Integer(1)); |
|
779 |
|
780 /**** calculate triangles ****/ |
|
781 vx2=vx3; |
|
782 |
|
783 int pos1,pos2,i=0; |
|
784 Vector pts=new Vector(10,10); |
|
785 int lboxx,rboxx,boxy; |
|
786 |
|
787 x1=vx1.getX(); |
|
788 y1=vx1.getY()+box_height; |
|
789 pts.addElement(new Point(x1,y1)); /** edge starting point **/ |
|
790 do { |
|
791 x2=vx2.getX(); |
|
792 y2=vx2.getY(); |
|
793 pos1=((Integer)(pos.elementAt(i))).intValue(); |
|
794 pos2=((Integer)(pos.elementAt(i+1))).intValue(); |
|
795 i++; |
|
796 layer=(Vector)(layers.elementAt(vx2.getDegree())); |
|
797 k=layer.indexOf(vx2); |
|
798 boxy=vx2.getY(); |
|
799 vx2=(Vertex)((vx2.getChildren()).nextElement()); |
|
800 x3=vx2.getX(); |
|
801 y3=vx2.getY(); |
|
802 if (pos1==2) y2+=box_height; |
|
803 if (pos2==2) y3+=box_height; |
|
804 |
|
805 lboxx = (k==0 /* || ((Vertex)(layer.elementAt(k-1))).isDummy() */ ) ? |
|
806 Integer.MIN_VALUE : |
|
807 ((Vertex)(layer.elementAt(k-1))).rightX(); |
|
808 |
|
809 rboxx = (k==layer.size()-1 /* || ((Vertex)(layer.elementAt(k+1))).isDummy() */ ) ? |
|
810 Integer.MAX_VALUE : |
|
811 ((Vertex)(layer.elementAt(k+1))).leftX(); |
|
812 |
|
813 Point p1,p2,p3; |
|
814 Points ps; |
|
815 |
|
816 p1 = new Point((x1+x2)/2,(y1+y2)/2); |
|
817 |
|
818 if (pos1<=2) { |
|
819 /** one control point **/ |
|
820 p2 = new Point(x2,y2); |
|
821 ps = calcPoint(p1,p2,new Point((x2+x3)/2,(y2+y3)/2),lboxx,rboxx,boxy); |
|
822 pts.addElement(ps.p); |
|
823 pts.addElement(p2); |
|
824 pts.addElement(ps.q); |
|
825 } else { |
|
826 /** two control points **/ |
|
827 p2 = new Point(x2,y2-box_height); |
|
828 p3 = new Point(x2,y2+box_height2); |
|
829 ps = calcPoint(p1,p2,p3,lboxx,rboxx,boxy); |
|
830 pts.addElement(ps.p); |
|
831 pts.addElement(p2); |
|
832 pts.addElement(ps.q); |
|
833 p2 = new Point(x2,y2+box_height*2); |
|
834 ps = calcPoint(p3,p2,new Point((p2.x+x3)/2,(p2.y+y3)/2), |
|
835 lboxx,rboxx,boxy); |
|
836 pts.addElement(ps.p); |
|
837 pts.addElement(p2); |
|
838 pts.addElement(ps.q); |
|
839 } |
|
840 x1=p2.x; |
|
841 y1=p2.y; |
|
842 } while (vx2.isDummy()); |
|
843 |
|
844 pts.addElement(new Point(vx2.getX(),vx2.getY())); /** edge end point **/ |
|
845 splines.addElement(new Spline(pts)); |
|
846 } |
|
847 } |
|
848 } |
|
849 } |
|
850 } |
|
851 |
|
852 /********************************************************************/ |
|
853 /* calculate bounding box */ |
|
854 /********************************************************************/ |
|
855 |
|
856 public void calcBoundingBox() { |
|
857 min_y=min_x=Integer.MAX_VALUE; |
|
858 max_y=max_x=Integer.MIN_VALUE; |
|
859 |
|
860 Enumeration e1=vertices.elements(); |
|
861 Vertex v; |
|
862 |
|
863 while (e1.hasMoreElements()) { |
|
864 v=(Vertex)(e1.nextElement()); |
|
865 min_x=Math.min(min_x,v.leftX()); |
|
866 max_x=Math.max(max_x,v.rightX()); |
|
867 min_y=Math.min(min_y,v.getY()); |
|
868 max_y=Math.max(max_y,v.getY()+box_height); |
|
869 } |
|
870 min_x-=20; |
|
871 min_y-=20; |
|
872 max_x+=20; |
|
873 max_y+=20; |
|
874 } |
|
875 |
|
876 /********************************************************************/ |
|
877 /* draw graph */ |
|
878 /********************************************************************/ |
|
879 |
|
880 public void draw(Graphics g) { |
|
881 if (box_height==0) layout(g); |
|
882 |
|
883 g.translate(-min_x,-min_y); |
|
884 |
|
885 Enumeration e1=vertices.elements(); |
|
886 while (e1.hasMoreElements()) |
|
887 ((Vertex)(e1.nextElement())).draw(g); |
|
888 |
|
889 e1=splines.elements(); |
|
890 while (e1.hasMoreElements()) |
|
891 ((Spline)(e1.nextElement())).draw(g); |
|
892 } |
|
893 |
|
894 /********************************************************************/ |
|
895 /* return vertex at position (x,y) */ |
|
896 /********************************************************************/ |
|
897 |
|
898 public Vertex vertexAt(int x,int y) { |
|
899 Enumeration e1=vertices.elements(); |
|
900 while (e1.hasMoreElements()) { |
|
901 Vertex v=(Vertex)(e1.nextElement()); |
|
902 if (v.contains(x,y)) return v; |
|
903 } |
|
904 return null; |
|
905 } |
|
906 |
|
907 /********************************************************************/ |
|
908 /* encode list of vertices (as array of vertice numbers) */ |
|
909 /********************************************************************/ |
|
910 |
|
911 public Vector encode(Vector v) { |
|
912 Vector code=new Vector(10,10); |
|
913 Enumeration e1=v.elements(); |
|
914 |
|
915 while (e1.hasMoreElements()) { |
|
916 Vertex vx=(Vertex)(e1.nextElement()); |
|
917 if (vx.getNumber()>=0) |
|
918 code.addElement(new Integer(vx.getNumber())); |
|
919 } |
|
920 return code; |
|
921 } |
|
922 |
|
923 /********************************************************************/ |
|
924 /* get vertex with number n */ |
|
925 /********************************************************************/ |
|
926 |
|
927 public Vertex getVertexByNum(int x) { |
|
928 Enumeration e1=vertices.elements(); |
|
929 |
|
930 while (e1.hasMoreElements()) { |
|
931 Vertex vx=(Vertex)(e1.nextElement()); |
|
932 if (vx.getNumber()==x) return vx; |
|
933 } |
|
934 return null; |
|
935 } |
|
936 |
|
937 /********************************************************************/ |
|
938 /* decode list of vertices */ |
|
939 /********************************************************************/ |
|
940 |
|
941 public Vector decode(Vector code) { |
|
942 Enumeration e1=code.elements(); |
|
943 Vector vec=new Vector(10,10); |
|
944 |
|
945 while (e1.hasMoreElements()) { |
|
946 int i=((Integer)(e1.nextElement())).intValue(); |
|
947 //Vertex vx=getVertexByNum(i); |
|
948 //if (vx!=null) vec.addElement(vx); |
|
949 vec.addElement(vertices2[i]); |
|
950 } |
|
951 return vec; |
|
952 } |
|
953 |
|
954 /********************************************************************/ |
|
955 /* collapse vertices */ |
|
956 /********************************************************************/ |
|
957 |
|
958 public void collapse(Vector vs,String name,Vector inflate) { |
|
959 Enumeration e1,e2,e3; |
|
960 boolean nonempty=false; |
|
961 Vertex vx3,vx2,vx1; |
|
962 |
|
963 e1=vertices.elements(); |
|
964 |
|
965 vx1=new NormalVertex(name); |
|
966 vx1.setInflate(inflate); |
|
967 |
|
968 while (e1.hasMoreElements()) { |
|
969 vx2=(Vertex)(e1.nextElement()); |
|
970 |
|
971 if (vs.indexOf(vx2)<0) { |
|
972 e2=vx2.getParents(); |
|
973 while (e2.hasMoreElements()) { |
|
974 vx3=(Vertex)(e2.nextElement()); |
|
975 if (vs.indexOf(vx3)>=0) { |
|
976 if (!vx1.isChild(vx2)) |
|
977 vx1.addChild(vx2); |
|
978 vx3.removeChild(vx2); |
|
979 } |
|
980 } |
|
981 |
|
982 e2=vx2.getChildren(); |
|
983 while (e2.hasMoreElements()) { |
|
984 vx3=(Vertex)(e2.nextElement()); |
|
985 if (vs.indexOf(vx3)>=0) { |
|
986 if (!vx2.isChild(vx1)) |
|
987 vx2.addChild(vx1); |
|
988 vx2.removeChild(vx3); |
|
989 } |
|
990 } |
|
991 } else { nonempty=true; } |
|
992 } |
|
993 |
|
994 e1=vs.elements(); |
|
995 while (e1.hasMoreElements()) |
|
996 try { |
|
997 removeVertex((Vertex)(e1.nextElement())); |
|
998 } catch (NoSuchElementException exn) {} |
|
999 |
|
1000 if (nonempty) addVertex(vx1); |
|
1001 } |
|
1002 |
|
1003 /********************************************************************/ |
|
1004 /* PostScript output */ |
|
1005 /********************************************************************/ |
|
1006 |
|
1007 public void PS(String fname,boolean printable) throws IOException { |
|
1008 FileOutputStream f = new FileOutputStream(fname); |
|
1009 PrintStream p = new PrintStream(f); |
|
1010 |
|
1011 if (printable) |
|
1012 p.println("%!PS-Adobe-2.0\n\n%%BeginProlog"); |
|
1013 else { |
|
1014 p.println("%!PS-Adobe-2.0 EPSF-2.0\n%%Orientation: Portrait"); |
|
1015 p.println("%%BoundingBox: "+min_x+" "+min_y+" "+max_x+" "+max_y); |
|
1016 p.println("%%EndComments\n\n%%BeginProlog"); |
|
1017 } |
|
1018 p.println("/m { moveto } def /l { lineto } def /n { newpath } def"); |
|
1019 p.println("/s { stroke } def /c { curveto } def"); |
|
1020 p.println("/b { n 0 0 m dup true charpath pathbbox 1 index 4 index sub"); |
|
1021 p.println("7 index exch sub 2 div 9 index add 1 index 4 index sub 7 index exch sub"); |
|
1022 p.println("2 div 9 index add 2 index add m pop pop pop pop"); |
|
1023 p.println("1 -1 scale show 1 -1 scale n 3 index 3 index m 1 index 0 rlineto"); |
|
1024 p.println("0 exch rlineto neg 0 rlineto closepath s pop pop } def"); |
|
1025 p.println("%%EndProlog\n"); |
|
1026 if (printable) { |
|
1027 int hsize=max_x-min_x; |
|
1028 int vsize=max_y-min_y; |
|
1029 if (hsize>vsize) { |
|
1030 // Landscape output |
|
1031 double scale=Math.min(1,Math.min(750.0/hsize,500.0/vsize)); |
|
1032 double trans_x=50+max_y*scale+(500-scale*vsize)/2.0; |
|
1033 double trans_y=50+max_x*scale+(750-scale*hsize)/2.0; |
|
1034 p.println(trans_x+" "+trans_y+" translate"); |
|
1035 p.println("-90 rotate"); |
|
1036 p.println(scale+" "+(-scale)+" scale"); |
|
1037 } else { |
|
1038 // Portrait output |
|
1039 double scale=Math.min(1,Math.min(500.0/hsize,750.0/vsize)); |
|
1040 double trans_x=50-min_x*scale+(500-scale*hsize)/2.0; |
|
1041 double trans_y=50+max_y*scale+(750-scale*vsize)/2.0; |
|
1042 p.println(trans_x+" "+trans_y+" translate"); |
|
1043 p.println(scale+" "+(-scale)+" scale"); |
|
1044 } |
|
1045 } else |
|
1046 p.println("0 "+(max_y+min_y)+" translate\n1 -1 scale"); |
|
1047 |
|
1048 p.println("/Helvetica findfont 12 scalefont setfont"); |
|
1049 p.println("0.5 setlinewidth"); |
|
1050 |
|
1051 Enumeration e1=vertices.elements(); |
|
1052 while (e1.hasMoreElements()) |
|
1053 ((Vertex)(e1.nextElement())).PS(p); |
|
1054 |
|
1055 e1=splines.elements(); |
|
1056 while (e1.hasMoreElements()) |
|
1057 ((Spline)(e1.nextElement())).PS(p); |
|
1058 |
|
1059 if (printable) p.println("showpage"); |
|
1060 |
|
1061 f.close(); |
|
1062 } |
|
1063 } |
|
1064 |
|
1065 /**** Return value of function calcPoint ****/ |
|
1066 |
|
1067 class Points { |
|
1068 public Point p,q; |
|
1069 |
|
1070 public Points(Point p1,Point p2) { |
|
1071 p=p1;q=p2; |
|
1072 } |
|
1073 } |
|
1074 |