![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to dag.ms CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10dc / vol2 / dag|
Return to dag.ms CVS log | Up to [Research Unix] / researchv10dc / vol2 / dag |
1.1 root 1: .so ../ADM/mac
2: .XX dag 147 "Dag \(em A Program for Drawing Directed Graphs"
3: . \" PE - end of picture
4: .de PE
5: .in
6: .X "END US PE
7: .nr X .65v
8: .if \\n($1>0 .X "SP \\nX PE"
9: .\"...bp
10: ..
11: .EQ
12: delim $$
13: .EN
14: .ds HP +2
15: .ds DG \fIdag\fP
16: .ds PO P\s-2OST\s+2S\s-2CRIPT\s+2
17: .ds PC \fIpic\fP
18: .fp 5 CW
19: .\"..ND "October 19, 1987 Revised June 11, 1989"
20: .TL
21: Dag \(em A Program for Drawing Directed Graphs\(dg
22: .AU
23: E. R. Gansner
24: S. C. North
25: K. P. Vo
26: .AI
27: .MH
28: .AB
29: .PP
30: .I Dag
31: is a \*(PC or \*(PO preprocessor that draws directed graphs.
32: It works well on acyclic graphs and other graphs that can be drawn
33: as hierarchies.
34: Graph descriptions contain nodes, edges, and optional control statements.
35: Here is a drawing of a graph from Forrester's book, \fIWorld Dynamics\fP
36: (Wright-Allen, Cambridge, MA, 1971).
37: It took 2.1 CPU seconds on a VAX-8650 to make this drawing.
38: .PS 3.5 3
39: arrowht = 0.111111;
40: arrowwid = 0.055556;
41: define Ellipse % [ellipse wid $2 ht $3 $1] %
42: .ps 4
43: Node0: Ellipse("S8",0.750000,0.500000) at (3.250000,7.250000);
44: Node1: Ellipse("9",0.750000,0.500000) at (3.250000,6.250000);
45: Node2: Ellipse("S24",0.750000,0.500000) at (1.138889,7.250000);
46: Node3: Ellipse("25",0.750000,0.500000) at (1.888889,6.250000);
47: Node4: Ellipse("27",0.750000,0.500000) at (0.375000,3.250000);
48: Node5: Ellipse("S1",0.750000,0.500000) at (15.083333,8.250000);
49: Node6: Ellipse("2",0.750000,0.500000) at (14.527778,7.250000);
50: Node7: Ellipse("10",0.750000,0.500000) at (15.638889,7.250000);
51: Node8: Ellipse("S35",0.750000,0.500000) at (10.319444,8.250000);
52: Node9: Ellipse("43",0.750000,0.500000) at (9.319444,7.250000);
53: Node10: Ellipse("36",0.750000,0.500000) at (11.319444,7.250000);
54: Node11: Ellipse("S30",0.750000,0.500000) at (8.069444,6.250000);
55: Node12: Ellipse("31",0.750000,0.500000) at (5.944444,4.250000);
56: Node13: Ellipse("33",0.750000,0.500000) at (8.444444,5.250000);
57: Node14: Ellipse("42",0.750000,0.500000) at (4.194444,5.250000);
58: Node15: Ellipse("T1",0.750000,0.500000) at (6.194444,1.250000);
59: Node16: Ellipse("26",0.750000,0.500000) at (3.111111,5.250000);
60: Node17: Ellipse("T24",0.750000,0.500000) at (2.416667,1.250000);
61: Node18: Ellipse("3",0.750000,0.500000) at (5.944444,5.250000);
62: Node19: Ellipse("16",0.750000,0.500000) at (14.486111,5.250000);
63: Node20: Ellipse("17",0.750000,0.500000) at (11.527778,6.250000);
64: Node21: Ellipse("18",0.750000,0.500000) at (12.194444,5.250000);
65: Node22: Ellipse("11",0.750000,0.500000) at (6.944444,5.250000);
66: Node23: Ellipse("14",0.750000,0.500000) at (16.527778,5.250000);
67: Node24: Ellipse("13",0.750000,0.500000) at (13.527778,6.250000);
68: Node25: Ellipse("12",0.750000,0.500000) at (12.944444,4.250000);
69: Node26: Ellipse("32",0.750000,0.500000) at (5.444444,3.250000);
70: Node27: Ellipse("T30",0.750000,0.500000) at (8.319444,2.250000);
71: Node28: Ellipse("34",0.750000,0.500000) at (7.444444,4.250000);
72: Node29: Ellipse("4",0.750000,0.500000) at (4.569444,4.250000);
73: Node30: Ellipse("15",0.750000,0.500000) at (13.694444,3.250000);
74: Node31: Ellipse("19",0.750000,0.500000) at (10.777778,5.250000);
75: Node32: Ellipse("29",0.750000,0.500000) at (9.944444,3.250000);
76: Node33: Ellipse("37",0.750000,0.500000) at (10.319444,7.250000);
77: Node34: Ellipse("39",0.750000,0.500000) at (12.527778,6.250000);
78: Node35: Ellipse("41",0.750000,0.500000) at (9.444444,4.250000);
79: Node36: Ellipse("38",0.750000,0.500000) at (5.444444,6.250000);
80: Node37: Ellipse("40",0.750000,0.500000) at (10.027778,6.250000);
81: Node38: Ellipse("23",0.750000,0.500000) at (4.444444,2.250000);
82: Node39: Ellipse("5",0.750000,0.500000) at (3.444444,3.250000);
83: Node40: Ellipse("21",0.750000,0.500000) at (8.444444,4.250000);
84: Node41: Ellipse("20",0.750000,0.500000) at (11.444444,4.250000);
85: Node42: Ellipse("28",0.750000,0.500000) at (10.444444,4.250000);
86: Node43: Ellipse("6",0.750000,0.500000) at (1.125000,2.250000);
87: Node44: Ellipse("T35",0.750000,0.500000) at (3.444444,2.250000);
88: Node45: Ellipse("22",0.750000,0.500000) at (4.444444,3.250000);
89: Node46: Ellipse("7",0.750000,0.500000) at (1.125000,1.250000);
90: Node47: Ellipse("T8",0.750000,0.500000) at (1.125000,0.250000);
91: spline -> from (3.250000,7.000000) to (3.250000,6.500000);
92: spline -> from (3.513889,6.069444) to (4.013889,5.472222);
93: spline -> from (3.000000,6.055556) to (2.444444,5.333333) to (2.416667,5.166667) to (2.375000,5.000000) to (2.375000,2.500000) to (2.569444,2.208333) to (2.763889,1.916667) to (3.069444,1.875000) to (5.833333,1.319444);
94: spline -> from (1.361111,7.041667) to (1.736111,6.472222);
95: spline -> from (1.083333,7.000000) to (0.416667,3.500000);
96: spline -> from (1.888889,6.000000) to (1.875000,4.500000) to (1.875000,4.250000) to (1.875000,4.000000) to (1.875000,2.500000) to (2.027778,2.194444) to (2.166667,1.888889) to (2.375000,1.875000) to (5.833333,1.305556);
97: spline -> from (2.180556,6.097222) to (2.888889,5.444444);
98: spline -> from (0.375000,3.000000) to (0.375000,2.500000) to (0.486111,2.194444) to (0.597222,1.902778) to (0.750000,1.875000) to (2.138889,1.416667);
99: spline -> from (14.916667,8.027778) to (14.652778,7.486111);
100: spline -> from (15.250000,8.027778) to (15.513889,7.486111);
101: spline -> from (14.305556,7.055556) to (7.097222,6.625000) to (6.875000,6.611111) to (6.597222,6.361111) to (6.305556,6.125000) to (6.041667,5.486111);
102: spline -> from (14.611111,7.000000) to (14.722222,6.500000) to (14.722222,6.277778) to (14.708333,6.069444) to (14.555556,5.500000);
103: spline -> from (14.319444,7.041667) to (11.513889,6.500000);
104: spline -> from (14.750000,7.041667) to (15.208333,6.347222) to (15.250000,6.166667) to (15.277778,6.000000) to (15.277778,2.500000) to (15.250000,2.375000) to (15.208333,2.250000) to (6.569444,1.291667);
105: spline -> from (14.486111,7.000000) to (14.347222,6.305556) to (14.208333,6.097222) to (14.055556,5.902778) to (12.527778,5.361111);
106: spline -> from (15.638889,7.000000) to (15.083333,6.888889) to (7.430556,6.611111) to (7.222222,6.305556) to (7.013889,6.000000) to (6.972222,5.500000);
107: spline -> from (15.888889,7.055556) to (16.458333,6.333333) to (16.500000,6.166667) to (16.527778,6.000000) to (16.527778,5.500000);
108: spline -> from (15.958333,7.125000) to (16.986111,6.444444) to (17.138889,6.222222) to (17.277778,6.000000) to (17.277778,2.500000) to (16.763889,2.208333) to (16.250000,1.916667) to (15.277778,1.875000) to (6.569444,1.277778);
109: spline -> from (15.638889,7.000000) to (13.861111,6.375000);
110: spline -> from (15.680556,7.000000) to (15.750000,6.500000) to (15.763889,6.250000) to (15.777778,6.000000) to (15.777778,5.500000) to (15.750000,5.263889) to (15.708333,5.041667) to (15.277778,4.958333) to (13.291667,4.347222);
111: spline -> from (10.055556,8.069444) to (9.513889,7.458333);
112: spline -> from (10.583333,8.069444) to (11.125000,7.458333);
113: spline -> from (8.958333,7.180556) to (5.444444,6.500000);
114: spline -> from (9.527778,7.041667) to (9.888889,6.486111);
115: spline -> from (11.152778,7.027778) to (10.847222,6.388889) to (10.819444,6.194444) to (10.777778,6.000000) to (10.777778,5.500000);
116: spline -> from (7.944444,6.013889) to (7.791667,5.375000) to (7.638889,5.138889) to (7.472222,4.916667) to (6.194444,4.444444);
117: spline -> from (8.194444,6.013889) to (8.361111,5.500000);
118: spline -> from (6.027778,4.000000) to (6.138889,3.500000) to (6.166667,3.250000) to (6.194444,3.000000) to (6.194444,1.500000);
119: spline -> from (5.791667,4.027778) to (5.555556,3.486111);
120: spline -> from (8.194444,5.069444) to (6.750000,4.500000) to (6.597222,4.402778) to (6.763889,4.180556) to (8.138889,2.472222);
121: spline -> from (8.236111,5.041667) to (7.652778,4.458333);
122: spline -> from (4.319444,5.013889) to (4.486111,4.500000);
123: spline -> from (3.402778,5.097222) to (4.319444,4.430556);
124: spline -> from (5.652778,5.097222) to (4.750000,4.472222);
125: spline -> from (14.416667,5.000000) to (14.319444,4.500000) to (14.263889,4.333333) to (14.208333,4.166667) to (13.819444,3.486111);
126: spline -> from (11.319444,6.041667) to (10.875000,5.486111);
127: spline -> from (12.194444,5.000000) to (12.194444,4.500000) to (12.083333,4.194444) to (11.972222,3.902778) to (11.819444,3.875000) to (10.277778,3.361111);
128: spline -> from (6.902778,5.000000) to (4.847222,4.416667);
129: spline -> from (16.263889,5.069444) to (14.930556,4.291667) to (14.819444,4.222222) to (14.708333,4.152778) to (13.916667,3.444444);
130: spline -> from (13.527778,6.000000) to (13.027778,5.902778) to (11.013889,5.444444);
131: spline -> from (12.944444,4.000000) to (10.291667,3.347222);
132: spline -> from (5.180556,3.069444) to (4.638889,2.458333);
133: spline -> from (7.444444,4.000000) to (9.597222,3.347222);
134: spline -> from (4.277778,4.083333) to (3.652778,3.458333);
135: spline -> from (13.333333,3.180556) to (6.541667,1.347222);
136: spline -> from (10.444444,5.138889) to (8.638889,4.458333);
137: spline -> from (10.972222,5.041667) to (11.305556,4.486111);
138: spline -> from (10.666667,5.013889) to (10.513889,4.500000);
139: spline -> from (9.625000,3.125000) to (8.583333,2.430556);
140: spline -> from (10.402778,7.000000) to (12.430556,6.486111);
141: spline -> from (10.319444,7.000000) to (9.652778,6.625000) to (9.347222,6.458333) to (9.333333,6.222222) to (9.305556,6.000000) to (9.430556,4.500000);
142: spline -> from (10.319444,7.000000) to (9.819444,6.888889) to (6.097222,6.597222) to (5.444444,6.500000);
143: spline -> from (10.319444,7.000000) to (10.125000,6.486111);
144: spline -> from (12.708333,6.027778) to (13.041667,5.388889) to (13.111111,5.277778) to (13.180556,5.166667) to (13.625000,4.375000) to (13.666667,4.180556) to (13.694444,4.000000) to (13.694444,3.500000);
145: spline -> from (9.597222,4.027778) to (9.833333,3.486111);
146: spline -> from (5.319444,6.013889) to (4.638889,4.500000);
147: spline -> from (10.250000,6.041667) to (10.625000,5.472222);
148: spline -> from (4.319444,2.013889) to (2.736111,1.375000);
149: spline -> from (4.763889,2.111111) to (5.916667,1.416667);
150: spline -> from (3.111111,3.138889) to (1.430556,2.388889);
151: spline -> from (3.444444,3.000000) to (3.444444,2.500000);
152: spline -> from (3.708333,3.069444) to (4.250000,2.458333);
153: spline -> from (8.444444,4.000000) to (7.944444,3.888889) to (4.944444,3.611111) to (4.444444,3.500000);
154: spline -> from (11.777778,4.138889) to (13.388889,3.402778);
155: spline -> from (10.291667,4.027778) to (10.055556,3.486111);
156: spline -> from (1.125000,2.000000) to (1.125000,1.500000);
157: spline -> from (4.444444,3.000000) to (4.444444,2.500000);
158: spline -> from (4.180556,3.069444) to (3.638889,2.458333);
159: spline -> from (1.125000,1.000000) to (1.125000,0.500000);
160: .ps
161: .PE
162: .AE
163: .FS
164: \(dg This is a revised version of |reference(dag spe).
165: .FE
166: .NH 1
167: Introduction
168: .PP
169: Directed graphs have many applications in computing,
170: such as describing data structures, finite automata,
171: data flow, procedure calls, and software configuration dependencies.
172: A picture is a good way to represent a directed graph.
173: It is seldom easy to understand much about a graph from a list of edges,
174: but with a picture one can quickly find individual nodes,
175: groups of related nodes, and trace paths in the graph.
176: The main obstacle is that it can be difficult and tedious to
177: draw graphs by hand.
178: .PP
179: .I Dag
180: is a program that draws directed graphs from edge lists.
181: It does particularly well on acyclic graphs such as trees, DAGs,
182: and other hierarchical graphs.
183: It reads descriptions in a concise language
184: and outputs drawings in \*(PC |reference(latest pic)
185: or \*(PO |reference(adobe postscript) format;
186: a typical use is
187: .P1
188: dag file | pic | troff
189: .P2
190: .........
191: .NH 1
192: Basics
193: .PP
194: This section describes how to give a basic description of a graph
195: as a list of edges.
196: Figure 1 shows a \*(DG description, and a reduced copy of the resulting picture.
197: .KS
198: .PS 6.5 4.5
199: arrowht = 0.111111;
200: arrowwid = 0.055556;
201: define Ellipse % [ellipse wid $2 ht $3 $1] %
202: .ps 4
203: box invis at (-10,0);
204: Node0: Ellipse("5th Edition",1.375000,0.500000) at (5.763889,10.250000);
205: Node1: Ellipse("6th Edition",1.375000,0.500000) at (4.111111,9.250000);
206: Node2: Ellipse("PWB 1.0",0.875000,0.500000) at (7.416667,9.250000);
207: Node3: Ellipse("Interdata",1.125000,0.500000) at (6.180556,8.250000);
208: Node4: Ellipse("Wollongong",1.250000,0.500000) at (3.388889,8.250000);
209: Node5: Ellipse("Mini Unix",1.125000,0.500000) at (4.819444,8.250000);
210: Node6: Ellipse("1 BSD",0.750000,0.500000) at (0.694444,8.250000);
211: Node7: Ellipse("LSX",0.750000,0.500000) at (2.138889,8.250000);
212: Node8: Ellipse("7th Edition",1.375000,0.500000) at (3.944444,7.250000);
213: Node9: Ellipse("Unix/TS 3.0",1.375000,0.500000) at (8.194444,5.250000);
214: Node10: Ellipse("PWB 2.0",0.875000,0.500000) at (7.166667,7.250000);
215: Node11: Ellipse("8th Edition",1.375000,0.500000) at (5.694444,2.250000);
216: Node12: Ellipse("32V",0.750000,0.500000) at (4.944444,6.250000);
217: Node13: Ellipse("V7M",0.750000,0.500000) at (1.111111,3.250000);
218: Node14: Ellipse("Ultrix-11",1.125000,0.500000) at (1.402778,1.250000);
219: Node15: Ellipse("Xenix",0.750000,0.500000) at (3.944444,6.250000);
220: Node16: Ellipse("UniPlus+",1.000000,0.500000) at (2.819444,6.250000);
221: Node17: Ellipse("9th Edition",1.375000,0.500000) at (6.555556,1.250000);
222: Node18: Ellipse("2 BSD",0.750000,0.500000) at (0.708333,5.250000);
223: Node19: Ellipse("2.8 BSD",0.875000,0.500000) at (2.652778,2.250000);
224: Node20: Ellipse("2.9 BSD",0.875000,0.500000) at (2.652778,1.250000);
225: Node21: Ellipse("3 BSD",0.750000,0.500000) at (4.944444,5.250000);
226: Node22: Ellipse("4 BSD",0.750000,0.500000) at (4.944444,4.250000);
227: Node23: Ellipse("4.1 BSD",0.875000,0.500000) at (4.638889,3.250000);
228: Node24: Ellipse("4.2 BSD",0.875000,0.500000) at (4.319444,2.250000);
229: Node25: Ellipse("4.3 BSD",0.875000,0.500000) at (5.180556,1.250000);
230: Node26: Ellipse("Ultrix-32",1.125000,0.500000) at (3.930556,1.250000);
231: Node27: Ellipse("PWB 1.2",0.875000,0.500000) at (7.430556,8.250000);
232: Node28: Ellipse("USG 1.0",0.875000,0.500000) at (9.555556,8.250000);
233: Node29: Ellipse("CB Unix 1",1.125000,0.500000) at (11.083333,7.250000);
234: Node30: Ellipse("USG 2.0",0.875000,0.500000) at (9.541667,7.250000);
235: Node31: Ellipse("CB Unix 2",1.125000,0.500000) at (11.083333,6.250000);
236: Node32: Ellipse("CB Unix 3",1.125000,0.500000) at (11.361111,5.250000);
237: Node33: Ellipse("Unix/TS++",1.125000,0.500000) at (10.319444,4.250000);
238: Node34: Ellipse("PDP-11 Sys V",1.500000,0.500000) at (11.930556,4.250000);
239: Node35: Ellipse("USG 3.0",0.875000,0.500000) at (9.569444,6.250000);
240: Node36: Ellipse("Unix/TS 1.0",1.375000,0.500000) at (8.194444,6.250000);
241: Node37: Ellipse("TS 4.0",0.750000,0.500000) at (10.263889,3.250000);
242: Node38: Ellipse("System V.0",1.250000,0.500000) at (10.263889,2.250000);
243: Node39: Ellipse("System V.2",1.250000,0.500000) at (10.263889,1.250000);
244: Node40: Ellipse("System V.3",1.250000,0.500000) at (10.263889,0.250000);
245: Node41: Ellipse("10th Edition",1.375000,0.500000) at (6.555556,0.250000);
246: spline -> from (5.305556,10.069444) to (4.430556,9.472222);
247: spline -> from (6.222222,10.069444) to (7.138889,9.444444);
248: spline -> from (4.638889,9.097222) to (5.819444,8.444444);
249: spline -> from (3.888889,9.013889) to (3.555556,8.486111);
250: spline -> from (4.333333,9.013889) to (4.666667,8.486111);
251: spline -> from (3.513889,9.125000) to (0.986111,8.402778);
252: spline -> from (3.611111,9.083333) to (2.402778,8.430556);
253: spline -> from (7.416667,9.000000) to (7.430556,8.500000);
254: spline -> from (7.791667,9.125000) to (9.222222,8.416667);
255: spline -> from (5.916667,8.027778) to (4.416667,7.430556);
256: spline -> from (6.194444,8.000000) to (6.222222,7.500000) to (6.263889,7.250000) to (6.291667,7.000000) to (6.375000,6.500000) to (6.430556,6.305556) to (6.486111,6.111111) to (7.791667,5.458333);
257: spline -> from (6.486111,8.041667) to (6.972222,7.472222);
258: spline -> from (0.694444,8.000000) to (0.708333,5.500000);
259: spline -> from (4.402778,7.055556) to (5.319444,6.625000) to (5.625000,6.486111) to (5.666667,6.236111) to (5.694444,6.000000) to (5.694444,2.500000);
260: spline -> from (4.250000,7.027778) to (4.750000,6.458333);
261: spline -> from (3.416667,7.083333) to (1.513889,6.486111) to (1.486111,6.236111) to (1.444444,6.000000) to (1.444444,5.500000) to (1.430556,5.250000) to (1.402778,5.000000) to (1.152778,3.500000);
262: spline -> from (3.458333,7.069444) to (2.319444,6.625000) to (2.000000,6.500000) to (2.013889,6.250000) to (2.013889,6.000000) to (2.388889,4.500000) to (2.388889,4.333333) to (2.375000,4.166667) to (2.000000,3.500000) to (1.916667,3.250000) to (1.819444,3.000000) to (1.750000,2.500000) to (1.708333,2.291667) to (1.652778,2.083333) to (1.472222,1.500000);
263: spline -> from (3.944444,7.000000) to (3.944444,6.500000);
264: spline -> from (3.597222,7.027778) to (3.041667,6.472222);
265: spline -> from (8.513889,5.027778) to (10.055556,3.458333);
266: spline -> from (7.152778,7.000000) to (7.138889,6.500000) to (7.180556,6.263889) to (7.208333,6.041667) to (7.513889,5.875000) to (7.930556,5.486111);
267: spline -> from (5.972222,2.027778) to (6.375000,1.486111);
268: spline -> from (4.944444,6.000000) to (4.944444,5.500000);
269: spline -> from (1.111111,3.000000) to (1.111111,2.500000) to (1.152778,2.277778) to (1.180556,2.069444) to (1.333333,1.500000);
270: spline -> from (1.000000,5.097222) to (1.652778,4.458333) to (1.791667,4.291667) to (1.930556,4.138889) to (2.291667,3.388889) to (2.361111,3.222222) to (2.430556,3.069444) to (2.583333,2.500000);
271: spline -> from (2.652778,2.000000) to (2.652778,1.500000);
272: spline -> from (2.333333,2.083333) to (1.652778,1.472222);
273: spline -> from (4.944444,5.000000) to (4.944444,4.500000);
274: spline -> from (4.847222,4.013889) to (4.708333,3.500000);
275: spline -> from (4.527778,3.013889) to (4.388889,2.500000);
276: spline -> from (4.263889,3.111111) to (2.972222,2.430556);
277: spline -> from (4.930556,3.055556) to (5.472222,2.486111);
278: spline -> from (4.569444,2.041667) to (5.000000,1.472222);
279: spline -> from (4.194444,2.013889) to (4.013889,1.500000);
280: spline -> from (7.347222,8.000000) to (7.222222,7.500000);
281: spline -> from (9.902778,8.097222) to (10.791667,7.458333);
282: spline -> from (9.555556,8.000000) to (9.541667,7.500000);
283: spline -> from (11.083333,7.000000) to (11.083333,6.500000);
284: spline -> from (9.555556,7.000000) to (9.569444,6.500000);
285: spline -> from (11.180556,6.000000) to (11.305556,5.500000);
286: spline -> from (11.777778,5.083333) to (12.958333,4.486111) to (13.472222,4.111111) to (12.819444,3.902778) to (10.611111,3.347222);
287: spline -> from (11.055556,5.041667) to (10.541667,4.486111);
288: spline -> from (11.541667,5.013889) to (11.805556,4.500000);
289: spline -> from (10.305556,4.000000) to (10.277778,3.500000);
290: spline -> from (9.236111,6.083333) to (8.472222,5.472222);
291: spline -> from (8.194444,6.000000) to (8.194444,5.500000);
292: spline -> from (10.263889,3.000000) to (10.263889,2.500000);
293: spline -> from (10.263889,2.000000) to (10.263889,1.500000);
294: spline -> from (10.263889,1.000000) to (10.263889,0.500000);
295: spline -> from (6.555556,1.000000) to (6.555556,0.500000);
296: .ps
297: .PE
298: .sp -6i
299:
300:
301: .ps 7p
302: .vs 9p
303: .ft 5
304: .nf
305: \&.GD 4 4
306: "5th Edition" "6th Edition" "PWB 1.0";
307: "6th Edition" "Interdata" "Wollongong"
308: "Mini Unix" "1 BSD" "LSX";
309: "Interdata" "7th Edition" "Unix/TS 3.0"
310: "PWB 2.0";
311: "7th Edition" "8th Edition" "32V" "V7M"
312: "Ultrix-11" "Xenix" "UniPlus+";
313: "V7M" "Ultrix-11";
314: "8th Edition" "9th Edition";
315: "9th Edition" "10th Edition";
316: "1 BSD" "2 BSD";
317: "2 BSD" "2.8 BSD";
318: "2.8 BSD" "2.9 BSD" "Ultrix-11";
319: "32V" "3 BSD";
320: "3 BSD" "4 BSD";
321: "4 BSD" "4.1 BSD";
322: "4.1 BSD" "4.2 BSD" "2.8 BSD" "8th Edition";
323: "4.2 BSD" "4.3 BSD" "Ultrix-32";
324: "PWB 1.0" "PWB 1.2" "USG 1.0";
325: "PWB 1.2" "PWB 2.0";
326: "USG 1.0" "CB Unix 1" "USG 2.0";
327: "CB Unix 1" "CB Unix 2";
328: "CB Unix 2" "CB Unix 3";
329: "CB Unix 3" "Unix/TS++" "PDP-11 Sys V";
330: "USG 2.0" "USG 3.0";
331: "USG 3.0" "Unix/TS 3.0";
332: "PWB 2.0" "Unix/TS 3.0";
333: "Unix/TS 1.0" "Unix/TS 3.0";
334: "Unix/TS 3.0" "TS 4.0";
335: "Unix/TS++" "TS 4.0";
336: "CB Unix 3" "TS 4.0";
337: "TS 4.0" "System V.0";
338: "System V.0" "System V.2";
339: "System V.2" "System V.3";
340: \&.GE
341: .ps
342: .vs
343: .ft
344: .fi
345: .ce
346: \fBFigure 1.\fR
347: .KE
348: .PP
349: Graph descriptions begin with \f5.GD\fP (or on some systems,
350: .CW .GS )
351: and end with \f5.GE\fP.
352: If the maximum width and height of the drawing are given on the
353: \f5GD\fP line, the drawing is scaled appropriately.
354: The drawing in Figure 1 has a 4 inch by 4 inch bounding box.
355: .PP
356: A graph description is a list of semicolon-terminated statements.
357: All the statements in Figure 1 are \fIedge\fP statements
358: that name a tail node and a list of head nodes.
359: Edges fan out from the tail node.
360: The statement \f5"5th Edition" "6th Edition" "PWB 1.0";\fP
361: makes an edge from \f55th Edition\fP to \f56th Edition\fP,
362: and another from \f55th Edition\fP to \f5PWB 1.0\fP.
363: Because the syntax of edge statements is simple, graph descriptions can be
364: generated from the output of other tools, such as \fIcflow\fP, profilers,
365: or \fImake\fP utilities, without much effort. There is also a verbose
366: form for edge statements:
367: .P1
368: edge from "5th Edition" to "6th Edition", to "PWB 1.0";
369: .P2
370: .PP
371: The keywords \f5edge\fP, \f5from\fP, \f5to\fP, and commas are optional.
372: Node names may be quoted to protect white space, punctuation,
373: or \*(DG keywords.
374: .PP
375: As shown, \*(DG places nodes in ranks so that edges
376: point downward if possible. Nodes are ordered from
377: left to right within ranks to reduce edge crossings and long edges.
378: If there are cycles in the graph it is not possible for all edges to
379: point downward, so some edges will be inverted.
380: For instance, the following graph contains a cycle $a -> b ->c -> a$,
381: so the edge $c -> a$ points upward.
382: .KS
383: .ft 5
384: .sp .5i
385: .in 1i
386: .nf
387: \&.GD
388: edge from a to b;
389: edge from b to c;
390: edge from c to a;
391: \&.GE
392: .sp .5i
393: .in
394: .ft
395: .ce
396: \fBFigure 2.\fR
397: .fi
398: .sp -2.5i
399: .PS 5.5 2
400: arrowht = 0.069444;
401: arrowwid = 0.027778;
402: define Ellipse % [ellipse wid $2 ht $3 $1] %
403: box invis at (-2.5,0);
404: .ps 10
405: Node0: Ellipse("a",0.750000,0.500000) at (0.750000,2.250000);
406: Node1: Ellipse("b",0.750000,0.500000) at (1.125000,1.250000);
407: Node2: Ellipse("c",0.750000,0.500000) at (0.750000,0.250000);
408: spline -> from (0.875000,2.013889) to (1.041667,1.500000);
409: spline -> from (1.000000,1.013889) to (0.833333,0.500000);
410: spline -> from (0.666667,0.500000) to (0.444444,1.111111) to (0.458333,1.305556) to (0.458333,1.500000) to (0.625000,2.013889);
411: .ps
412: .PE
413: .KE
414: Edges that point backward can be made:
415: .KS
416: .sp .5i
417: .P1
418: \&.GD
419: backedge from a to b;
420: edge from b to c;
421: edge from c to a;
422: \&.GE
423: .P2
424: .sp .5i
425: .ce
426: \fBFigure 3.\fR
427: .sp -2.5i
428: .PS 5.5 2
429: .ps 10
430: box invis at (-2.5,0);
431: arrowht = 0.069444;
432: arrowwid = 0.027778;
433: define Ellipse % [ellipse wid $2 ht $3 $1] %
434: .ps 10
435: Node0: Ellipse("a",0.750000,0.500000) at (0.750000,0.250000);
436: Node1: Ellipse("b",0.750000,0.500000) at (0.750000,2.250000);
437: Node2: Ellipse("c",0.750000,0.500000) at (1.125000,1.250000);
438: spline -> from (0.875000,2.013889) to (1.041667,1.500000);
439: spline <- from (0.625000,2.013889) to (0.458333,1.500000) to (0.458333,1.305556) to (0.444444,1.111111) to (0.666667,0.500000);
440: spline -> from (1.000000,1.013889) to (0.833333,0.500000);
441: .ps
442: .PE
443: .KE
444: .PP
445: \fIPath\fP statements create chains of edges.
446: Here is a more compact way to describe part of Figure 1:
447: .P1
448: path from "Unix/TS 1.0" to "Unix/TS 3.0" to "TS 4.0" to "System V.0";
449: .P2
450: .PP
451: Beginning a graph description with \f5.GR\fP instead
452: of \f5.GD\fP makes edges point from left-to-right as
453: shown in Figure 4.
454: (\f5GD\fP means ``graph down'' and \f5GR\fP ``graph right.'')
455: .KF
456: .PS 5
457: arrowht = 0.111111;
458: arrowwid = 0.055556;
459: define Ellipse % [ellipse wid $2 ht $3 $1] %
460: .ps 12
461: Node0: Ellipse("Newton",0.750000,0.500000) at (0.375000,2.125000);
462: Node1: Ellipse("Moore",0.750000,0.500000) at (1.625000,2.125000);
463: Node2: Ellipse("Veblen",0.750000,0.500000) at (3.000000,1.750000);
464: Node3: Ellipse("Birkhoff",1.000000,0.500000) at (3.000000,2.500000);
465: Node4: Ellipse("Whitney",0.875000,0.500000) at (4.430556,2.500000);
466: Node5: Ellipse("Church",0.750000,0.500000) at (4.430556,1.750000);
467: Node6: Ellipse("Turing",0.750000,0.500000) at (5.805556,0.250000);
468: Node7: Ellipse("Rosser",0.750000,0.500000) at (5.805556,3.250000);
469: Node8: Ellipse("Ritchie",0.875000,0.500000) at (5.805556,2.500000);
470: Node9: Ellipse("Kleene",0.750000,0.500000) at (5.805556,1.750000);
471: Node10: Ellipse("Scott",0.750000,0.500000) at (5.805556,1.000000);
472: spline -> from (0.750000,2.125000) to (1.250000,2.125000);
473: spline -> from (1.930556,2.277778) to (2.527778,2.416667);
474: spline -> from (1.944444,2.000000) to (2.638889,1.833333);
475: spline -> from (3.375000,1.750000) to (4.055556,1.750000);
476: spline -> from (3.500000,2.500000) to (4.000000,2.500000);
477: spline -> from (4.652778,1.555556) to (5.500000,1.152778);
478: spline -> from (4.805556,1.750000) to (5.430556,1.750000);
479: spline -> from (4.791667,1.805556) to (5.527778,2.305556);
480: spline -> from (4.791667,1.819444) to (5.458333,3.166667);
481: spline -> from (4.583333,1.513889) to (5.583333,0.458333);
482: .ps
483: .sp -.75i
484: .PE
485: .ce
486: \fBFigure 4.\fR
487: .KE
488: .PP
489: A backpath is a chain of back-edges.
490: .P1
491: backpath from Subaru to Honda to Ferrari;
492: .P2
493: .NH 1
494: Node Attributes
495: .PP
496: This section explains how to control the way nodes are drawn.
497: The node attributes are shape, size, label,
498: pointsize of the label, and color.
499: By default nodes are drawn as \(12\(aa\(aa by \(34\(aa\(aa ellipses
500: labeled with the node name in 14-point type.
501: The size may be increased to fit the label.
502: .PP
503: \f5draw nodes\fP sets default attributes for nodes created
504: afterward in a graph description;
505: nodes already created are not affected.
506: \f5draw\fP \fInodelist\fP sets attributes of individual nodes.
507: Nodes in the \fInodelist\fP are created if they do not already exist.
508: .NH 2
509: Node Shapes
510: .PP
511: The pre-defined shapes are \f5Box\fP, \f5Square\fP, \f5Circle\fP, \f5Doublecircle\fP, \f5Ellipse\fP, \f5Diamond\fP, and \f5Plaintext\fP.
512: Shape names are capitalized to avoid conflict with \*(PC keywords.
513: Here is an example involving node shapes:
514: .P1
515: edge from a to b;
516: draw ETA, Apollo, NeXT as Box;
517: draw nodes as Plaintext;
518: edge from x to y;
519: .P2
520: \f5a\fP and \f5b\fP are drawn as ellipses;
521: \f5ETA\fP, \f5Apollo\fP, and \f5NeXT\fP as boxes;
522: and \f5x\fP and \f5y\fP as \f5Plaintext\fP because
523: \f5Plaintext\fP became the default before \f5x\fP and \f5y\fP were created.
524: .PP
525: .EQ
526: delim off
527: .EN
528: User-defined node shapes are created by writing \*(PC macros or \*(PO procedures.
529: Shapes have three arguments: the node label, width, and height.
530: In a \*(PC macro these are \f5$1, $2,\fP and \f5$3\fP.
531: In a \*(PO procedure the arguments are passed on the stack.
532: To draw a node, \*(DG moves to its center point and calls the shape
533: with the necessary arguments.
534: It is usually convenient to define macros within the graph description
535: in a block between \f5.PS\fP and \f5.PE\fP.
536: The contents of this block are passed straight through \*(DG
537: and appear in the graphics code after the standard prologue but
538: before any nodes or edges are drawn.
539: .PP
540: There are two limitations on user-defined shapes.
541: First, \*(DG assumes height and width are independent.
542: So if a user-defined shape has a fixed aspect ratio,
543: fine-tuning may be needed to make the drawing look right.
544: Second, because \*(DG doesn't know how to compute the boundary
545: of user-defined shapes, and \*(PC macros aren't general enough for the job,
546: edges in \*(PC drawings are clipped to a node's bounding rectangle.
547: The second limitation does not apply to shapes written in \*(PO
548: since the user also supplies a clipping procedure (see Appendix B).
549: Figure 5 shows an example shape macro in \*(PC.
550: .KF
551: .sp .3i
552: .P1
553: \&.GD
554: \&.PS
555: define Triplecircle % [
556: circle rad .5 * $2;
557: circle rad .475 * $2 at last circle.c;
558: circle rad .45 * $2 at last circle.c;
559: $1 at last circle.c;
560: ] %
561: \&.PE
562: edge from 1 to 2;
563: draw 1 as Triplecircle height 1 width 1;
564: draw 2 as Circle height 1 width 1;
565: \&.GE
566: .P2
567: .sp .4i
568: .ce
569: \fBFigure 5.\fR
570: .sp -3i
571: .PS 6
572: box invis at (-5,0);
573: arrowht = 0.111111;
574: arrowwid = 0.055556;
575: define Circle % [circle rad $2/2; $1 at last circle.c] %
576: define Triplecircle % [ circle rad .5 * $2; circle rad .475 * $2 at last circle.c; circle rad .45 * $2 at last circle.c; $1 at last circle.c; ] %
577: .ps 14
578: Node0: Triplecircle("1",1.000000,1.000000) at (0.500000,2.000000);
579: Node1: Circle("2",1.000000,1.000000) at (0.500000,0.500000);
580: spline -> solid from (0.500000,1.500000) to (0.500000,1.000000);
581: .ps
582: .PE
583: .KE
584: .......
585: .NH 2
586: Node Labels
587: .PP
588: The default label of a node is its name.
589: Another label can be set, which is particularly
590: useful to allow distinct nodes to share a common label.
591: .P1
592: draw "/usr/src/cmd" label "cmd";
593: draw "/usr/local/src/cmd" label "cmd";
594: .P2
595: .EQ
596: delim $$
597: .EN
598: .NH 2
599: Node Colors
600: .PP
601: Nodes may have color in \*(PO drawings.
602: A color value is a string that is passed to the
603: procedure \f5dagsetcolor\fP in the emitted \*(PO code.
604: In the standard \*(PO prologue this procedure
605: accepts a hue-saturation-brightness triple.
606: Macros for common colors can be defined in a \f5.PS/.PE\fP block:
607: .P1
608: \&.PS
609: /red [.1 1 1] def
610: \&.PE
611: draw important_node color red;
612: .P2
613: Other interpretations of color values may be implemented
614: by redefining \f5dagsetcolor\fP and defining compatible node shapes.
615: Appendix B explains how to make gray-scale shaded nodes this way.
616: .NH 1
617: Edge Attributes
618: .PP
619: This section explains how to control the way edges are drawn.
620: The edge attributes are label,
621: pointsize of the label, ink style, color, and weight.
622: Attributes may be set when edges are created.
623: \f5draw edges\fP sets default attributes for edges
624: created afterward in the graph description.
625: Previously created edges cannot be changed because
626: unlike nodes, edges do not have identifiers.
627: .NH 2
628: Edge Labels
629: .PP
630: A label is a text string or fragment of executable graphics code
631: drawn at the midpoint of an edge. Text labels are preferred.
632: Graphics code is available for extreme cases, but it is discouraged
633: because it is dependent on the target graphics language.
634: Graphics code is enclosed in curly braces as shown below.
635: .P1
636: edge from a to b label "x" ;
637: edge from b to c label {circle rad .1};
638: .P2
639: .PP
640: Figure 6 is the description of a finite automaton with labeled edges
641: and its picture.
642: .EQ
643: delim off
644: .EN
645: .KF
646: .P1
647: \&.GR 6
648: draw nodes as Circle width .5 height .5;
649: draw LR_0 LR_3 LR_4 LR_8 as Doublecircle width .5 height .5;
650: draw edges pointsize 8;
651: LR_0 LR_2 label "SS(B)";
652: LR_0 LR_1 label "SS(S)";
653: LR_1 LR_3 label "S($end)";
654: LR_2 LR_6 label "SS(b)";
655: LR_2 LR_5 label "SS(a)";
656: LR_2 LR_4 label "S(A)";
657: LR_5 LR_7 label "S(b)";
658: LR_5 LR_5 label "S(a)";
659: LR_6 LR_6 label "S(b)";
660: LR_6 LR_5 label "S(a)";
661: LR_7 LR_8 label "S(b)";
662: LR_7 LR_5 label "S(a)";
663: LR_8 LR_6 label "S(b)";
664: LR_8 LR_5 label "S(a)";
665: \&.GE
666: .P2
667: .PS 6
668: arrowht = 0.069444;
669: arrowwid = 0.027778;
670: define Box % [box wid $2 ht $3 $1] %
671: define Square % [box wid $2 ht $2 $1] %
672: define Circle % [circle rad $2/2; $1 at last circle.c] %
673: define Ellipse % [ellipse wid $2 ht $3 $1] %
674: define Diamond % [move down $3/2; line up $3/2 right $2/2 then up $3/2 left $2/2 then down $3/2 left $2/2 then down $3/2 right $2/2; move up $3/2; $1;] %
675: define Doublecircle % [circle rad $2/2; circle rad .9*$2/2 at last circle.c; $1 at last circle.c] %
676: define Plaintext % [box invis wid $2 ht $3 $1] %
677: .ps 11
678: Node0: Doublecircle("LR_0",0.500000,0.500000) at (0.250000,1.972222);
679: Node1: Doublecircle("LR_3",0.500000,0.500000) at (2.250000,2.625000);
680: Node2: Doublecircle("LR_4",0.500000,0.500000) at (2.250000,0.875000);
681: Node3: Doublecircle("LR_8",0.500000,0.500000) at (4.250000,1.375000);
682: Node4: Circle("LR_2",0.500000,0.500000) at (1.250000,1.319444);
683: Node5: Circle("LR_1",0.500000,0.500000) at (1.250000,2.625000);
684: Node6: Circle("LR_6",0.500000,0.500000) at (5.250000,0.750000);
685: Node7: Circle("LR_5",0.500000,0.500000) at (2.250000,1.625000);
686: Node8: Circle("LR_7",0.500000,0.500000) at (3.250000,1.875000);
687: .ps
688: .ps 8
689: spline -> from (0.430556,2.152778) to (1.027778,2.500000);
690: move to (0.750000,2.333333); "SS(S)";
691: spline -> from (0.430556,1.791667) to (1.027778,1.444444);
692: move to (0.750000,1.597222); "SS(B)";
693: spline -> from (4.000000,1.347222) to (3.500000,1.291667) to (3.250000,1.319444) to (3.000000,1.333333) to (2.472222,1.513889);
694: move to (3.250000,1.319444); "S(a)";
695: spline -> from (4.430556,1.208333) to (5.027778,0.875000);
696: move to (4.750000,1.027778); "S(b)";
697: spline -> from (1.458333,1.180556) to (2.013889,0.972222);
698: move to (1.750000,1.069444); "S(A)";
699: spline -> from (1.486111,1.416667) to (2.013889,1.555556);
700: move to (1.750000,1.486111); "SS(a)";
701: spline -> from (1.388889,1.111111) to (1.875000,0.625000) to (2.180556,0.319444) to (2.347222,0.291667) to (2.500000,0.250000) to (4.000000,0.250000) to (4.180556,0.291667) to (4.361111,0.319444) to (5.027778,0.638889);
702: move to (3.208333,0.250000); "SS(b)";
703: spline -> from (1.500000,2.625000) to (2.000000,2.625000);
704: move to (1.750000,2.625000); "S($end)";
705: spline -> from (5.000000,0.750000) to (3.500000,0.750000) to (3.333333,0.791667) to (3.166667,0.819444) to (2.402778,1.416667);
706: move to (3.722222,0.750000); "S(a)";
707: spline -> from (5.194444,1.000000) to (5.138889,1.125000) to (5.250000,1.250000) to (5.361111,1.125000) to (5.305556,1.000000);
708: move to (5.250000,1.250000); "S(b)";
709: spline -> from (2.194444,1.875000) to (2.138889,2.000000) to (2.250000,2.125000) to (2.361111,2.000000) to (2.305556,1.875000);
710: move to (2.250000,2.125000); "S(a)";
711: spline -> from (2.486111,1.708333) to (2.750000,1.666667) to (3.000000,1.819444);
712: move to (2.750000,1.666667); "S(b)";
713: spline -> from (3.000000,1.819444) to (2.750000,1.861111) to (2.486111,1.708333);
714: move to (2.750000,1.861111); "S(a)";
715: spline -> from (3.458333,1.736111) to (4.027778,1.472222);
716: move to (3.750000,1.597222); "S(b)";
717: .ps
718: .PE
719: .sp -1.2i
720: .ce
721: \fBFigure 6.\fR
722: .KE
723: .EQ
724: delim $$
725: .EN
726: .NH 2
727: Edge Weights
728: .PP
729: Edge weights or costs are integers.
730: Increasing the weight of an edge makes \*(DG try to shorten it.
731: The default weight is 1; \*(DG internally increases the
732: weight of long edges to improve the drawing.
733: In the Unix History graph of Figure 1, we might want to favor the edge
734: \f5"2 BSD" "2.8 BSD"\fP over \f5"4.1 BSD" "2.8 BSD"\fP. This suggests:
735: .P1
736: edge from "2 BSD" to "2.8 BSD" weight 1000;
737: .P2
738: .PP
739: It's best to use large values to swamp the internal adjustment,
740: otherwise a little experimenting with weights will probably be needed.
741: .NH 2
742: Edge Styles
743: .PP
744: The graph description may name the ``ink'' or line style
745: for edges: \f5solid\fP, \f5dotted\fP, \f5dashed\fP, or \f5invis\fP.
746: .P1
747: edge from "2 BSD" to "2.8 BSD" dashed;
748: .P2
749: .PP
750: Unfortunately \fItroff\fP does not have dotted or dashed splines
751: so they appear as solid splines in \*(PC output.
752: .NH 2
753: Edge Colors
754: .PP
755: Edge colors are much like node colors.
756: .P1
757: edge from "2 BSD" to "2.8 BSD" color "[.2 1 1 ]";
758: draw edges "[.3 .5 .5]";
759: .P2
760: .NH 1
761: Spacing Control
762: .PP
763: \fISeparate\fP statements set the minimum spacing in inches between
764: adjacent nodes or ranks.
765: .P1
766: separate nodes .75;
767: separate ranks 2;
768: separate ranks 2 exactly;
769: separate ranks 2 equally;
770: .P2
771: .PP
772: Because some drawings have edges that are almost horizontal
773: and thus hard to read, \*(DG may increase the separation
774: between certain ranks to improve the drawing.
775: When this happens, a side-effect is that ranks are not equally spaced.
776: The
777: .CW equally
778: qualifier
779: tells \*(DG to maintain even
780: spacing between ranks, which may be more aesthetically pleasing and readable;
781: .CW exactly
782: inhibits the rank spacing adjustment.
783: .PP
784: Another kind of spacing control is requested by putting the
785: keyword \f5fill\fP on the \f5GD\fP line. This forces the drawing
786: to fill the bounding box by increasing the node and rank separations.
787: \&\f5fill\fP overrides ``\f5separate ranks exactly\fP''. For example:
788: .P1
789: \&.GD 6 8 fill
790: .P2
791: .NH 1
792: Rank Assignment Control
793: .PP
794: The graph description may state that certain nodes should be
795: placed on the minimum or maximum rank,
796: or be kept as a group on the same rank.
797: .P1
798: minimum rank root1 root2 root3;
799: maximum rank leaf38 leaf39;
800: same rank add sub mul div shift;
801: .P2
802: .PP
803: Figure 7 is another drawing of Forrester's \fIWorld Dynamics\fP graph.
804: In this drawing, (1) source nodes
805: \fIS1, S8, S24, S30\fP and \fIS35\fP
806: are constrained to appear at the minimum rank, (2) target nodes
807: \fIT1, T8, T24, T30\fP and \fIT35\fP are to appear at the maximum rank, and (3)
808: all other nodes stay at the same ranks as in the drawing of the abstract.
809: .KF
810: .PS 3.5
811: arrowht = 0.111111;
812: arrowwid = 0.055556;
813: define Ellipse % [ellipse wid $2 ht $3 $1] %
814: .ps 4
815: Node0: Ellipse("S8",0.750000,0.500000) at (4.444444,7.250000);
816: Node1: Ellipse("S24",0.750000,0.500000) at (2.097222,7.250000);
817: Node2: Ellipse("S1",0.750000,0.500000) at (8.319444,7.250000);
818: Node3: Ellipse("S35",0.750000,0.500000) at (10.819444,7.250000);
819: Node4: Ellipse("S30",0.750000,0.500000) at (17.000000,7.250000);
820: Node5: Ellipse("T8",0.750000,0.500000) at (0.375000,0.250000);
821: Node6: Ellipse("T24",0.750000,0.500000) at (2.041667,0.250000);
822: Node7: Ellipse("T1",0.750000,0.500000) at (7.569444,0.250000);
823: Node8: Ellipse("T35",0.750000,0.500000) at (3.041667,0.250000);
824: Node9: Ellipse("T30",0.750000,0.500000) at (16.458333,0.250000);
825: Node10: Ellipse("9",0.750000,0.500000) at (4.444444,6.250000);
826: Node11: Ellipse("25",0.750000,0.500000) at (2.569444,6.250000);
827: Node12: Ellipse("27",0.750000,0.500000) at (1.375000,1.250000);
828: Node13: Ellipse("2",0.750000,0.500000) at (8.263889,6.250000);
829: Node14: Ellipse("10",0.750000,0.500000) at (13.944444,6.250000);
830: Node15: Ellipse("43",0.750000,0.500000) at (11.319444,6.250000);
831: Node16: Ellipse("36",0.750000,0.500000) at (10.319444,6.250000);
832: Node17: Ellipse("31",0.750000,0.500000) at (18.194444,3.250000);
833: Node18: Ellipse("33",0.750000,0.500000) at (17.569444,4.250000);
834: Node19: Ellipse("42",0.750000,0.500000) at (4.819444,5.250000);
835: Node20: Ellipse("26",0.750000,0.500000) at (3.319444,5.250000);
836: Node21: Ellipse("3",0.750000,0.500000) at (5.819444,5.250000);
837: Node22: Ellipse("16",0.750000,0.500000) at (8.319444,4.250000);
838: Node23: Ellipse("17",0.750000,0.500000) at (9.513889,5.250000);
839: Node24: Ellipse("18",0.750000,0.500000) at (9.319444,4.250000);
840: Node25: Ellipse("11",0.750000,0.500000) at (6.819444,5.250000);
841: Node26: Ellipse("14",0.750000,0.500000) at (11.694444,4.250000);
842: Node27: Ellipse("13",0.750000,0.500000) at (13.569444,5.250000);
843: Node28: Ellipse("12",0.750000,0.500000) at (16.069444,4.250000);
844: Node29: Ellipse("32",0.750000,0.500000) at (14.458333,2.250000);
845: Node30: Ellipse("34",0.750000,0.500000) at (17.013889,3.250000);
846: Node31: Ellipse("4",0.750000,0.500000) at (5.319444,4.250000);
847: Node32: Ellipse("15",0.750000,0.500000) at (8.819444,2.250000);
848: Node33: Ellipse("19",0.750000,0.500000) at (10.319444,4.250000);
849: Node34: Ellipse("29",0.750000,0.500000) at (13.347222,2.250000);
850: Node35: Ellipse("37",0.750000,0.500000) at (12.444444,6.250000);
851: Node36: Ellipse("39",0.750000,0.500000) at (12.152778,3.250000);
852: Node37: Ellipse("41",0.750000,0.500000) at (14.569444,4.250000);
853: Node38: Ellipse("38",0.750000,0.500000) at (11.069444,5.250000);
854: Node39: Ellipse("40",0.750000,0.500000) at (12.069444,5.250000);
855: Node40: Ellipse("23",0.750000,0.500000) at (3.375000,1.250000);
856: Node41: Ellipse("5",0.750000,0.500000) at (2.375000,3.250000);
857: Node42: Ellipse("21",0.750000,0.500000) at (4.055556,3.250000);
858: Node43: Ellipse("20",0.750000,0.500000) at (8.819444,3.250000);
859: Node44: Ellipse("28",0.750000,0.500000) at (13.152778,3.250000);
860: Node45: Ellipse("6",0.750000,0.500000) at (0.375000,2.250000);
861: Node46: Ellipse("22",0.750000,0.500000) at (3.375000,2.250000);
862: Node47: Ellipse("7",0.750000,0.500000) at (0.375000,1.250000);
863: spline -> from (4.444444,7.000000) to (4.444444,6.500000);
864: spline -> from (2.236111,7.013889) to (2.458333,6.486111);
865: spline -> from (1.972222,7.013889) to (1.819444,6.500000) to (1.777778,6.250000) to (1.722222,6.000000) to (1.388889,1.500000);
866: spline -> from (8.305556,7.000000) to (8.277778,6.500000);
867: spline -> from (8.583333,7.069444) to (13.194444,6.583333) to (13.944444,6.500000);
868: spline -> from (10.972222,7.027778) to (11.208333,6.486111);
869: spline -> from (10.666667,7.027778) to (10.430556,6.486111);
870: spline -> from (16.944444,7.000000) to (16.861111,6.500000) to (16.847222,6.250000) to (16.819444,6.000000) to (16.819444,4.500000) to (16.847222,4.250000) to (16.861111,4.000000) to (17.194444,3.875000) to (17.916667,3.416667);
871: spline -> from (17.138889,7.013889) to (17.347222,6.430556) to (17.402778,6.208333) to (17.444444,6.000000) to (17.555556,4.500000);
872: spline -> from (4.569444,6.013889) to (4.736111,5.500000);
873: spline -> from (4.319444,6.013889) to (4.152778,5.500000) to (4.152778,5.291667) to (4.138889,5.083333) to (4.750000,3.430556) to (4.791667,3.208333) to (4.819444,3.000000) to (4.819444,1.500000) to (4.861111,1.361111) to (4.888889,1.236111) to (7.236111,0.375000);
874: spline -> from (2.569444,6.000000) to (2.569444,5.500000) to (2.611111,5.291667) to (2.638889,5.083333) to (3.194444,3.500000) to (3.277778,3.319444) to (3.347222,3.152778) to (3.680556,2.875000) to (4.055556,2.347222) to (4.111111,2.166667) to (4.152778,2.000000) to (4.194444,1.500000) to (4.375000,1.208333) to (4.555556,0.916667) to (4.819444,0.875000) to (7.208333,0.333333);
875: spline -> from (2.791667,6.041667) to (3.166667,5.472222);
876: spline -> from (1.569444,1.041667) to (1.902778,0.486111);
877: spline -> from (7.916667,6.152778) to (6.000000,5.472222);
878: spline -> from (8.236111,6.000000) to (8.208333,5.500000) to (8.222222,5.250000) to (8.236111,5.000000) to (8.291667,4.500000);
879: spline -> from (8.555556,6.097222) to (9.291667,5.444444);
880: spline -> from (8.069444,6.027778) to (7.694444,5.375000) to (7.652778,5.180556) to (7.611111,5.000000) to (7.583333,4.500000) to (7.583333,4.250000) to (7.569444,4.000000) to (7.569444,0.500000);
881: spline -> from (8.402778,6.013889) to (8.597222,5.500000) to (8.680556,5.333333) to (8.763889,5.166667) to (9.180556,4.486111);
882: spline -> from (13.944444,6.000000) to (13.194444,5.902778) to (6.986111,5.472222);
883: spline -> from (14.069444,6.013889) to (14.236111,5.500000) to (14.402778,4.972222) to (14.097222,4.902778) to (12.041667,4.347222);
884: spline -> from (14.250000,6.097222) to (15.250000,5.305556) to (15.291667,5.152778) to (15.319444,5.000000) to (15.319444,1.500000) to (15.291667,1.375000) to (15.250000,1.250000) to (7.930556,0.305556);
885: spline -> from (13.944444,6.000000) to (13.694444,5.486111);
886: spline -> from (14.277778,6.138889) to (16.000000,5.291667) to (16.041667,5.138889) to (16.069444,5.000000) to (16.069444,4.500000);
887: spline -> from (11.236111,6.000000) to (11.125000,5.500000);
888: spline -> from (11.541667,6.041667) to (11.916667,5.472222);
889: spline -> from (10.319444,6.000000) to (10.319444,4.500000);
890: spline -> from (18.194444,3.000000) to (17.083333,1.083333) to (16.611111,1.000000) to (16.138889,0.916667) to (7.944444,0.277778);
891: spline -> from (18.194444,3.000000) to (17.611111,2.902778) to (14.819444,2.333333);
892: spline -> from (17.861111,4.097222) to (18.569444,3.625000) to (18.847222,3.444444) to (18.902778,3.222222) to (18.944444,3.000000) to (18.944444,1.500000) to (18.916667,1.361111) to (18.875000,1.222222) to (16.777778,0.375000);
893: spline -> from (17.402778,4.027778) to (17.138889,3.486111);
894: spline -> from (4.972222,5.027778) to (5.208333,4.486111);
895: spline -> from (3.652778,5.138889) to (5.027778,4.402778);
896: spline -> from (5.666667,5.027778) to (5.402778,4.500000);
897: spline -> from (8.236111,4.000000) to (8.125000,3.500000) to (8.138889,3.333333) to (8.138889,3.180556) to (8.444444,2.875000) to (8.680556,2.486111);
898: spline -> from (9.736111,5.055556) to (10.152778,4.472222);
899: spline -> from (9.555556,4.055556) to (10.527778,3.361111) to (10.750000,3.208333) to (10.972222,3.069444) to (13.013889,2.361111);
900: spline -> from (6.583333,5.055556) to (5.541667,4.458333);
901: spline -> from (11.375000,4.125000) to (10.347222,3.472222) to (10.138889,3.333333) to (9.916667,3.208333) to (9.055556,2.444444);
902: spline -> from (13.347222,5.041667) to (10.513889,4.458333);
903: spline -> from (16.055556,4.000000) to (16.041667,3.500000) to (16.013889,3.361111) to (15.972222,3.236111) to (13.347222,2.500000);
904: spline -> from (14.458333,2.000000) to (13.902778,1.875000) to (3.750000,1.277778);
905: spline -> from (16.958333,3.000000) to (13.902778,2.597222) to (13.347222,2.500000);
906: spline -> from (4.972222,4.166667) to (2.708333,3.361111);
907: spline -> from (8.625000,2.027778) to (7.708333,0.486111);
908: spline -> from (10.319444,4.000000) to (9.819444,3.888889) to (4.430556,3.291667);
909: spline -> from (10.319444,4.000000) to (9.125000,3.388889);
910: spline -> from (10.513889,4.041667) to (13.138889,3.500000);
911: spline -> from (13.569444,2.041667) to (14.013889,1.361111) to (14.083333,1.291667) to (14.152778,1.222222) to (16.138889,0.375000);
912: spline -> from (12.555556,6.013889) to (12.736111,5.500000) to (12.777778,5.250000) to (12.819444,5.000000) to (12.819444,4.500000) to (12.791667,4.333333) to (12.750000,4.166667) to (12.305556,3.472222);
913: spline -> from (12.763889,6.125000) to (14.319444,5.472222) to (14.750000,5.291667) to (14.750000,5.138889) to (14.736111,5.000000) to (14.625000,4.500000);
914: spline -> from (12.138889,6.097222) to (11.319444,5.444444);
915: spline -> from (12.319444,6.013889) to (12.152778,5.500000);
916: spline -> from (11.791667,3.166667) to (9.166667,2.347222);
917: spline -> from (14.375000,4.027778) to (14.027778,3.375000) to (13.958333,3.263889) to (13.888889,3.166667) to (13.347222,2.500000);
918: spline -> from (11.069444,5.000000) to (10.513889,4.930556) to (5.652778,4.361111);
919: spline -> from (11.888889,5.027778) to (10.458333,4.486111);
920: spline -> from (3.069444,1.097222) to (2.277778,0.444444);
921: spline -> from (3.375000,1.000000) to (3.986111,0.902778) to (7.208333,0.319444);
922: spline -> from (2.041667,3.138889) to (0.666667,2.402778);
923: spline -> from (2.291667,3.000000) to (2.180556,2.500000) to (2.152778,2.250000) to (2.125000,2.000000) to (2.125000,1.500000) to (2.166667,1.347222) to (2.194444,1.194444) to (2.847222,0.458333);
924: spline -> from (2.458333,3.000000) to (2.569444,2.500000) to (2.638889,2.333333) to (2.694444,2.180556) to (3.000000,1.875000) to (3.236111,1.486111);
925: spline -> from (3.861111,3.041667) to (3.513889,2.486111);
926: spline -> from (8.819444,3.000000) to (8.819444,2.500000);
927: spline -> from (13.222222,3.000000) to (13.305556,2.500000);
928: spline -> from (0.375000,2.000000) to (0.375000,1.500000);
929: spline -> from (3.375000,2.000000) to (3.375000,1.500000);
930: spline -> from (3.152778,2.041667) to (2.694444,1.347222) to (2.694444,1.236111) to (2.694444,1.125000) to (2.944444,0.486111);
931: spline -> from (0.375000,1.000000) to (0.375000,0.500000);
932: .ps
933: .PE
934: .ce
935: \fBFigure 7.\fR
936: .KE
937: .PP
938: Figure 8 illustrates how a time-line can be
939: created with \f5same rank\fP statements.
940: .KF
941: .PS 5.346320
942: arrowht = 0.111111;
943: arrowwid = 0.055556;
944: define Box % [box wid $2 ht $3 $1] %
945: define Plaintext % [box invis wid $2 ht $3 $1] %
946: .ps 9
947: Node0: Plaintext("1971",1.069444,0.597222) at (0.805556,18.958333);
948: Node1: Plaintext("1972",1.069444,0.597222) at (0.805556,17.861111);
949: Node2: Plaintext("1973",1.069444,0.597222) at (0.805556,16.763889);
950: Node3: Plaintext("1974",1.069444,0.597222) at (0.805556,15.666667);
951: Node4: Plaintext("1975",1.069444,0.597222) at (0.805556,14.569444);
952: Node5: Plaintext("1976",1.069444,0.597222) at (0.805556,13.472222);
953: Node6: Plaintext("1977",1.069444,0.597222) at (0.805556,12.375000);
954: Node7: Plaintext("1978",1.069444,0.597222) at (0.805556,11.277778);
955: Node8: Plaintext("1979",1.069444,0.597222) at (0.805556,10.180556);
956: Node9: Plaintext("1980",1.069444,0.597222) at (0.805556,9.083333);
957: Node10: Plaintext("1981",1.069444,0.597222) at (0.805556,7.986111);
958: Node11: Plaintext("1982",1.069444,0.597222) at (0.805556,6.888889);
959: Node12: Plaintext("1983",1.069444,0.597222) at (0.805556,5.791667);
960: Node13: Plaintext("1984",1.069444,0.597222) at (0.805556,4.694444);
961: Node14: Plaintext("1985",1.069444,0.597222) at (0.805556,3.597222);
962: Node15: Plaintext("1986",1.069444,0.597222) at (0.805556,2.500000);
963: Node16: Plaintext("1987",1.069444,0.597222) at (0.805556,1.402778);
964: Node17: Plaintext("future",1.611111,0.597222) at (0.805556,0.305556);
965: Node18: Box("Thompson sh",2.958333,0.597222) at (10.194444,18.958333);
966: Node19: Box("Ritchie cpp",2.958333,0.597222) at (15.666667,17.861111);
967: Node20: Box("SCCS",1.069444,0.597222) at (3.166667,15.666667);
968: Node21: Box("make",1.069444,0.597222) at (6.833333,13.472222);
969: Node22: Box("Bourne sh",2.416667,0.597222) at (11.708333,13.472222);
970: Node23: Box("Mashey sh",2.416667,0.597222) at (8.986111,13.472222);
971: Node24: Box("Reiser cpp",2.694444,0.597222) at (15.666667,11.277778);
972: Node25: Box("augmented make",3.777778,0.597222) at (5.236111,11.277778);
973: Node26: Box("Form sh",1.888889,0.597222) at (12.361111,11.277778);
974: Node27: Box("Csh",0.805556,0.597222) at (8.986111,11.277778);
975: Node28: Box("build",1.347222,0.597222) at (6.666667,10.180556);
976: Node29: Box("emacs",1.347222,0.597222) at (13.208333,9.083333);
977: Node30: Box("vi",0.750000,0.597222) at (10.097222,9.083333);
978: Node31: Box("RCS",0.805556,0.597222) at (1.986111,7.986111);
979: Node32: Box("esh",0.805556,0.597222) at (13.708333,7.986111);
980: Node33: Box("vsh",0.805556,0.597222) at (12.152778,7.986111);
981: Node34: Box("<curses>",2.152778,0.597222) at (10.430556,7.986111);
982: Node35: Box("etc.",1.069444,0.597222) at (10.430556,6.888889);
983: Node36: Box("ksh",0.805556,0.597222) at (11.083333,5.791667);
984: Node37: Box("8th ed. make",3.236111,0.597222) at (4.763889,4.694444);
985: Node38: Box("nmake",1.347222,0.597222) at (10.583333,3.597222);
986: Node39: Box("Versioned files",4.041667,0.597222) at (4.166667,3.597222);
987: Node40: Box("ncpp",1.069444,0.597222) at (15.013889,2.500000);
988: Node41: Box("nmake+viewpaths",4.041667,0.597222) at (9.388889,2.500000);
989: Node42: Box("mk",0.750000,0.597222) at (6.555556,2.500000);
990: Node43: Box("ksh-i",1.347222,0.597222) at (12.333333,2.500000);
991: Node44: Box("Ansi cpp",2.152778,0.597222) at (15.013889,1.402778);
992: Node45: Box("n2make",1.611111,0.597222) at (12.388889,1.402778);
993: Node46: Box("extended directories",5.388889,0.597222) at (8.638889,1.402778);
994: Node47: Box("fdelta",1.611111,0.597222) at (2.388889,1.402778);
995: Node48: Box("Advanced Software Development Environment",11.069444,0.597222) at (10.513889,0.305556);
996: .ps
997: .ps 14
998: spline -> from (10.333333,18.666667) to (10.513889,18.083333) to (10.597222,17.819444) to (10.666667,17.569444) to (11.638889,13.763889);
999: spline -> from (10.111111,18.666667) to (9.055556,13.763889);
1000: spline -> from (15.666667,17.569444) to (15.666667,11.569444);
1001: spline -> from (3.694444,15.486111) to (5.472222,14.597222) to (5.513889,14.430556) to (5.541667,14.277778) to (5.541667,12.666667) to (5.583333,12.500000) to (5.611111,12.347222) to (7.500000,11.319444) to (7.569444,11.152778) to (7.625000,10.986111) to (7.680556,10.472222) to (7.708333,10.180556) to (7.722222,9.888889) to (7.736111,9.375000) to (7.750000,9.083333) to (7.750000,8.791667) to (7.750000,6.083333) to (7.791667,5.791667) to (7.819444,5.500000) to (7.902778,4.986111) to (7.958333,4.694444) to (8.013889,4.402778) to (9.916667,3.805556);
1002: spline -> from (3.500000,15.375000) to (4.000000,14.666667) to (4.041667,14.472222) to (4.069444,14.277778) to (4.069444,13.763889) to (4.111111,13.555556) to (4.138889,13.361111) to (5.083333,11.569444);
1003: spline -> from (3.138889,15.375000) to (2.875000,11.569444) to (2.861111,11.277778) to (2.847222,10.986111) to (2.777778,8.277778) to (2.777778,7.986111) to (2.777778,7.694444) to (2.777778,4.986111) to (2.819444,4.819444) to (2.847222,4.652778) to (3.805556,3.888889);
1004: spline -> from (2.791667,15.375000) to (2.194444,14.652778) to (2.166667,14.458333) to (2.125000,14.277778) to (1.986111,8.277778);
1005: spline -> from (6.694444,13.180556) to (6.513889,12.597222) to (6.444444,12.458333) to (6.375000,12.333333) to (5.555556,11.569444);
1006: spline -> from (7.083333,13.180556) to (7.458333,12.500000) to (7.527778,12.388889) to (7.597222,12.291667) to (8.083333,11.402778) to (8.138889,11.194444) to (8.194444,10.986111) to (8.236111,10.472222) to (8.250000,10.180556) to (8.250000,9.888889) to (8.250000,6.083333) to (8.291667,5.861111) to (8.319444,5.652778) to (8.569444,4.902778) to (8.638889,4.777778) to (8.708333,4.666667) to (10.069444,3.888889);
1007: spline -> from (11.833333,13.180556) to (12.277778,11.569444);
1008: spline -> from (12.513889,13.180556) to (13.875000,12.416667) to (13.916667,12.250000) to (13.944444,12.083333) to (13.944444,11.569444) to (13.972222,11.277778) to (13.986111,10.986111) to (14.208333,9.375000) to (14.194444,9.180556) to (14.180556,8.986111) to (13.847222,8.277778);
1009: spline -> from (11.583333,13.180556) to (11.125000,11.569444) to (11.083333,11.277778) to (11.041667,10.986111) to (11.041667,9.375000) to (11.083333,9.194444) to (11.111111,9.027778) to (11.861111,8.277778);
1010: spline -> from (8.986111,13.180556) to (8.986111,11.569444);
1011: spline -> from (15.638889,10.986111) to (15.041667,2.791667);
1012: spline -> from (5.750000,10.986111) to (6.333333,10.472222);
1013: spline -> from (5.208333,10.986111) to (4.777778,4.986111);
1014: spline -> from (12.319444,10.986111) to (12.194444,9.375000) to (12.222222,9.194444) to (12.236111,9.013889) to (12.861111,8.083333) to (12.861111,7.944444) to (12.861111,7.819444) to (12.680556,7.180556) to (12.611111,7.013889) to (12.527778,6.847222) to (11.486111,6.083333);
1015: spline -> from (8.986111,10.986111) to (8.986111,8.277778) to (9.013889,7.986111) to (9.041667,7.694444) to (9.097222,7.180556) to (9.152778,6.930556) to (9.208333,6.694444) to (9.902778,6.472222) to (10.680556,6.027778);
1016: spline -> from (6.708333,9.888889) to (7.222222,4.986111) to (7.277778,4.805556) to (7.319444,4.638889) to (9.111111,2.791667);
1017: spline -> from (13.388889,8.791667) to (13.597222,8.277778);
1018: spline -> from (10.472222,8.861111) to (11.750000,8.194444);
1019: spline -> from (10.194444,8.791667) to (10.347222,8.277778);
1020: spline -> from (2.097222,7.694444) to (2.208333,7.180556) to (2.250000,6.888889) to (2.277778,6.597222) to (2.277778,4.986111) to (2.305556,4.694444) to (2.333333,4.402778) to (3.500000,3.888889);
1021: spline -> from (1.902778,7.694444) to (1.819444,7.180556) to (1.791667,6.888889) to (1.763889,6.597222) to (1.763889,3.888889) to (1.805556,3.638889) to (1.833333,3.388889) to (2.305556,1.694444);
1022: spline -> from (13.652778,7.694444) to (13.597222,7.180556) to (13.555556,6.944444) to (13.500000,6.708333) to (11.486111,5.944444);
1023: spline -> from (11.958333,7.694444) to (11.222222,6.083333);
1024: spline -> from (10.430556,7.694444) to (10.430556,7.180556);
1025: spline -> from (10.986111,5.500000) to (10.986111,4.986111) to (10.916667,4.694444) to (10.833333,4.402778) to (10.638889,3.888889);
1026: spline -> from (10.680556,5.722222) to (6.902778,4.402778) to (6.722222,4.347222) to (6.527778,4.305556) to (5.138889,3.888889);
1027: spline -> from (11.486111,5.666667) to (13.500000,4.722222) to (13.541667,4.555556) to (13.569444,4.402778) to (13.569444,1.694444) to (13.458333,1.347222) to (13.347222,1.013889) to (13.194444,0.986111) to (11.666667,0.597222);
1028: spline -> from (10.680556,5.555556) to (9.805556,4.763889) to (9.736111,4.583333) to (9.666667,4.402778) to (9.583333,3.888889) to (9.680556,3.541667) to (9.763889,3.208333) to (9.916667,3.180556) to (11.666667,2.694444);
1029: spline -> from (5.416667,4.402778) to (6.486111,3.652778) to (6.527778,3.472222) to (6.555556,3.305556) to (6.555556,2.791667);
1030: spline -> from (10.638889,3.888889) to (10.638889,4.402778) to (10.722222,4.694444) to (10.791667,4.986111) to (10.986111,5.500000);
1031: spline -> from (11.250000,3.472222) to (14.486111,2.638889);
1032: spline -> from (10.152778,3.305556) to (9.666667,2.791667);
1033: spline -> from (4.291667,3.305556) to (4.805556,1.347222) to (5.125000,1.180556) to (5.444444,1.027778) to (8.472222,0.597222);
1034: spline -> from (15.013889,2.208333) to (15.013889,1.694444);
1035: spline -> from (10.472222,2.208333) to (11.694444,1.694444);
1036: spline -> from (9.111111,2.208333) to (8.805556,1.694444);
1037: spline -> from (14.555556,1.111111) to (11.972222,0.597222);
1038: spline -> from (11.708333,1.111111) to (10.944444,0.597222);
1039: spline -> from (9.319444,1.111111) to (10.083333,0.597222);
1040: spline -> from (3.069444,1.111111) to (7.819444,0.597222);
1041: .ps
1042: .PE
1043: .ce
1044: \fBFigure 8.\fR
1045: .SP
1046: .KE
1047: .PP
1048: Forcing a group of nodes to be on the same rank can cause \fIflat\fP-edges, i.e.,
1049: edges that point sideways instead of upward or downward.
1050: If possible, \*(DG draws flat-edges from left to right.
1051: (This means that, as a side-effect, left-to-right order in a rank can
1052: be controlled by creating invisible flat-edges.)
1053: Figure 9 shows a graph description
1054: in which the relative placements of nodes are completely specified.
1055: The edge crossing is unavoidable.
1056: .KF
1057: .sp .3i
1058: .P1 10n
1059: \&.GD
1060: same rank 1 2;
1061: same rank 3 4;
1062: 1 4;
1063: 2 3;
1064: 1 2 invis;
1065: 3 4 invis;
1066: \&.GE
1067: .P2
1068: .sp .6i
1069: .ce
1070: \fBFigure 9.\fR
1071: .sp -2i
1072: .PS 6 2
1073: .ps 10
1074: box invis at (-2,0);
1075: arrowwid = 0.050000;
1076: arrowht = 0.150000;
1077: define Ellipse % [ellipse wid $2 ht $3 $1] %
1078: Box0: Ellipse("1",0.750000,0.500000) at (0.375000,1.250000);
1079: Box1: Ellipse("2",0.750000,0.500000) at (1.375000,1.250000);
1080: Box2: Ellipse("3",0.750000,0.500000) at (0.375000,0.250000);
1081: Box3: Ellipse("4",0.750000,0.500000) at (1.375000,0.250000);
1082: spline -> solid from (0.583333,1.041667) to (1.166667,0.458333);
1083: spline -> solid from (1.166667,1.041667) to (0.583333,0.458333);
1084: .ps
1085: .PE
1086: .KE
1087: .PP
1088: If edges are \f5ordered\fP, \*(DG automatically places head nodes on the
1089: same rank and creates invisible flat-edges. Figure 10
1090: is a small part of a parse tree.
1091: Ordered edges are needed to correctly represent the grammar.
1092: .KF
1093: .P1
1094: \&.GD
1095: ordered edge from "for-stmt" to "for" "var" "=" "expr1" "to" "expr2";
1096: ordered edge from "expr1" to "left_op" "*" "right_op";
1097: \&.GE
1098: .P2
1099: .PS 4.000000 1.702128
1100: arrowht = 0.111111;
1101: arrowwid = 0.055556;
1102: define Box % [box wid $2 ht $3 $1] %
1103: .ps 9
1104: Node0: Box("for-stmt",1.000000,0.500000) at (3.000000,2.250000);
1105: Node1: Box("for",0.750000,0.500000) at (0.500000,1.250000);
1106: Node2: Box("var",0.750000,0.500000) at (1.500000,1.250000);
1107: Node3: Box("=",0.750000,0.500000) at (2.500000,1.250000);
1108: Node4: Box("expr1",0.750000,0.500000) at (3.500000,1.250000);
1109: Node5: Box("to",0.750000,0.500000) at (4.500000,1.250000);
1110: Node6: Box("expr2",0.750000,0.500000) at (5.500000,1.250000);
1111: Node7: Box("left_op",0.875000,0.500000) at (2.444444,0.250000);
1112: Node8: Box("*",0.750000,0.500000) at (3.500000,0.250000);
1113: Node9: Box("right_op",1.000000,0.500000) at (4.625000,0.250000);
1114: .ps
1115: .ps 14
1116: spline -> from (2.500000,2.097222) to (0.763889,1.500000);
1117: spline -> from (2.500000,2.000000) to (1.833333,1.500000);
1118: spline -> from (2.833333,2.000000) to (2.611111,1.500000);
1119: spline -> from (3.166667,2.000000) to (3.388889,1.500000);
1120: spline -> from (3.500000,2.000000) to (4.166667,1.500000);
1121: spline -> from (3.500000,2.097222) to (5.236111,1.500000);
1122: spline -> from (3.152778,1.000000) to (2.680556,0.500000);
1123: spline -> from (3.500000,1.000000) to (3.500000,0.500000);
1124: spline -> from (3.875000,1.000000) to (4.375000,0.500000);
1125: .ps
1126: .PE
1127: .ce
1128: \fBFigure 10.\fR
1129: .KE
1130: .PP
1131: There are many other properties of a graph drawing that one
1132: might want to control,
1133: but it is difficult to build a good tool that achieves
1134: many, possibly conflicting, aesthetic goals.
1135: Users can exercise some control over node placement by setting edge
1136: weights and creating invisible edges.
1137: For finer control over drawings we suggest
1138: changing the drawing with a graphical editor or by modifying
1139: the generated code.
1140: .PP
1141: There are no absolute restrictions on the graphs that \*(DG can draw.
1142: Self-edges and multi-edges are allowed.
1143: For picture clarity, it's best to avoid nodes with many incident edges.
1144: For instance, in procedure call graphs, it is a good idea to eliminate common
1145: library calls (for example, \fIstdio\fP) before making the drawing.
1146: Removing these less interesting nodes both yields a more informative drawing and
1147: reduces run time.
1148: .NH 1
1149: Drawing Algorithms
1150: .PP
1151: .I Dag
1152: has three main components: the parser, \fIdraw_dag\fP,
1153: and the code generator. The parser is written in
1154: \s-2YACC\s+2|reference(latest yacc).
1155: It constructs a graph of attributed nodes and edges in memory.
1156: The graph is passed to the drawing procedure \fIdraw_dag\fP,
1157: which sets $(x,y)$ coordinates of nodes
1158: and spline control points of edges.
1159: The code generator traverses the attributed graph to emit target code
1160: in an obvious fashion. \fIDraw_dag\fP is thus the heart of \*(DG.
1161: .PP
1162: To design algorithms for drawing graphs,
1163: we need to define what makes a good drawing.
1164: We have chosen three desirable properties for drawings of directed graphs:
1165: .PP
1166: .B P1.
1167: The drawing should reveal the partial order implied by edges of the graph.
1168: Nodes are placed in ranks so that edges points downward.
1169: If the graph is not acyclic, cycles are broken by reversing edges.
1170: .PP
1171: .B P2.
1172: The drawing should not be cluttered with irrelevance.
1173: For example, edge crossings are undesirable because they suggest
1174: a connection that is not really present in the underlying abstract graph.
1175: Edges also should not intersect nodes that are not their endpoints.
1176: .PP
1177: .B P3.
1178: The drawing should reveal the relationships implied by edges by placing
1179: adjacent nodes in the graph close together.
1180: .PP
1181: Unfortunately, these goals conflict.
1182: For instance,
1183: the placement of nodes in ranks may make it impossible to avoid edge crossings.
1184: Also, the minimization of edge-crossings in a layout
1185: is computationally intractable.
1186: So we are satisfied to find heuristics that run quickly
1187: and make good layouts in common cases.
1188: We sketch these techniques briefly as an aid to understanding the
1189: behavior of \*(DG.
1190: .PP
1191: .I Draw_dag
1192: has four passes. The first pass finds an optimal rank assignment for the
1193: nodes, satisfying P1 and P3. The optimal rank assignment problem
1194: is to assign integer ranks to nodes such that the sum of the weighted edge
1195: lengths is minimized. The length of an edge here is taken as
1196: the difference in the ranks of its head and tail nodes.
1197: The optimal rank assignment problem can be formulated as an integer program.
1198: Because of its special characteristics the simplex method
1199: for linear programming can be used to solve these integer programs.
1200: However we have developed a
1201: combinatorial algorithm that finds the solution
1202: in a factor of $O(|E|)$ less time than the standard simplex algorithm
1203: and uses only $O(|E|)$ space.
1204: Following rank assignment, \fIdraw_dag\fP
1205: creates dummy nodes where long edges cross ranks. The placement of dummy
1206: nodes determines edge crossings and is also
1207: an aid to drawing splines for long edges. Consequently,
1208: optimal rank assignment is important not only for drawing quality,
1209: but also to minimize the number of dummy nodes.
1210: This reduces edge crossing and improves the running time
1211: of subsequent passes that have a factor of
1212: $O(|V|)$ in their running time.
1213: .PP
1214: The second pass orders nodes from left to right within ranks.
1215: This pass tries to reduce edge crossings (P2) subject to the
1216: constraints on node order implied by flat edges (P1).
1217: It is based on an iterative technique like that of
1218: |reference(sugiyama)|reference(rowe browser).
1219: The key improvements are a new weight function and local optimizations.
1220: We call the weight function the ``generalized median'';
1221: it produces less crossings by reducing the effects of widely spread nodes,
1222: and is inexpensive to compute.
1223: Informally, the generalized median
1224: of a node with respect to an adjacent rank is defined as follows.
1225: When the number of neighbors of a node in the concerned adjacent rank
1226: is odd, the generalized median is simply the median position of its
1227: neighbors. When the number of neighbors is even, the generalized median
1228: is in between the left and the right median positions.
1229: The exact value is tilted toward the side where neighbor nodes are
1230: more tightly packed.
1231: .PP
1232: The generalized median heuristic (and other similar heuristics)
1233: tends to work better if the initial order of nodes is good.
1234: To enhance this condition,
1235: we apply transpositions of
1236: adjacent nodes to precondition the inputs to the generalized median method and to
1237: further optimize its solutions.
1238: The transposition heuristic
1239: can be viewed as a descent method to find local optima.
1240: .PP
1241: The third pass assigns absolute coordinates to nodes,
1242: respecting the ordering determined by the previous pass (P3).
1243: The optimal assignment can be formulated as a set of linear
1244: constraints and an objective function involving absolute values.
1245: This can be transformed into a linear program by a standard technique
1246: that involves introducing extra variables. \f5dag -O\fP works this way.
1247: Since this pass is the bottleneck in \fIdraw_dag\fP,
1248: we have developed a fast heuristic
1249: based on computation of the generalized median positions of adjacent nodes
1250: with additional local optimizations.
1251: .PP
1252: The final pass finds the spline control points for edges.
1253: There are several cases to consider, including self-edges, edges between
1254: nodes on the same rank, adjacent ranks, or nonadjacent ranks, possibly
1255: in the presence of multi-edges.
1256: Short edges are easy to draw; we use a single B-spline
1257: |reference(mortenson) that is
1258: shaped according to the number of parallel multi-edges being drawn.
1259: Long edges, or edges that have endpoints on nonadjacent ranks,
1260: are more difficult since they may
1261: pass near other nodes and change direction.
1262: The B-spline control points are chosen for
1263: smoothness,
1264: avoiding node intersections, and
1265: avoiding edge crossings.
1266: .PP
1267: The dummy nodes are created with a
1268: height a little larger than the highest non-dummy node in the same rank,
1269: and width usually twice the default node separation. This is big enough
1270: to make a spline inside the boundaries of the dummy node, if necessary.
1271: On the other hand, if there is space next to the dummy node, it is
1272: often preferable to encroach on it to draw a smoother spline.
1273: .KF top
1274: .PS 6.5
1275: scale=250
1276: box ht 100 wid 75 at (0,0);
1277: line dashed from last box.c + 200,120 to last box.c to last box.c + -200,-190;
1278: line from last box.c + 200,120 to last box.c + -200,-190;
1279: "(a)" at last box.c +0,-250;
1280: box ht 100 wid 75 at (500,0);
1281: line from last box.c + 200,156.7 to last box.c to last box.c + -33.3,-200;
1282: "\(bu" at last box.c + 37.5,27;
1283: "\(bu" at last box.c+ -8.3333333,-51;
1284: "\(bu" at last box.c + 0,-2;
1285: "(b)" at last box.c +0,-250;
1286: box ht 100 wid 75 at (1000,0);
1287: line from last box.c + 200,60 to last box.c + -37.5,40;
1288: line dashed from last box.c + -200,-40 to last box.c+ 37.5,7.5;
1289: line from last box.c + -200,-40 to last box.c + 0,42.22222;
1290: "\(bu" at last box.c + 0,40;
1291: "\(bu" at last box.c + -37.5,26;
1292: "\(bu" at last box.c + 37.5,42;
1293: "(c)" at last box.c +0,-250;
1294: .PE
1295: .PS 6.5
1296: scale=250
1297: box ht 100 wid 75 at 0,0;
1298: line from last box.c + 200,40 to last box.c + -37.5,-6.66666;
1299: line from last box.c + -200,-40 to last box.c + 37.5,-20;
1300: "\(bu" at last box.c + 0,-2;
1301: "\(bu" at last box.c + 37.5,7;
1302: "\(bu" at last box.c + -37.5,-30;
1303: "(d)" at last box +0,-250;
1304: box ht 100 wid 75 at 500,0;
1305: line from last box.c + 116.7,-200 to last box.c + 37.5,-40;
1306: line from last box.c + 200,-83.3 to last box.c + 0,-50;
1307: "(e)" at last box +0,-250;
1308: box ht 100 wid 75 at 1000,0;
1309: line from last box.c + 116,-200 to last box.c + 0,-50;
1310: line from last box.c + 200,-83.3 to last box.c + 0,-50;
1311: "(f)" at last box +0,-250;
1312: .PE
1313: .ce
1314: \fBFigure 11.\fR
1315: .SP
1316: .KE
1317: .PP
1318: The edge drawing procedure in \fIdraw_dag\fP visits each dummy node to
1319: choose its spline control points. If a straight line between the neighbors
1320: of the dummy node does not intersect any other node, nor change the order of
1321: edge crossings, then the dummy node is deleted (Figure 11a).
1322: This removes small bumps in the edges.
1323: Next, \fIdraw_dag\fP aims the incident edges as close to the center of the dummy node
1324: box as possible, without intersecting adjacent nodes.
1325: .I Draw_dag
1326: uses the points where the edges intersect the dummy node
1327: as spline control points. It also finds a third point to determine
1328: how the spline bends as it passes through the dummy node.
1329: If the intersection of the edges lies inside the dummy node (Figure 11b),
1330: \fIdraw_dag\fP chooses it as the third control point.
1331: Otherwise, \fIdraw_dag\fP tries to move the edges toward each other
1332: so they do intersect (Figure 11c) and
1333: again takes the intersection as the third control point.
1334: If the edges can't be made to intersect, but the angle between them is acute,
1335: \fIdraw_dag\fP can still make a smooth spline by choosing the midpoint of the opposite side.
1336: When the angle is obtuse, that is, the edges are close to being parallel,
1337: then it chooses the midpoint of the dummy node box.
1338: In the latter case the spline has two points of inflection
1339: as it passes through the dummy node, which is not as smooth as the
1340: other cases which have only one,
1341: but the extra turn is necessary when an edge
1342: makes a jog as it passes through a rank near other nodes (Figure 11d).
1343: .PP
1344: Moving an edge may create an edge intersection
1345: near an incident real (non-dummy) node (Figure 11e).
1346: Such intersections are eliminated by sorting the incident edges according
1347: to the
1348: .I x -coordinates
1349: of the other endpoints, and moving their nearby
1350: endpoints slightly (Figure 11f).
1351: .PP
1352: Tables 1-3 show the performance of \fIdraw_dag\fP using
1353: various node placement methods.
1354: The tables list the time (in seconds) spent in the three node placement
1355: passes: time spent on level (or rank) assignment ($t sub level$),
1356: time spent ordering nodes within ranks to reduce edge crossings ($t sub cross$),
1357: and time spent finding final coordinates ($t sub coord$).
1358: The total time $t sub total$ is the sum of these plus time spent in initialization
1359: and creating splines.
1360: The times were measured on a VAX-8650 under the 4.3BSD UNIX System and
1361: averaged over 5 runs to reduce statistical fluctuation.
1362: Times were measured on three graphs,
1363: the \fIWorld Dynamics\fP graph from the abstract of this paper and
1364: two procedure call graphs from C programs.
1365: \&\fIWorld Dynamics \fP has 48 nodes and 69 edges.
1366: The initial placement has 126 crossings.
1367: \&\fICallGraph-1\fP in Figure 12
1368: has 38 nodes, 58 edges, and the initial placement has 128 crossings.
1369: \&\fI CallGraph-2\fP in Figure 13 is \*(DG's call graph of
1370: 170 nodes and 258 edges. Its initial placement has 1170 crossings.
1371: .PP
1372: We tried three algorithms for ordering of nodes within ranks:
1373: (1) \&\fIgmedian\fP is \*(DG's generalized median algorithm,
1374: (2) \&\fIbcenter\fP is the barycenter method described in |reference(sugiyama),
1375: and (3) \fIrmedian\fP is the ``right median''
1376: |reference(eades), which orders nodes using
1377: the position of the median neighbor when the number of neighbors is odd,
1378: and the right median neighbor otherwise.
1379: We also tried all three methods in combination with transposition of
1380: adjacent nodes.
1381: To simplify the comparison of relative performance,
1382: the iterative loop for minimizing edge crossing is set to terminate
1383: after exactly 20 iterations.
1384: In practice, the loop termination is determined by an adaptive parameter
1385: that depends on the convergent rate of a solution.
1386: Thus, for example, the total time for the \fIWorld Dynamics\fP
1387: graph using \fIgmedian+\fP
1388: is slightly higher than it would be in an actual run.
1389: The experiments show that generalized median behaves well in a
1390: variety of test cases, and in about the same run-time as the other methods.
1391: All three methods improved by adding transposition, which seems well worth
1392: the extra computational expense. In Table 1, transposition
1393: reduced edge crossing by 30%.
1394: .KS
1395: .SP 1
1396: .TS
1397: center, allbox;
1398: c s c s s s
1399: c c c c c c
1400: l n n n n n.
1401: World Dynamics seconds
1402: Method $n sub cross$ $t sub level$ $t sub crossing$ $t sub coord$ $t sub total$
1403: gmedian 59 .06 .47 .56 1.18
1404: bcenter 59 .06 .44 .47 1.08
1405: rmedian 62 .05 .45 .51 1.11
1406: gmedian+ 41 .06 1.30 .49 1.96
1407: bcenter+ 43 .06 1.23 .50 1.88
1408: rmedian+ 47 .05 1.25 .49 1.88
1409: .TE
1410: .ce
1411: Table 1
1412: .KE
1413: .KS
1414: .PS 6.000000
1415: arrowht = 0.111111;
1416: arrowwid = 0.055556;
1417: define Box % [box wid $2 ht $3 $1] %
1418: define Square % [box wid $2 ht $2 $1] %
1419: define Circle % [circle rad $2/2; $1 at last circle.c] %
1420: define Ellipse % [ellipse wid $2 ht $3 $1] %
1421: define Diamond % [move down $3/2; line up $3/2 right $2/2 then up $3/2 left $2/2 then down $3/2 left $2/2 then down $3/2 right $2/2; move up $3/2; $1;] %
1422: define Doublecircle % [circle rad $2/2; circle rad .9*$2/2 at last circle.c; $1 at last circle.c] %
1423: define Plaintext % [box invis wid $2 ht $3 $1] %
1424: .ps 4
1425: Node0: Ellipse("progen",0.750000,0.500000) at (12.527778,10.250000);
1426: Node1: Ellipse("xmalloc",0.875000,0.500000) at (13.152778,2.250000);
1427: Node2: Ellipse("setbuf",0.750000,0.500000) at (11.902778,9.250000);
1428: Node3: Ellipse("initsymtbl",1.250000,0.500000) at (13.152778,9.250000);
1429: Node4: Ellipse("scanner",0.875000,0.500000) at (6.319444,9.250000);
1430: Node5: Ellipse("put_one",0.875000,0.500000) at (5.013889,8.250000);
1431: Node6: Ellipse("setblkval",1.125000,0.500000) at (9.930556,5.250000);
1432: Node7: Ellipse("Mapblk",0.750000,0.500000) at (11.222222,3.250000);
1433: Node8: Ellipse("bhash",0.750000,0.500000) at (12.097222,2.250000);
1434: Node9: Ellipse("token_fetch",1.375000,0.500000) at (8.875000,4.250000);
1435: Node10: Ellipse("unget_one",1.125000,0.500000) at (3.944444,1.250000);
1436: Node11: Ellipse("ungetc",0.750000,0.500000) at (3.944444,0.250000);
1437: Node12: Ellipse("look_ahead",1.250000,0.500000) at (3.208333,8.250000);
1438: Node13: Ellipse("comment_scan",1.500000,0.500000) at (3.208333,7.250000);
1439: Node14: Ellipse("tree_walker",1.375000,0.500000) at (6.930556,4.250000);
1440: Node15: Ellipse("dnfeval",0.875000,0.500000) at (7.416667,3.250000);
1441: Node16: Ellipse("tilde_token",1.375000,0.500000) at (5.388889,2.250000);
1442: Node17: Ellipse("q_token",0.875000,0.500000) at (9.680556,2.250000);
1443: Node18: Ellipse("get_ch",0.750000,0.500000) at (11.416667,1.250000);
1444: Node19: Ellipse("unget_ch",1.000000,0.500000) at (10.291667,1.250000);
1445: Node20: Ellipse("atol",0.750000,0.500000) at (7.013889,2.250000);
1446: Node21: Ellipse("next_or",0.875000,0.500000) at (8.069444,2.250000);
1447: Node22: Ellipse("ret_token",1.125000,0.500000) at (10.916667,2.250000);
1448: Node23: Ellipse("range_walker",1.500000,0.500000) at (8.444444,8.250000);
1449: Node24: Ellipse("expreval",1.000000,0.500000) at (8.625000,7.250000);
1450: Node25: Ellipse("next_val",1.000000,0.500000) at (10.083333,6.250000);
1451: Node26: Ellipse("mcprse",0.750000,0.500000) at (11.388889,5.250000);
1452: Node27: Ellipse("refblkval",1.125000,0.500000) at (11.041667,4.250000);
1453: Node28: Ellipse("setsymval",1.125000,0.500000) at (15.013889,4.250000);
1454: Node29: Ellipse("Mapsym",0.750000,0.500000) at (16.375000,3.250000);
1455: Node30: Ellipse("hash",0.750000,0.500000) at (16.375000,2.250000);
1456: Node31: Ellipse("randstr",0.875000,0.500000) at (17.847222,2.250000);
1457: Node32: Ellipse("incrsymval",1.250000,0.500000) at (17.805556,4.250000);
1458: Node33: Ellipse("refsymval",1.125000,0.500000) at (16.375000,4.250000);
1459: Node34: Ellipse("echo_of",0.875000,0.500000) at (12.777778,4.250000);
1460: Node35: Ellipse("mclex",0.750000,0.500000) at (13.833333,4.250000);
1461: Node36: Ellipse("next_op",0.875000,0.500000) at (8.625000,6.250000);
1462: Node37: Ellipse("quote_token",1.375000,0.500000) at (0.694444,7.250000);
1463: .ps
1464: .ps 14
1465: spline -> from (12.152778,10.208333) to (6.736111,9.319444);
1466: spline -> from (12.722222,10.027778) to (13.013889,9.500000);
1467: spline -> from (12.333333,10.027778) to (12.027778,9.486111);
1468: spline -> from (12.902778,10.208333) to (17.263889,9.500000) to (18.041667,9.250000) to (18.805556,9.000000) to (18.805556,3.500000) to (18.777778,3.291667) to (18.736111,3.083333) to (16.750000,2.875000) to (13.569444,2.319444);
1469: spline -> from (5.888889,9.194444) to (0.777778,8.500000) to (0.750000,8.250000) to (0.708333,8.000000) to (0.694444,7.500000);
1470: spline -> from (6.736111,9.180556) to (10.958333,8.277778) to (11.055556,8.138889) to (11.138889,8.000000) to (11.222222,6.500000) to (11.236111,6.250000) to (11.250000,6.000000) to (11.375000,5.500000);
1471: spline -> from (5.944444,9.125000) to (4.236111,8.500000) to (4.111111,8.416667) to (4.277778,8.166667) to (4.763889,7.361111) to (4.819444,7.180556) to (4.861111,7.000000) to (5.361111,2.500000);
1472: spline -> from (5.902778,9.166667) to (2.444444,8.597222) to (2.000000,8.388889) to (2.291667,8.055556) to (2.944444,7.486111);
1473: spline -> from (6.694444,9.125000) to (7.250000,8.791667) to (8.027778,8.458333);
1474: spline -> from (6.319444,9.000000) to (6.416667,6.500000) to (6.472222,6.250000) to (6.513889,6.000000) to (6.652778,5.500000) to (6.736111,5.250000) to (6.819444,5.000000) to (6.861111,4.500000);
1475: spline -> from (5.916667,9.166667) to (3.611111,8.444444);
1476: spline -> from (5.902778,9.180556) to (2.222222,8.625000) to (2.013889,8.597222) to (1.875000,8.291667) to (1.722222,8.000000) to (1.750000,6.500000) to (1.750000,6.250000) to (1.750000,6.000000) to (1.750000,2.500000) to (1.791667,2.361111) to (1.819444,2.222222) to (3.555556,1.430556);
1477: spline -> from (6.472222,9.013889) to (6.750000,8.402778) to (6.791667,8.194444) to (6.819444,8.000000) to (6.819444,6.500000) to (6.861111,6.347222) to (6.888889,6.194444) to (8.638889,4.486111);
1478: spline -> from (6.597222,9.055556) to (7.152778,8.430556) to (7.263889,8.208333) to (7.375000,8.000000) to (7.694444,6.500000) to (7.861111,6.208333) to (8.013889,5.916667) to (8.194444,5.875000) to (9.486111,5.402778);
1479: spline -> from (5.986111,9.083333) to (5.250000,8.458333);
1480: spline -> from (9.958333,5.000000) to (10.000000,4.500000) to (10.041667,4.291667) to (10.083333,4.083333) to (10.486111,3.875000) to (10.986111,3.444444);
1481: spline -> from (11.555556,3.125000) to (13.152778,2.500000);
1482: spline -> from (11.472222,3.055556) to (11.930556,2.472222);
1483: spline -> from (8.875000,4.000000) to (8.875000,2.500000) to (8.763889,2.194444) to (8.652778,1.888889) to (8.500000,1.875000) to (4.486111,1.319444);
1484: spline -> from (3.944444,1.000000) to (3.944444,0.500000);
1485: spline -> from (3.541667,8.041667) to (4.263889,7.319444) to (4.305556,7.152778) to (4.333333,7.000000) to (4.333333,3.500000) to (4.305556,3.250000) to (4.277778,3.000000) to (4.208333,2.500000) to (4.152778,2.250000) to (4.097222,2.000000) to (4.000000,1.500000);
1486: spline -> from (3.208333,8.000000) to (3.208333,7.500000);
1487: spline -> from (3.236111,7.000000) to (3.513889,2.500000) to (3.555556,2.305556) to (3.597222,2.125000) to (3.847222,1.500000);
1488: spline -> from (6.861111,4.500000) to (6.625000,5.000000) to (6.541667,5.250000) to (6.458333,5.500000) to (6.319444,6.000000) to (6.277778,6.250000) to (6.222222,6.500000) to (6.319444,9.000000);
1489: spline -> from (7.097222,4.013889) to (7.305556,3.486111);
1490: spline -> from (7.847222,3.305556) to (7.972222,3.361111) to (8.097222,3.250000) to (7.972222,3.138889) to (7.847222,3.194444);
1491: spline -> from (7.777778,3.111111) to (10.763889,2.486111);
1492: spline -> from (7.097222,3.430556) to (6.250000,3.875000) to (5.861111,4.000000) to (5.847222,4.250000) to (5.819444,4.500000) to (5.819444,8.000000) to (5.861111,8.194444) to (5.888889,8.402778) to (6.166667,9.013889);
1493: spline -> from (7.569444,3.013889) to (7.916667,2.486111);
1494: spline -> from (7.277778,3.013889) to (7.097222,2.500000);
1495: spline -> from (7.763889,3.097222) to (9.333333,2.402778);
1496: spline -> from (7.041667,3.125000) to (5.777778,2.458333);
1497: spline -> from (7.805556,3.125000) to (12.597222,2.611111) to (13.152778,2.500000);
1498: spline -> from (4.972222,2.055556) to (4.222222,1.472222);
1499: spline -> from (9.805556,2.013889) to (10.138889,1.486111);
1500: spline -> from (9.930556,2.041667) to (11.180556,1.444444);
1501: spline -> from (10.722222,2.013889) to (10.430556,1.486111);
1502: spline -> from (11.083333,2.013889) to (11.333333,1.500000);
1503: spline -> from (8.027778,8.458333) to (7.444444,8.791667) to (6.694444,9.125000);
1504: spline -> from (8.500000,8.000000) to (8.583333,7.500000);
1505: spline -> from (8.625000,7.000000) to (8.625000,6.500000);
1506: spline -> from (9.000000,7.083333) to (9.819444,6.458333);
1507: spline -> from (10.430556,6.069444) to (11.152778,5.444444);
1508: spline -> from (11.680556,5.097222) to (13.680556,4.472222);
1509: spline -> from (11.375000,5.500000) to (11.444444,6.000000) to (11.430556,6.250000) to (11.416667,6.500000) to (11.333333,8.000000) to (11.250000,8.138889) to (11.152778,8.277778) to (6.736111,9.180556);
1510: spline -> from (11.638889,5.069444) to (12.500000,4.444444);
1511: spline -> from (11.708333,5.125000) to (15.694444,4.611111) to (16.375000,4.500000);
1512: spline -> from (11.722222,5.125000) to (17.055556,4.611111) to (17.805556,4.500000);
1513: spline -> from (11.694444,5.111111) to (14.888889,4.500000);
1514: spline -> from (11.388889,5.000000) to (10.750000,4.902778) to (7.027778,4.500000);
1515: spline -> from (11.388889,5.000000) to (9.402778,4.416667);
1516: spline -> from (11.388889,5.000000) to (11.152778,4.500000);
1517: spline -> from (11.750000,5.305556) to (11.888889,5.361111) to (12.013889,5.250000) to (11.888889,5.138889) to (11.750000,5.194444);
1518: spline -> from (11.527778,5.013889) to (13.152778,2.500000);
1519: spline -> from (11.097222,4.000000) to (11.180556,3.500000);
1520: spline -> from (15.388889,4.069444) to (16.138889,3.444444);
1521: spline -> from (16.680556,3.111111) to (17.569444,2.444444);
1522: spline -> from (16.013889,3.166667) to (13.527778,2.375000);
1523: spline -> from (16.375000,3.000000) to (16.375000,2.500000);
1524: spline -> from (18.222222,4.069444) to (19.138889,3.375000) to (19.402778,3.138889) to (19.125000,3.000000) to (18.152778,2.430556);
1525: spline -> from (17.402778,4.055556) to (16.625000,3.444444);
1526: spline -> from (16.375000,4.000000) to (16.375000,3.500000);
1527: spline -> from (0.694444,7.000000) to (0.694444,2.500000) to (0.736111,2.263889) to (0.763889,2.041667) to (3.458333,1.375000);
1528: .ps
1529: .PE
1530: .sp -2
1531: .ce
1532: \fBFigure 12.\fR CallGraph-1.
1533: .SP 2
1534: .KE
1535: .KS
1536: .TS
1537: center, allbox;
1538: c s c s s s
1539: c c c c c c
1540: l n n n n n.
1541: CallGraph-1 seconds
1542: Method $ n sub cross$ $t sub level$ $t sub crossing$ $t sub coord$ $t sub total$
1543: gmedian 12 .04 .38 .57 1.08
1544: bcenter 10 .04 .44 .90 1.48
1545: rmedian 14 .04 .43 .70 1.26
1546: gmedian+ 11 .03 .73 .85 1.73
1547: bcenter+ 11 .04 .77 .64 1.56
1548: rmedian+ 11 .05 .89 .64 1.67
1549: .TE
1550: .ce
1551: Table 2
1552: .KE
1553: .KS
1554: .TS
1555: center, allbox;
1556: c s c s s s
1557: c c c c c c
1558: l n n n n n.
1559: CallGraph-2 seconds
1560: Method $ n sub cross$ $t sub level$ $t sub crossing$ $t sub coord$ $t sub total$
1561: gmedian 193 .50 2.87 2.91 6.52
1562: bcenter 249 .53 2.73 2.82 6.36
1563: rmedian 227 .53 2.96 3.07 6.84
1564: gmedian+ 154 .51 8.11 3.32 12.23
1565: bcenter+ 145 .52 8.21 3.05 12.04
1566: rmedian+ 200 .50 8.35 3.75 12.86
1567: .TE
1568: .ce
1569: Table 3
1570: .KE
1571: .KS
1572: .PS 6.000000 3.000000
1573: arrowht = 0.111111;
1574: arrowwid = 0.055556;
1575: define Box % [box wid $2 ht $3] %
1576: Node0: Box("start",0.750000,0.500000) at (16.500000,43.208333);
1577: Node1: Box("main",0.750000,0.500000) at (16.500000,39.305556);
1578: Node2: Box("yyparse",0.875000,0.500000) at (41.500000,35.402778);
1579: Node3: Box("nextfile",1.000000,0.500000) at (32.055556,35.402778);
1580: Node4: Box("fclose",0.750000,0.500000) at (12.611111,35.402778);
1581: Node5: Box("global_init",1.375000,0.500000) at (30.375000,35.402778);
1582: Node6: Box("gets",0.750000,0.500000) at (13.208333,27.597222);
1583: Node7: Box("set_output_type",1.888889,0.500000) at (14.180556,35.402778);
1584: Node8: Box("graph_init",1.250000,0.500000) at (16.000000,35.402778);
1585: Node9: Box("sscanf",0.750000,0.500000) at (2.583333,35.402778);
1586: Node10: Box("strcmp",0.750000,0.500000) at (14.291667,19.777778);
1587: Node11: Box("reclaim_storage",1.888889,0.500000) at (6.347222,35.402778);
1588: Node12: Box("make_drawing",1.500000,0.500000) at (47.916667,31.500000);
1589: Node13: Box("yylex",0.750000,0.500000) at (41.875000,31.500000);
1590: Node14: Box("node_lookup",1.375000,0.500000) at (43.180556,31.500000);
1591: Node15: Box("ct_edge_t",1.125000,0.500000) at (54.416667,27.597222);
1592: Node16: Box("apply_proto_node_t",2.263889,0.500000) at (39.625000,31.500000);
1593: Node17: Box("setpointsize_node_tFi",2.638889,0.500000) at (28.194444,27.597222);
1594: Node18: Box("setshape_node_t",1.888889,0.500000) at (25.180556,27.597222);
1595: Node19: Box("enter_edgelist_edge_t",2.638889,0.500000) at (33.750000,31.500000);
1596: Node20: Box("atof",0.750000,0.500000) at (9.611111,23.694444);
1597: Node21: Box("init_proto",1.250000,0.500000) at (46.236111,31.500000);
1598: Node22: Box("atoi",0.750000,0.500000) at (44.986111,31.500000);
1599: Node23: Box("draw_dag",1.000000,0.500000) at (55.722222,27.597222);
1600: Node24: Box("emit_ps",0.875000,0.500000) at (38.583333,27.597222);
1601: Node25: Box("translate",1.125000,0.500000) at (49.791667,27.597222);
1602: Node26: Box("find_drawing_size",2.138889,0.500000) at (47.916667,27.597222);
1603: Node27: Box("dag_ranks",1.125000,0.500000) at (64.111111,23.694444);
1604: Node28: Box("dag_positions",1.625000,0.500000) at (59.958333,23.694444);
1605: Node29: Box("dag_levels",1.250000,0.500000) at (57.750000,23.694444);
1606: Node30: Box("dag_spline",1.250000,0.500000) at (49.638889,23.694444);
1607: Node31: Box("dag_start",1.125000,0.500000) at (53.597222,23.694444);
1608: Node32: Box("dag_unitedges",1.625000,0.500000) at (45.444444,23.694444);
1609: Node33: Box("dag_delstem",1.375000,0.500000) at (43.694444,23.694444);
1610: Node34: Box("dag_insstem",1.375000,0.500000) at (56.194444,23.694444);
1611: Node35: Box("dag_end",0.875000,0.500000) at (54.833333,23.694444);
1612: Node36: Box("buildrank",1.125000,0.500000) at (82.055556,19.777778);
1613: Node37: Box("nw",0.750000,0.500000) at (51.236111,11.972222);
1614: Node38: Box("decompose",1.125000,0.500000) at (63.180556,19.777778);
1615: Node39: Box("inversion",1.125000,0.500000) at (86.347222,11.972222);
1616: Node40: Box("mincross",1.000000,0.500000) at (83.000000,15.875000);
1617: Node41: Box("transpose",1.125000,0.500000) at (84.986111,11.972222);
1618: Node42: Box("cross_stat",1.250000,0.500000) at (82.305556,11.972222);
1619: Node43: Box("fixstem",0.875000,0.500000) at (80.513889,15.875000);
1620: Node44: Box("initrank",1.000000,0.500000) at (60.972222,15.875000);
1621: Node45: Box("median",0.750000,0.500000) at (81.055556,11.972222);
1622: Node46: Box("copyrank",1.000000,0.500000) at (83.680556,11.972222);
1623: Node47: Box("goodposition",1.500000,0.500000) at (70.902778,19.777778);
1624: Node48: Box("smoothedges",1.375000,0.500000) at (61.694444,19.777778);
1625: Node49: Box("levelposition",1.625000,0.500000) at (59.944444,19.777778);
1626: Node50: Box("minnode",0.875000,0.500000) at (69.791667,15.875000);
1627: Node51: Box("mincut",0.750000,0.500000) at (67.986111,11.972222);
1628: Node52: Box("minpath",0.875000,0.500000) at (76.763889,15.875000);
1629: Node53: Box("medianpos",1.125000,0.500000) at (78.027778,15.875000);
1630: Node54: Box("define_median_t",1.888889,0.500000) at (72.527778,15.875000);
1631: Node55: Box("rlength",0.875000,0.500000) at (70.902778,15.875000);
1632: Node56: Box("minedge",0.875000,0.500000) at (74.152778,15.875000);
1633: Node57: Box("verticalcut",1.375000,0.500000) at (71.041667,11.972222);
1634: Node58: Box("startpos",1.000000,0.500000) at (79.333333,15.875000);
1635: Node59: Box("edgefactor",1.250000,0.500000) at (75.458333,15.875000);
1636: Node60: Box("define_order",1.500000,0.500000) at (69.361111,11.972222);
1637: Node61: Box("mediansort",1.250000,0.500000) at (81.055556,8.069444);
1638: Node62: Box("qsort",0.750000,0.500000) at (73.805556,8.069444);
1639: Node63: Box("rcross",0.750000,0.500000) at (82.305556,8.069444);
1640: Node64: Box("vcross",0.750000,0.500000) at (84.986111,8.069444);
1641: Node65: Box("wmedian",0.875000,0.500000) at (73.763889,11.972222);
1642: Node66: Box("vlength",0.875000,0.500000) at (72.416667,11.972222);
1643: Node67: Box("qst",0.750000,0.500000) at (74.597222,4.166667);
1644: Node68: Box("mediancmp",1.125000,0.500000) at (74.652778,0.250000);
1645: Node69: Box("rightcmp",1.000000,0.500000) at (73.347222,0.250000);
1646: Node70: Box("adjcmp",0.750000,0.500000) at (72.222222,0.250000);
1647: Node71: Box("prioritycmp",1.375000,0.500000) at (78.250000,0.250000);
1648: Node72: Box("leftcmp",0.875000,0.500000) at (76.888889,0.250000);
1649: Node73: Box("intcmp",0.750000,0.500000) at (75.833333,0.250000);
1650: Node74: Box("emit_ps_edge",1.500000,0.500000) at (41.013889,23.694444);
1651: Node75: Box("emit_ps_node",1.500000,0.500000) at (38.250000,23.694444);
1652: Node76: Box("emit_ps_header",1.763889,0.500000) at (33.736111,23.694444);
1653: Node77: Box("emit_ps_edge_header",2.388889,0.500000) at (31.416667,23.694444);
1654: Node78: Box("emit_ps_node_header",2.388889,0.500000) at (28.777778,23.694444);
1655: Node79: Box("emit_ps_trailer",1.888889,0.500000) at (36.305556,23.694444);
1656: Node80: Box("emit_ps_nodeport",2.013889,0.500000) at (33.625000,19.777778);
1657: Node81: Box("printf",0.750000,0.500000) at (29.472222,15.875000);
1658: Node82: Box("find_seg_midpoint",2.138889,0.500000) at (40.694444,19.777778);
1659: Node83: Box("emit_ps_edgelabel_edge_t",3.013889,0.500000) at (37.875000,19.777778);
1660: Node84: Box("doprnt",0.750000,0.500000) at (22.388889,11.972222);
1661: Node85: Box("flsbuf",0.750000,0.500000) at (22.277778,8.069444);
1662: Node86: Box("setlevels",1.125000,0.500000) at (56.833333,19.777778);
1663: Node87: Box("balance",0.875000,0.500000) at (53.680556,15.875000);
1664: Node88: Box("networksimplex",1.763889,0.500000) at (62.597222,15.875000);
1665: Node89: Box("addedge",0.875000,0.500000) at (52.055556,15.875000);
1666: Node90: Box("pathdegree",1.250000,0.500000) at (75.569444,11.972222);
1667: Node91: Box("getminmax",1.125000,0.500000) at (77.000000,11.972222);
1668: Node92: Box("treevalue",1.125000,0.500000) at (65.805556,11.972222);
1669: Node93: Box("treeupdate",1.250000,0.500000) at (63.625000,11.972222);
1670: Node94: Box("cutset",0.750000,0.500000) at (66.152778,8.069444);
1671: Node95: Box("delete_edge",1.375000,0.500000) at (63.569444,8.069444);
1672: Node96: Box("insert_edge",1.375000,0.500000) at (61.819444,8.069444);
1673: Node97: Box("initlevel",1.125000,0.500000) at (60.444444,11.972222);
1674: Node98: Box("spantree",1.000000,0.500000) at (62.250000,11.972222);
1675: Node99: Box("assignpos",1.125000,0.500000) at (78.361111,11.972222);
1676: Node100: Box("widthof",0.875000,0.500000) at (77.000000,8.069444);
1677: Node101: Box("delimitname",1.375000,0.500000) at (33.847222,27.597222);
1678: Node102: Box("newstring",1.125000,0.500000) at (32.333333,27.597222);
1679: Node103: Box("eatwhitespace",1.625000,0.500000) at (26.027778,23.694444);
1680: Node104: Box("escape",0.750000,0.500000) at (31.986111,19.777778);
1681: Node105: Box("downspline",1.250000,0.500000) at (45.888889,19.777778);
1682: Node106: Box("upspline",1.000000,0.500000) at (44.513889,19.777778);
1683: Node107: Box("selfedge_t",1.250000,0.500000) at (50.388889,19.777778);
1684: Node108: Box("setmargins",1.250000,0.500000) at (48.888889,19.777778);
1685: Node109: Box("assignside",1.250000,0.500000) at (47.388889,19.777778);
1686: Node110: Box("setname_node_t",1.763889,0.500000) at (30.638889,27.597222);
1687: Node111: Box("ct_node_t",1.125000,0.500000) at (37.333333,27.597222);
1688: Node112: Box("hash",0.750000,0.500000) at (35.652778,27.597222);
1689: Node113: Box("ct",0.750000,0.500000) at (22.000000,27.597222);
1690: Node114: Box("fopen",0.750000,0.500000) at (13.611111,23.694444);
1691: Node115: Box("strlen",0.750000,0.500000) at (15.291667,19.777778);
1692: Node116: Box("strcpy",0.750000,0.500000) at (24.097222,23.694444);
1693: Node117: Box("setbounds",1.125000,0.500000) at (57.666667,15.875000);
1694: Node118: Box("straight",1.000000,0.500000) at (56.361111,15.875000);
1695: Node119: Box("addpoint",1.000000,0.500000) at (45.361111,15.875000);
1696: Node120: Box("bzero",0.750000,0.500000) at (51.236111,8.069444);
1697: Node121: Box("open",0.750000,0.500000) at (13.291667,19.777778);
1698: Node122: Box("findiop",0.875000,0.500000) at (12.236111,19.777778);
1699: Node123: Box("write",0.750000,0.500000) at (20.819444,4.166667);
1700: Node124: Box("fstat",0.750000,0.500000) at (16.486111,4.166667);
1701: Node125: Box("isatty",0.750000,0.500000) at (22.277778,4.166667);
1702: Node126: Box("lineXbox",1.000000,0.500000) at (44.111111,15.875000);
1703: Node127: Box("defineline",1.250000,0.500000) at (42.736111,15.875000);
1704: Node128: Box("lineXselfedge",1.625000,0.500000) at (41.055556,15.875000);
1705: Node129: Box("flatedge_t",1.250000,0.500000) at (51.888889,19.777778);
1706: Node130: Box("copypoints",1.250000,0.500000) at (46.736111,15.875000);
1707: Node131: Box("dfs",0.750000,0.500000) at (53.638889,19.777778);
1708: Node132: Box("findroot",1.000000,0.500000) at (55.013889,19.777778);
1709: Node133: Box("autosize_node_t",1.888889,0.500000) at (22.527778,23.694444);
1710: Node134: Box("is_fixed_aspect_ratio_t",2.888889,0.500000) at (17.361111,19.777778);
1711: Node135: Box("sethw_node_t",1.500000,0.500000) at (19.805556,19.777778);
1712: Node136: Box("cat_libfile",1.375000,0.500000) at (21.500000,19.777778);
1713: Node137: Box("unsquirrel",1.250000,0.500000) at (28.472222,19.777778);
1714: Node138: Box("noedge_t",1.000000,0.500000) at (48.611111,15.875000);
1715: Node139: Box("multiple",1.000000,0.500000) at (49.861111,15.875000);
1716: Node140: Box("fflush",0.750000,0.500000) at (19.361111,15.875000);
1717: Node141: Box("sprintf",0.875000,0.500000) at (22.027778,15.875000);
1718: Node142: Box("system",0.750000,0.500000) at (20.611111,15.875000);
1719: Node143: Box("close",0.750000,0.500000) at (12.847222,31.500000);
1720: Node144: Box("scross",0.750000,0.500000) at (80.055556,11.972222);
1721: Node145: Box("ct_t",0.750000,0.500000) at (20.958333,23.694444);
1722: Node146: Box("emit_ps_setink",1.763889,0.500000) at (26.222222,19.777778);
1723: Node147: Box("sti",0.750000,0.500000) at (55.166667,31.500000);
1724: Node148: Box("reset_options",1.625000,0.500000) at (30.375000,31.500000);
1725: Node149: Box("fgets",0.750000,0.500000) at (11.333333,23.694444);
1726: Node150: Box("filbuf",0.750000,0.500000) at (10.680556,19.777778);
1727: Node151: Box("append_edge",1.375000,0.500000) at (23.305556,27.597222);
1728: Node152: Box("bfs",0.750000,0.500000) at (60.444444,8.069444);
1729: Node153: Box("read",0.750000,0.500000) at (11.444444,15.875000);
1730: Node154: Box("signal",0.750000,0.500000) at (21.111111,11.972222);
1731: Node155: Box("sigvec",0.750000,0.500000) at (21.111111,8.069444);
1732: Node156: Box("innum",0.750000,0.500000) at (6.555556,27.597222);
1733: Node157: Box("ungetc",0.750000,0.500000) at (5.097222,23.694444);
1734: Node158: Box("instr",0.750000,0.500000) at (7.597222,23.694444);
1735: Node159: Box("doscan",0.750000,0.500000) at (0.375000,31.500000);
1736: Node160: Box("execl",0.750000,0.500000) at (18.611111,11.972222);
1737: Node161: Box("execv",0.750000,0.500000) at (18.611111,8.069444);
1738: Node162: Box("execve",0.750000,0.500000) at (18.611111,4.166667);
1739: Node163: Box("ioctl",0.750000,0.500000) at (22.277778,0.250000);
1740: Node164: Box("reclaim_nodes",1.625000,0.500000) at (3.416667,31.500000);
1741: Node165: Box("reclaim_edges",1.625000,0.500000) at (5.277778,31.500000);
1742: Node166: Box("reclaim_hashtable",2.138889,0.500000) at (7.402778,31.500000);
1743: Node167: Box("reclaim_samenodesets",2.513889,0.500000) at (9.972222,31.500000);
1744: Node168: Box("freestrings",1.375000,0.500000) at (1.680556,31.500000);
1745: Node169: Box("wait",0.750000,0.500000) at (20.111111,11.972222);
1746: spline -> from (16.500000,42.958333) to (16.500000,39.555556);
1747: spline -> from (16.875000,39.263889) to (46.569444,35.652778) to (47.694444,35.472222) to (48.805556,35.305556) to (54.791667,31.722222);
1748: spline -> from (16.875000,39.263889) to (46.763889,35.652778) to (47.888889,35.472222) to (49.000000,35.305556) to (54.791667,31.722222);
1749: spline -> from (16.875000,39.250000) to (41.069444,35.472222);
1750: spline -> from (16.875000,39.222222) to (31.569444,35.652778);
1751: spline -> from (16.236111,39.055556) to (12.861111,35.652778);
1752: spline -> from (16.875000,39.208333) to (29.694444,35.597222);
1753: spline -> from (16.166667,39.055556) to (11.680556,35.458333) to (11.652778,35.305556) to (11.611111,35.152778) to (11.597222,31.750000) to (11.638889,31.541667) to (11.666667,31.347222) to (13.111111,27.847222);
1754: spline -> from (16.347222,39.055556) to (14.333333,35.652778);
1755: spline -> from (16.472222,39.055556) to (16.027778,35.652778);
1756: spline -> from (16.125000,39.208333) to (2.958333,35.513889);
1757: spline -> from (16.527778,39.055556) to (16.972222,35.652778) to (16.986111,35.402778) to (17.000000,35.152778) to (17.000000,23.944444) to (16.972222,23.763889) to (16.930556,23.597222) to (14.458333,20.027778);
1758: spline -> from (16.125000,39.166667) to (7.000000,35.652778);
1759: spline -> from (41.944444,35.152778) to (47.513889,31.750000);
1760: spline -> from (41.527778,35.152778) to (41.847222,31.750000);
1761: spline -> from (41.611111,35.152778) to (43.069444,31.750000);
1762: spline -> from (41.930556,35.250000) to (51.652778,31.527778) to (51.722222,31.458333) to (51.791667,31.402778) to (54.250000,27.847222);
1763: spline -> from (41.375000,35.152778) to (39.750000,31.750000);
1764: spline -> from (41.472222,35.152778) to (41.152778,31.750000) to (41.027778,31.458333) to (40.902778,31.166667) to (40.750000,31.125000) to (29.083333,27.847222);
1765: spline -> from (41.180556,35.152778) to (37.083333,31.750000) to (36.902778,31.611111) to (36.708333,31.472222) to (25.847222,27.847222);
1766: spline -> from (41.069444,35.194444) to (34.250000,31.750000);
1767: spline -> from (41.069444,35.250000) to (31.708333,31.597222) to (31.527778,31.375000) to (31.333333,31.152778) to (12.680556,27.944444) to (12.541667,27.875000) to (12.388889,27.819444) to (9.777778,23.944444);
1768: spline -> from (41.819444,35.152778) to (45.930556,31.750000);
1769: spline -> from (41.736111,35.152778) to (44.763889,31.750000);
1770: spline -> from (32.055556,35.152778) to (32.055556,31.750000) to (32.027778,31.513889) to (31.986111,31.277778) to (22.277778,27.847222);
1771: spline -> from (12.569444,35.152778) to (12.125000,31.750000) to (12.152778,31.555556) to (12.166667,31.361111) to (13.902778,27.736111) to (13.902778,27.541667) to (13.888889,27.347222) to (11.513889,20.027778) to (11.513889,19.777778) to (11.513889,19.527778) to (11.805556,19.402778) to (18.986111,16.055556);
1772: spline -> from (12.625000,35.152778) to (12.833333,31.750000);
1773: spline -> from (31.069444,35.152778) to (44.013889,31.833333) to (44.375000,31.694444) to (44.166667,31.430556) to (40.583333,27.666667) to (40.513889,27.500000) to (40.430556,27.347222) to (39.458333,23.944444) to (39.388889,23.763889) to (39.319444,23.583333) to (39.000000,23.319444) to (35.069444,19.833333) to (35.041667,19.680556) to (35.000000,19.527778) to (35.000000,16.125000) to (35.041667,15.986111) to (35.069444,15.861111) to (50.861111,12.055556);
1774: spline -> from (30.375000,35.152778) to (30.375000,31.750000);
1775: spline -> from (13.083333,27.347222) to (11.458333,23.944444);
1776: spline -> from (14.194444,35.152778) to (14.458333,27.847222) to (14.472222,27.597222) to (14.472222,27.347222) to (14.472222,23.944444) to (14.472222,23.694444) to (14.458333,23.444444) to (14.305556,20.027778);
1777: spline -> from (2.430556,35.152778) to (0.513889,31.750000);
1778: spline -> from (6.152778,35.152778) to (3.597222,31.750000);
1779: spline -> from (6.277778,35.152778) to (5.347222,31.750000);
1780: spline -> from (6.416667,35.152778) to (7.333333,31.750000);
1781: spline -> from (6.597222,35.152778) to (9.736111,31.750000);
1782: spline -> from (6.027778,35.152778) to (1.972222,31.750000);
1783: spline -> from (48.444444,31.250000) to (55.222222,27.847222);
1784: spline -> from (47.277778,31.250000) to (39.013889,27.777778);
1785: spline -> from (48.041667,31.250000) to (49.666667,27.847222);
1786: spline -> from (47.916667,31.250000) to (47.916667,27.847222);
1787: spline -> from (41.847222,31.250000) to (34.388889,27.847222);
1788: spline -> from (41.833333,31.250000) to (32.833333,27.847222);
1789: spline -> from (41.847222,31.250000) to (35.000000,27.833333) to (34.930556,27.583333) to (34.847222,27.347222) to (26.625000,23.944444);
1790: spline -> from (41.805556,31.250000) to (13.583333,27.638889);
1791: spline -> from (43.125000,31.250000) to (31.347222,27.847222);
1792: spline -> from (43.180556,31.250000) to (42.208333,27.847222) to (42.180556,27.597222) to (42.138889,27.347222) to (42.138889,20.027778) to (42.111111,19.861111) to (42.069444,19.694444) to (41.763889,19.402778) to (38.444444,15.944444) to (38.250000,15.708333) to (38.402778,15.625000) to (50.861111,12.083333);
1793: spline -> from (43.152778,31.250000) to (37.402778,27.847222);
1794: spline -> from (43.152778,31.250000) to (36.027778,27.791667);
1795: spline -> from (43.125000,31.250000) to (21.625000,27.972222) to (19.444444,27.638889) to (19.375000,27.527778) to (19.305556,27.430556) to (17.930556,23.944444) to (17.847222,23.777778) to (17.763889,23.625000) to (14.500000,20.027778);
1796: spline -> from (53.861111,27.430556) to (43.013889,24.069444) to (42.861111,24.027778) to (42.750000,23.736111) to (42.638889,23.444444) to (42.638889,20.027778) to (42.611111,19.861111) to (42.569444,19.708333) to (38.944444,15.944444) to (38.750000,15.708333) to (38.916667,15.625000) to (50.861111,12.083333);
1797: spline -> from (38.847222,31.250000) to (28.916667,27.847222);
1798: spline -> from (38.638889,31.250000) to (26.041667,27.847222);
1799: spline -> from (38.722222,31.250000) to (26.736111,27.930556) to (26.583333,27.708333) to (26.430556,27.500000) to (22.777778,23.944444);
1800: spline -> from (27.805556,27.347222) to (22.888889,23.944444);
1801: spline -> from (25.000000,27.347222) to (22.694444,23.944444);
1802: spline -> from (24.888889,27.347222) to (20.958333,23.944444);
1803: spline -> from (33.041667,31.250000) to (23.902778,27.847222);
1804: spline -> from (56.222222,27.375000) to (63.569444,23.944444);
1805: spline -> from (56.013889,27.347222) to (59.694444,23.944444);
1806: spline -> from (55.861111,27.347222) to (57.625000,23.944444);
1807: spline -> from (55.555556,27.347222) to (50.041667,23.944444);
1808: spline -> from (55.666667,27.347222) to (53.736111,23.944444);
1809: spline -> from (55.430556,27.347222) to (46.125000,23.944444);
1810: spline -> from (55.402778,27.347222) to (44.222222,23.944444);
1811: spline -> from (55.750000,27.347222) to (56.166667,23.944444);
1812: spline -> from (55.694444,27.347222) to (54.888889,23.944444);
1813: spline -> from (38.750000,27.347222) to (40.861111,23.944444);
1814: spline -> from (38.569444,27.347222) to (38.277778,23.944444);
1815: spline -> from (38.416667,27.347222) to (34.055556,23.944444);
1816: spline -> from (38.333333,27.347222) to (31.888889,23.944444);
1817: spline -> from (38.236111,27.347222) to (29.430556,23.944444);
1818: spline -> from (38.500000,27.347222) to (36.458333,23.944444);
1819: spline -> from (64.666667,23.583333) to (81.500000,19.902778);
1820: spline -> from (64.111111,23.444444) to (64.111111,20.027778) to (64.083333,19.819444) to (64.041667,19.625000) to (63.736111,19.402778) to (59.250000,15.986111) to (59.138889,15.833333) to (59.027778,15.694444) to (51.611111,12.152778);
1821: spline -> from (64.041667,23.444444) to (63.236111,20.027778);
1822: spline -> from (64.666667,23.597222) to (84.652778,20.027778) to (85.361111,19.777778) to (86.069444,19.527778) to (86.333333,12.222222);
1823: spline -> from (60.708333,23.444444) to (70.208333,20.027778);
1824: spline -> from (60.083333,23.444444) to (61.583333,20.027778);
1825: spline -> from (59.875000,23.444444) to (58.833333,20.027778) to (58.763889,19.861111) to (58.694444,19.708333) to (55.138889,16.027778) to (55.027778,15.916667) to (54.916667,15.805556) to (51.472222,12.222222);
1826: spline -> from (59.958333,23.444444) to (59.944444,20.027778);
1827: spline -> from (57.694444,23.444444) to (56.888889,20.027778);
1828: spline -> from (57.791667,23.444444) to (58.236111,20.027778) to (58.222222,19.861111) to (58.194444,19.708333) to (54.638889,16.027778) to (54.527778,15.902778) to (54.416667,15.791667) to (51.444444,12.222222);
1829: spline -> from (57.750000,23.444444) to (57.763889,20.027778) to (57.736111,19.847222) to (57.694444,19.666667) to (57.388889,19.402778) to (53.944444,16.125000);
1830: spline -> from (50.263889,23.541667) to (64.111111,20.055556) to (64.444444,19.972222) to (64.569444,19.750000) to (64.694444,19.527778) to (67.152778,12.222222) to (67.236111,11.986111) to (67.305556,11.763889) to (67.611111,11.597222) to (73.430556,8.277778);
1831: spline -> from (49.388889,23.444444) to (46.125000,20.027778);
1832: spline -> from (49.291667,23.444444) to (44.833333,20.027778);
1833: spline -> from (49.694444,23.444444) to (50.347222,20.027778);
1834: spline -> from (49.861111,23.444444) to (52.819444,19.861111) to (52.819444,19.736111) to (52.819444,19.611111) to (52.513889,19.402778) to (48.111111,16.250000) to (47.805556,16.027778) to (47.805556,15.916667) to (47.805556,15.805556) to (51.013889,12.222222);
1835: spline -> from (49.583333,23.444444) to (48.930556,20.027778);
1836: spline -> from (49.486111,23.444444) to (47.527778,20.027778);
1837: spline -> from (53.597222,23.444444) to (53.638889,20.027778);
1838: spline -> from (53.750000,23.444444) to (55.819444,19.902778) to (55.819444,19.763889) to (55.819444,19.638889) to (55.513889,19.402778) to (51.625000,16.250000) to (51.305556,15.986111) to (51.277778,15.805556) to (51.236111,15.625000) to (51.236111,12.222222);
1839: spline -> from (53.694444,23.444444) to (54.930556,20.027778);
1840: spline -> from (45.319444,23.444444) to (43.750000,20.027778) to (43.666667,19.861111) to (43.569444,19.708333) to (39.944444,15.944444) to (39.736111,15.694444) to (40.097222,15.541667) to (50.861111,12.097222);
1841: spline -> from (43.652778,23.444444) to (43.180556,20.027778) to (43.125000,19.861111) to (43.069444,19.708333) to (39.444444,15.944444) to (39.250000,15.708333) to (39.444444,15.625000) to (50.861111,12.083333);
1842: spline -> from (82.125000,19.527778) to (82.944444,16.125000);
1843: spline -> from (82.208333,19.527778) to (84.250000,16.000000) to (84.305556,15.805556) to (84.361111,15.625000) to (84.944444,12.222222);
1844: spline -> from (82.055556,19.527778) to (82.097222,16.125000) to (82.111111,15.875000) to (82.111111,15.625000) to (82.291667,12.222222);
1845: spline -> from (81.944444,19.527778) to (80.611111,16.125000);
1846: spline -> from (81.500000,19.680556) to (61.000000,16.125000);
1847: spline -> from (82.277778,19.527778) to (85.055556,16.125000) to (85.194444,15.875000) to (85.333333,15.625000) to (86.277778,12.222222);
1848: spline -> from (51.236111,11.722222) to (51.236111,8.319444);
1849: spline -> from (62.861111,19.527778) to (58.750000,15.944444) to (58.638889,15.791667) to (58.527778,15.638889) to (51.611111,12.166667);
1850: spline -> from (82.861111,15.625000) to (81.180556,12.222222);
1851: spline -> from (83.138889,15.625000) to (84.861111,12.222222);
1852: spline -> from (82.958333,15.625000) to (82.347222,12.222222);
1853: spline -> from (83.041667,15.625000) to (83.638889,12.222222);
1854: spline -> from (83.222222,15.625000) to (86.138889,12.222222);
1855: spline -> from (84.986111,11.722222) to (84.986111,8.319444);
1856: spline -> from (84.805556,11.722222) to (82.472222,8.319444);
1857: spline -> from (82.305556,11.722222) to (82.305556,8.319444);
1858: spline -> from (80.430556,15.625000) to (79.388889,12.222222) to (79.319444,12.013889) to (79.236111,11.805556) to (78.916667,11.597222) to (74.166667,8.319444);
1859: spline -> from (80.486111,15.625000) to (80.083333,12.222222);
1860: spline -> from (60.472222,15.638889) to (51.611111,12.125000);
1861: spline -> from (81.055556,11.722222) to (81.055556,8.319444);
1862: spline -> from (80.680556,11.722222) to (74.180556,8.263889);
1863: spline -> from (81.138889,11.722222) to (82.222222,8.319444);
1864: spline -> from (70.833333,19.527778) to (69.861111,16.125000);
1865: spline -> from (70.708333,19.527778) to (68.055556,15.972222) to (68.027778,15.791667) to (67.986111,15.625000) to (67.986111,12.222222);
1866: spline -> from (71.305556,19.527778) to (76.388889,16.125000);
1867: spline -> from (71.388889,19.527778) to (77.569444,16.125000);
1868: spline -> from (71.013889,19.527778) to (72.430556,16.125000);
1869: spline -> from (70.902778,19.527778) to (70.902778,16.125000);
1870: spline -> from (71.125000,19.527778) to (73.944444,16.125000);
1871: spline -> from (70.777778,19.527778) to (69.055556,16.013889) to (69.055556,15.875000) to (69.055556,15.750000) to (70.916667,12.222222);
1872: spline -> from (71.486111,19.527778) to (78.847222,16.125000);
1873: spline -> from (71.208333,19.527778) to (75.166667,16.125000);
1874: spline -> from (70.736111,19.527778) to (68.555556,15.986111) to (68.555556,15.805556) to (68.541667,15.625000) to (69.305556,12.222222);
1875: spline -> from (70.166667,19.527778) to (60.097222,16.125000) to (60.069444,15.888889) to (60.027778,15.666667) to (51.611111,12.125000);
1876: spline -> from (61.416667,19.527778) to (57.916667,16.125000);
1877: spline -> from (61.263889,19.527778) to (55.583333,16.083333) to (55.500000,15.972222) to (55.416667,15.875000) to (51.500000,12.222222);
1878: spline -> from (61.333333,19.527778) to (56.708333,16.125000);
1879: spline -> from (70.069444,15.625000) to (73.513889,12.222222);
1880: spline -> from (69.972222,15.625000) to (72.250000,12.222222);
1881: spline -> from (68.361111,11.736111) to (73.430556,8.319444);
1882: spline -> from (76.680556,15.625000) to (75.638889,12.222222);
1883: spline -> from (76.777778,15.625000) to (76.986111,12.222222);
1884: spline -> from (78.055556,15.625000) to (78.333333,12.222222);
1885: spline -> from (72.611111,15.625000) to (73.680556,12.222222);
1886: spline -> from (74.125000,15.625000) to (73.791667,12.222222);
1887: spline -> from (74.180556,15.625000) to (74.541667,12.222222) to (74.597222,12.041667) to (74.638889,11.861111) to (76.847222,8.319444);
1888: spline -> from (71.236111,11.722222) to (73.625000,8.319444);
1889: spline -> from (79.263889,15.625000) to (78.416667,12.222222);
1890: spline -> from (75.472222,15.625000) to (75.569444,12.222222);
1891: spline -> from (69.666667,11.722222) to (73.527778,8.319444);
1892: spline -> from (73.861111,7.819444) to (74.541667,4.416667);
1893: spline -> from (73.805556,7.819444) to (73.847222,4.416667) to (73.875000,4.166667) to (73.902778,3.916667) to (74.597222,0.500000);
1894: spline -> from (73.777778,7.819444) to (73.375000,4.416667) to (73.361111,4.166667) to (73.347222,3.916667) to (73.347222,0.500000);
1895: spline -> from (73.722222,7.819444) to (72.625000,4.416667) to (72.569444,4.166667) to (72.513889,3.916667) to (72.236111,0.500000);
1896: spline -> from (74.069444,7.819444) to (77.402778,4.416667) to (77.555556,4.166667) to (77.694444,3.916667) to (78.208333,0.500000);
1897: spline -> from (74.000000,7.819444) to (76.486111,4.263889) to (76.541667,4.083333) to (76.583333,3.916667) to (76.875000,0.500000);
1898: spline -> from (73.930556,7.819444) to (75.625000,4.305556) to (75.666667,4.111111) to (75.708333,3.916667) to (75.819444,0.500000);
1899: spline -> from (73.763889,11.722222) to (73.805556,8.319444);
1900: spline -> from (74.513889,3.916667) to (73.430556,0.500000);
1901: spline -> from (74.597222,3.916667) to (74.652778,0.500000);
1902: spline -> from (74.750000,3.916667) to (76.750000,0.500000);
1903: spline -> from (74.847222,3.916667) to (78.013889,0.500000);
1904: spline -> from (74.430556,3.916667) to (72.375000,0.500000);
1905: spline -> from (74.680556,3.916667) to (75.750000,0.500000);
1906: spline -> from (74.972222,4.222222) to (75.097222,4.277778) to (75.222222,4.166667) to (75.097222,4.055556) to (74.972222,4.111111);
1907: spline -> from (40.513889,23.444444) to (34.097222,20.027778);
1908: spline -> from (40.638889,23.444444) to (35.652778,19.888889) to (35.541667,19.805556) to (35.430556,19.736111) to (29.861111,16.125000);
1909: spline -> from (40.986111,23.444444) to (40.708333,20.027778);
1910: spline -> from (40.805556,23.444444) to (38.069444,20.027778);
1911: spline -> from (37.736111,23.444444) to (30.888889,19.861111) to (30.777778,19.694444) to (30.652778,19.527778) to (29.555556,16.125000);
1912: spline -> from (37.819444,23.444444) to (32.361111,20.013889);
1913: spline -> from (33.500000,23.444444) to (29.680556,19.847222) to (29.638889,19.680556) to (29.597222,19.527778) to (29.486111,16.125000);
1914: spline -> from (33.027778,23.444444) to (22.180556,20.000000);
1915: spline -> from (33.430556,23.444444) to (28.805556,20.027778);
1916: spline -> from (31.069444,23.444444) to (26.555556,20.027778);
1917: spline -> from (31.152778,23.444444) to (27.847222,20.152778) to (27.541667,19.847222) to (27.541667,19.750000) to (27.541667,19.652778) to (29.347222,16.125000);
1918: spline -> from (28.513889,23.444444) to (25.041667,19.847222) to (25.041667,19.736111) to (25.041667,19.638889) to (25.347222,19.402778) to (29.180556,16.125000);
1919: spline -> from (35.888889,23.444444) to (30.388889,19.930556) to (30.291667,19.722222) to (30.180556,19.527778) to (29.513889,16.125000);
1920: spline -> from (33.347222,19.527778) to (29.736111,16.125000);
1921: spline -> from (29.097222,15.680556) to (22.763889,12.180556);
1922: spline -> from (22.375000,11.722222) to (22.277778,8.319444);
1923: spline -> from (22.180556,7.819444) to (20.916667,4.416667);
1924: spline -> from (21.902778,7.833333) to (16.861111,4.416667);
1925: spline -> from (22.277778,7.819444) to (22.277778,4.416667);
1926: spline -> from (57.222222,19.527778) to (62.236111,16.125000);
1927: spline -> from (56.500000,19.527778) to (52.361111,16.125000);
1928: spline -> from (56.555556,19.527778) to (52.958333,15.972222) to (52.875000,15.847222) to (52.791667,15.722222) to (51.333333,12.222222);
1929: spline -> from (53.513889,15.625000) to (51.388889,12.222222);
1930: spline -> from (62.819444,15.625000) to (65.597222,12.222222);
1931: spline -> from (62.666667,15.625000) to (63.555556,12.222222);
1932: spline -> from (62.875000,15.625000) to (66.361111,12.347222) to (66.666667,12.055556) to (66.680556,11.888889) to (66.694444,11.722222) to (66.194444,8.319444);
1933: spline -> from (61.861111,15.625000) to (51.611111,12.097222);
1934: spline -> from (62.750000,15.625000) to (64.680556,12.097222) to (64.680556,11.902778) to (64.666667,11.722222) to (63.638889,8.319444);
1935: spline -> from (62.513889,15.625000) to (61.458333,12.222222) to (61.430556,11.972222) to (61.402778,11.722222) to (61.791667,8.319444);
1936: spline -> from (62.458333,15.625000) to (60.583333,12.222222);
1937: spline -> from (62.569444,15.625000) to (62.277778,12.222222);
1938: spline -> from (52.000000,15.625000) to (51.291667,12.222222);
1939: spline -> from (77.000000,11.722222) to (77.000000,8.319444);
1940: spline -> from (65.833333,11.722222) to (66.125000,8.319444);
1941: spline -> from (64.250000,12.027778) to (64.375000,12.083333) to (64.500000,11.972222) to (64.375000,11.861111) to (64.250000,11.916667);
1942: spline -> from (66.527778,8.125000) to (66.652778,8.180556) to (66.777778,8.069444) to (66.652778,7.958333) to (66.527778,8.013889);
1943: spline -> from (60.444444,11.722222) to (60.444444,8.319444);
1944: spline -> from (62.347222,11.722222) to (63.486111,8.319444);
1945: spline -> from (62.222222,11.722222) to (61.847222,8.319444);
1946: spline -> from (78.263889,11.722222) to (77.083333,8.319444);
1947: spline -> from (33.305556,27.347222) to (26.527778,23.944444);
1948: spline -> from (31.819444,27.347222) to (24.944444,23.930556) to (24.888889,23.680556) to (24.819444,23.444444) to (15.583333,20.027778);
1949: spline -> from (31.791667,27.347222) to (24.472222,23.930556);
1950: spline -> from (45.847222,19.527778) to (45.388889,16.125000);
1951: spline -> from (45.763889,19.527778) to (44.222222,16.125000);
1952: spline -> from (45.666667,19.527778) to (42.930556,16.125000);
1953: spline -> from (45.555556,19.527778) to (41.361111,16.125000);
1954: spline -> from (44.569444,19.527778) to (45.305556,16.125000);
1955: spline -> from (44.388889,19.527778) to (42.847222,16.125000);
1956: spline -> from (44.277778,19.527778) to (41.277778,16.125000);
1957: spline -> from (44.486111,19.527778) to (44.138889,16.125000);
1958: spline -> from (50.041667,19.527778) to (45.680556,16.125000);
1959: spline -> from (30.083333,27.347222) to (23.041667,23.944444);
1960: spline -> from (37.513889,27.347222) to (39.819444,23.805556) to (39.819444,23.708333) to (39.819444,23.625000) to (36.069444,19.847222) to (36.055556,19.680556) to (36.041667,19.527778) to (36.638889,16.125000) to (36.694444,15.986111) to (36.750000,15.861111) to (50.861111,12.069444);
1961: spline -> from (36.777778,27.388889) to (21.013889,23.944444);
1962: spline -> from (36.861111,27.347222) to (27.236111,23.944444) to (27.194444,23.694444) to (27.138889,23.458333) to (20.305556,20.027778);
1963: spline -> from (21.625000,27.430556) to (13.986111,23.875000);
1964: spline -> from (21.777778,27.347222) to (18.861111,23.944444) to (18.722222,23.777778) to (18.583333,23.625000) to (15.375000,20.027778);
1965: spline -> from (22.152778,27.347222) to (34.763889,24.027778) to (35.111111,23.875000) to (34.916667,23.611111) to (31.305556,19.847222) to (31.319444,19.680556) to (31.319444,19.527778) to (32.291667,16.125000) to (32.361111,15.986111) to (32.430556,15.861111) to (50.861111,12.055556);
1966: spline -> from (22.027778,27.347222) to (23.958333,23.944444);
1967: spline -> from (13.583333,23.444444) to (13.305556,20.027778);
1968: spline -> from (13.513889,23.444444) to (12.319444,20.027778);
1969: spline -> from (45.763889,15.625000) to (50.861111,12.222222);
1970: spline -> from (22.277778,3.916667) to (22.277778,0.500000);
1971: spline -> from (51.444444,19.527778) to (45.777778,16.125000);
1972: spline -> from (51.541667,19.527778) to (47.069444,16.125000);
1973: spline -> from (47.041667,15.625000) to (50.944444,12.222222);
1974: spline -> from (53.444444,19.527778) to (50.805556,15.972222) to (50.791667,15.791667) to (50.763889,15.625000) to (51.208333,12.222222);
1975: spline -> from (53.291667,19.527778) to (48.930556,16.125000);
1976: spline -> from (53.375000,19.527778) to (50.097222,16.125000);
1977: spline -> from (54.013889,19.833333) to (54.138889,19.888889) to (54.263889,19.777778) to (54.138889,19.666667) to (54.013889,19.722222);
1978: spline -> from (22.027778,23.444444) to (15.472222,20.027778);
1979: spline -> from (22.180556,23.444444) to (17.694444,20.027778);
1980: spline -> from (22.347222,23.444444) to (19.972222,20.027778);
1981: spline -> from (21.347222,19.527778) to (19.500000,16.125000);
1982: spline -> from (21.541667,19.527778) to (22.000000,16.125000);
1983: spline -> from (21.444444,19.527778) to (20.666667,16.125000);
1984: spline -> from (48.791667,15.625000) to (51.069444,12.222222);
1985: spline -> from (19.361111,15.625000) to (19.361111,12.222222) to (19.375000,11.972222) to (19.388889,11.722222) to (19.833333,8.319444) to (19.888889,8.069444) to (19.930556,7.819444) to (20.763889,4.416667);
1986: spline -> from (22.055556,15.625000) to (22.361111,12.222222);
1987: spline -> from (20.638889,15.625000) to (21.083333,12.222222);
1988: spline -> from (20.472222,15.625000) to (18.736111,12.222222);
1989: spline -> from (20.583333,15.625000) to (20.138889,12.222222);
1990: spline -> from (20.583333,23.486111) to (14.666667,20.000000);
1991: spline -> from (26.444444,19.527778) to (29.263889,16.125000);
1992: spline -> from (55.541667,31.361111) to (64.472222,27.847222) to (64.791667,27.597222) to (65.111111,27.347222) to (65.111111,20.027778) to (65.083333,19.875000) to (65.041667,19.736111) to (59.750000,16.000000) to (59.638889,15.833333) to (59.527778,15.680556) to (51.611111,12.138889);
1993: spline -> from (54.791667,31.430556) to (36.638889,27.944444) to (36.416667,27.597222) to (36.180556,27.263889) to (24.472222,23.847222);
1994: spline -> from (54.791667,31.416667) to (37.555556,27.847222);
1995: spline -> from (55.111111,31.250000) to (54.458333,27.847222);
1996: spline -> from (11.291667,23.444444) to (10.722222,20.027778);
1997: spline -> from (10.736111,19.527778) to (11.402778,16.125000);
1998: spline -> from (10.680556,19.527778) to (10.708333,12.222222) to (10.750000,12.041667) to (10.777778,11.875000) to (16.305556,4.416667);
1999: spline -> from (21.111111,11.722222) to (21.111111,8.319444);
2000: spline -> from (6.458333,27.347222) to (5.194444,23.944444);
2001: spline -> from (6.763889,27.347222) to (9.416667,23.944444);
2002: spline -> from (6.625000,27.347222) to (7.527778,23.944444);
2003: spline -> from (7.805556,23.444444) to (10.486111,20.027778);
2004: spline -> from (0.750000,31.277778) to (6.166667,27.847222);
2005: spline -> from (0.430556,31.250000) to (1.750000,23.944444) to (1.805556,23.805556) to (1.861111,23.666667) to (10.305556,19.944444);
2006: spline -> from (0.541667,31.250000) to (4.944444,23.944444);
2007: spline -> from (18.611111,11.722222) to (18.611111,8.319444);
2008: spline -> from (18.611111,7.819444) to (18.611111,4.416667);
2009: .PE
2010: .ce
2011: \fBFigure 13.\fR CallGraph-2.
2012: .KE
2013: .NH 1
2014: Conclusions
2015: .PP
2016: .I Dag
2017: is a practical tool for drawing directed graphs.
2018: We have favored ease of use over low-level drawing control,
2019: by providing a simple graph description language and a few
2020: well-tuned heuristics that produce
2021: good drawings quickly in common cases.
2022: .NH 1
2023: References
2024: .LP
2025: |reference_placement
2026: .BP
2027: .Tm Syntax s
2028: .SH
2029: Appendix A. \fIDag\fP Syntax
2030: .LP
2031: .nf
2032: \fI
2033: program \fR:\fP statement-list
2034: \fR;\fI
2035:
2036: statement-list \fR:\fP statement-list statement
2037: \fR|\fP \f5/* empty */\fP
2038: \fR;\fI
2039:
2040: statement \fR:\fP draw-statement
2041: \fR|\fP edge-statement
2042: \fR|\fP control-statement
2043: \fR;\fI
2044:
2045: draw-statement \fR:\fP \f5draw \fPnode-list node-desc \f5;\fP
2046: \fR|\fP \f5draw nodes \fPnode-desc \f5;\fP
2047: \fR|\fP \f5draw edges \fPedge-desc \f5;\fP
2048: \fR;\fI
2049:
2050: node-list \fR:\fP node-list \fR[\fP\f5,\fP\fR]\fP node-name
2051: \fR|\fP node-name
2052: \fR;\fI
2053:
2054: node-desc \fR:\fP node-desc-item
2055: \fR|\fP node-desc node-desc-item
2056: \fR;\fI
2057:
2058: node-desc-item \fR:\fP \f5width\fP float
2059: \fR|\fP \f5height\fP float
2060: \fR|\fP \f5pointsize\fP integer
2061: \fR|\fP \f5label\fP string
2062: \fR|\fP \f5label\fP \f5 { \fPdrawing-code\f5 } \fP
2063: \fR|\fP \f5as { \fPdrawing-code\f5 } \fP
2064: \fR|\fP \f5as\fP string
2065: \fR|\fP \f5color\fP string
2066: \fR;\fI
2067:
2068: edge-statement \fR:\fP \fR[\fP\f5ordered\fP\fR]\fP \fR[[\fP\f5back\fP\fR]\fPedge from\fP\fR]\fP node-name \fR[\fP\f5to\fP\fR]\fP head-list \f5;\fP
2069: \fR|\fP \fR[\fP\f5back\fP\fR]\fP\f5path\fP \fR[\fP\f5from\fP\fR]\fP node-name \fR[\fP\f5to\fP\fR]\fP head-list \f5;\fP
2070: \fR;\fI
2071:
2072: head-list \fR|\fP head-list head
2073: \fR|\fP head-list \fR[\fP\f5,\fP\fR]\fP \fR[\fP\f5to\fP\fR]\fP head
2074: \fR|\fP \f5/* empty */\fP
2075: \fR;\fI
2076:
2077: head \fR:\fP node-name edge-desc
2078: \fR|\fP node-name
2079: \fR;\fI
2080:
2081: edge-desc \fR:\fP edge-desc-item
2082: \fR|\fP edge-desc edge-desc-item
2083: \fR;\fI
2084:
2085: edge-desc-item \fR:\fP \f5weight \fP integer
2086: \fR|\fP \f5label \fPstring
2087: \fR|\fP \f5label { \fPdrawing-code\f5 }\fP
2088: \fR|\fP \f5pointsize\fP integer
2089: \fR|\fP \f5color\fP string
2090: \fR|\fP inkvalue
2091: \fR;\fI
2092:
2093: inkvalue \fR:\fP \f5solid\fP
2094: \fR|\fP \f5dashed\fP
2095: \fR|\fP \f5dotted\fP
2096: \fR|\fP \f5invis\fP
2097: \fR;\fI
2098:
2099: control-statement \fR:\fP \f5separate\fP sep-list \f5;\fP
2100: \fR|\fP \f5minimum rank\fP node-list \f5;\fP
2101: \fR|\fP \f5maximum rank\fP node-list \f5;\fP
2102: \fR|\fP \f5same rank\fP node-list \f5;\fP
2103: \fR;\fI
2104:
2105: sep-list \fR:\fP sep-list sep-item
2106: \fR|\fP \f5/* empty */\fP
2107: \fR;\fI
2108:
2109: sep-item \fR:\fP \f5nodes\fP float
2110: \fR|\fP \f5ranks\fP float
2111: \fR|\fP \f5ranks\fP float \f5exactly\fP
2112: \fR|\fP \f5ranks\fP float \f5equally\fP
2113: \fR;\fI
2114:
2115: node-name \fR:\fP string
2116: \fR;\fI
2117:
2118: .fi
2119: \fR
2120: .PP
2121: A \fIstring\fP is any sequence of non-whitespace, non-punctuation characters,
2122: or any quoted string that does not contain a newline.
2123: A \fIdrawing-code\fP is any sequence of characters containing balanced
2124: left and right curly braces.
2125: .NH 1
2126: Appendix B. \*(PO Interface
2127: .PP
2128: \f5dag -Tps\fP generates \*(PO\ code.
2129: The drawing is in the default \*(PO\ coordinate system.
2130: Two procedures are needed to define a new node shape.
2131: The first draws the shape over the current point.
2132: It takes three arguments off the stack:
2133: the node width, height, and name.
2134: The second procedure computes where edges intersect the shape.
2135: Its arguments are the $x$ and $y$ dimensions of the shape, and a
2136: ray. The first point is the origin and the second point that
2137: defines the ray is always on the bounding box of the node when
2138: it is placed at $(0,0)$. This procedure returns the point where
2139: the ray intersects the shape (or if it misses the shape, then
2140: the nearest point or at least the point on the bounding box
2141: that was passed as an argument). The argument points are always
2142: in the same quadrant.
2143: .PP
2144: For some examples of shape-drawing procedures, examine the
2145: output of \f5dag -Tps\fP for definitions of procedures such
2146: as \f5Ellipse\fP and \f5Ellipse_clip\fP.
2147: .PP
2148: Shaded nodes may be useful when color output is not available.
2149: Here is an example.
2150: .P1
2151: \&.GR
2152: \&.PS
2153: /setdagcolor {/daggrayscale exch def} def
2154:
2155: /ShadedBox {
2156: /height exch def
2157: /width exch def
2158: /nodename exch def
2159: currentpoint 2 copy
2160: .P3
2161: newpath
2162: moveto
2163: width -2 div
2164: height -2 div
2165: rmoveto
2166: width 0 rlineto
2167: 0 height rlineto
2168: width neg 0 rlineto
2169: closepath
2170: .P3
2171: gsave
2172: daggrayscale setgray
2173: fill
2174: grestore
2175: stroke
2176: moveto
2177: nodename width .9 mul height .9 mul daglabel
2178: } def
2179: .P3
2180: /ShadedBox_clip { Box_clip } def
2181: \&.PE
2182: draw nodes as ShadedBox;
2183: draw nodes color "1";
2184: draw a color ".7";
2185: draw b color ".9";
2186: a b c;
2187: \&.GE
2188: .P2
2189: .PP
2190: \&\f5setdagcolor\fP is called before drawing a node or edge.
2191: The color value is emitted as \*(PO code
2192: which usually pushes something on the stack
2193: that \f5setdagcolor\fP consumes.
2194: For drawing shaded boxes, colors will be real values
2195: between 0 and 1, where 0 is black and 1 is white.
2196: Thus \f5setdagcolor\fP is redefined to store its argument
2197: it in the global variable \f5daggrayscale\fP where
2198: \f5ShadedBox\fP can find it later.
2199: .PP
2200: In the definition of \f5ShadedBox\fP, the path of rectangle is created
2201: and then the sequence \f5daggrayscale setgray fill\fP shades its interior.
2202: The shading is done within \f5gsave/grestore\fP because
2203: we want to shade neither the outline of the box itself nor its label.
2204: .PP
2205: Since \f5ShadedBox\fP has the same boundary as \f5Box\fP,
2206: \f5ShadedBox_clip\fP is implemented by calling \f5Box_clip\fP.
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.