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