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