![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to dag.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / dag|
Return to dag.c CVS log | Up to [Research Unix] / researchv10no / cmd / dag |
1.1 root 1: /* DAG - draw a directed graph
2: * Gansner North Vo
3: */
4:
5: const char* Version = "\n@(#)Version M-03/31/89\0\n";
6:
7: #include "draw_dag.h"
8: #include "dag.h"
9: #include "parsedag.h"
10: #include "TrieFA.ins.c"
11:
12: /* useful constants */
13: const double Pi = 3.1415926537;
14: const double IPP = .01; // real inches per point of type
15: const int Resolution = 72; // points per virtual inch
16:
17: /*** globals ***/
18: Infile Current_file;
19: boolean Uselib = true; // user specified lib with -l option
20: char* Lib_path; // library directory
21: int N; // number of nodes
22: int Extent; // extent of node and edge array including spares
23: DAG_node_t** Node; // node list
24: DAG_edge_t** Edge; // edge list
25: user_info_t User; // user options from .GS line
26: options_t Options; // user options from graph input (for draw_dag)
27: char* Cmd_name; // from command line
28: output_lang_t Output_type;
29: int Xmax,Ymax;
30: Point Page_size;
31: Point Margin = {36,36};
32:
33: void dumprank(int * rank) {
34: if (rank)
35: while (*rank >= 0) fprintf(stderr,"%d ",*rank++);
36: fprintf(stderr,"\n");
37: }
38:
39: void dumpgraph() {
40: fprintf(stderr,"global ranksep %d nodesep %d\n",Options.ranksep,Options.nodesep);
41: for (int i = 0; i < N; i++) {
42: fprintf(stderr,"%s -> ",Node[i]->name);
43: for (DAG_edge_t *e = Edge[i]; e; e = e->nextof())
44: fprintf(stderr,"%s ",Node[e->node]->name);
45: fprintf(stderr,"\n size %d %d\n",Node[i]->height,Node[i]->width);
46: }
47: fprintf(stderr,"min rank: "); dumprank(Options.source_nodes);
48: fprintf(stderr,"max rank: "); dumprank(Options.sink_nodes);
49: for (i = 0; i < Options.n_same_nodes; i++) {
50: fprintf(stderr,"rank %d: ",i);
51: dumprank(Options.same_nodes[i]);
52: }
53: }
54:
55: /*
56: * translate draw_dag coordinates to preferred system.
57: */
58:
59: void translate() {
60: int node;
61: if (!User.rotated) {
62: switch(Output_type) {
63: case Pic:
64: case Cip:
65: case Postscript:
66: case Graphdraw:
67: for (node = 0; node < N; node++) {
68: Node[node]->pos.y = Ymax - Node[node]->pos.y;
69: for (DAG_edge_t *e = Edge[node]; e; e = e->nextof()) {
70: for (int sp = 0; e->splinept[sp].x >= 0; sp++)
71: e->splinept[sp].y = Ymax - e->splinept[sp].y;
72: e->top.y = Ymax - e->top.y;
73: e->bottom.y = Ymax - e->bottom.y;
74: }
75: }
76: break;
77: }
78: }
79: else {
80: swap(Xmax,Ymax);
81: switch(Output_type) {
82: case Pic:
83: case Cip:
84: case Postscript:
85: case Graphdraw:
86: for (node = 0; node < N; node++) {
87: swap(Node[node]->pos.x,Node[node]->pos.y);
88: for (DAG_edge_t *e = Edge[node]; e; e = e->nextof()) {
89: for (int sp = 0; e->splinept[sp].x >= 0; sp++)
90: swap(e->splinept[sp].x,e->splinept[sp].y);
91: swap(e->top.x,e->top.y);
92: swap(e->bottom.x,e->bottom.y);
93: }
94: }
95: break;
96: }
97: }
98: }
99:
100: /*
101: * compute Xmax, Ymax of drawing region
102: */
103: void find_drawing_size() {
104: int node;
105: Xmax = 0; Ymax = 0;
106:
107: /* find extent of drawing region */
108: for (node = 0; node < N; node++) {
109: Xmax = max(Xmax,Node[node]->pos.x + (Node[node]->width + 1) / 2);
110: Ymax = max(Ymax,Node[node]->pos.y + (Node[node]->height + 1) / 2);
111: for (DAG_edge_t *e = Edge[node]; e; e = e->nextof()) {
112: for (int sp = 0; e->splinept[sp].x >= 0; sp++) {
113: Xmax = max(Xmax,e->splinept[sp].x);
114: Ymax = max(Ymax,e->splinept[sp].y);
115: }
116: }
117: }
118: }
119:
120: void make_drawing() {
121: if (N <= 0) return;
122:
123: draw_dag(N,(node_t**)Node,(edge_t**)Edge,Options);
124: find_drawing_size();
125: translate();
126:
127: switch (Output_type) {
128: case Pic:
129: case Cip:
130: emit_pic();
131: break;
132: case Postscript:
133: emit_ps();
134: break;
135: case Graphdraw:
136: emit_graphdraw();
137: break;
138: }
139: }
140:
141: void global_init(char *cmdname) {
142: Node = new DAG_node_t*[Init_extent];
143: Edge = new DAG_edge_t*[Init_extent];
144: Extent = Init_extent;
145: Cmd_name = cmdname;
146: Options = reset_options();
147: }
148:
149: void graph_init() {
150: N = 0;
151: Syntax_error = 0;
152: User = user_info_t();
153: Default_node = Reset_node;
154: Default_edge = Reset_edge;
155: }
156:
157: void reclaim_nodes() {
158: for (int i = 0; i < N; i++) delete Node[i];
159: }
160:
161: void reclaim_edges() {
162: DAG_edge_t *e,*f;
163: for (int node = 0; node < N; node++) {
164: if (e = Edge[node]) {
165: if (e->splinept) delete e->splinept;
166: while (e) {
167: f = e->nextof();
168: delete e;
169: e = f;
170: }
171: Edge[node] = 0;
172: }
173: }
174: }
175:
176: void reclaim_samenodesets() {
177: delete Options.source_nodes;
178: Options.source_nodes = 0;
179: delete Options.sink_nodes;
180: Options.sink_nodes = 0;
181: for (int i = 0; i < Options.n_same_nodes; i++) {
182: delete Options.same_nodes[i];
183: Options.same_nodes[i] = 0;
184: }
185: Options.same_nodes = 0;
186: Options.n_same_nodes = 0;
187: }
188:
189: void reclaim_storage() {
190: reclaim_nodes();
191: reclaim_edges();
192: reclaim_hashtable();
193: reclaim_samenodesets();
194: freestrings();
195: }
196:
197: main(int argc, char**argv) {
198: char **args = argv;
199: int nfiles = 0;
200: boolean use_stdin = true;
201:
202: global_init(argv[0]);
203: for (int arg = 1; arg < argc; arg++) {
204: if (*argv[arg] == '-') {
205: switch(argv[arg][1]) {
206: case 'O':
207: Options.quick = false;
208: break;
209: case 'l':
210: Uselib = false;
211: break;
212: case 'v':
213: Options.verbose = true;
214: break;
215: case 'T': // type of output
216: set_output_type(&argv[arg][2]);
217: break;
218: case 'p':
219: set_page_size(&argv[arg][2]);
220: break;
221: }
222: }
223: else {nfiles++; use_stdin = false;}
224: }
225: if (use_stdin) nfiles = 1;
226:
227: for (int file = 0; file < nfiles; file++) {
228: char buf[BUFSIZ];
229: if (!use_stdin) Current_file = nextfile(args);
230: if (!Current_file.fp) continue;
231: if (Output_type == Pic) printf(".lf 1 %s\n",Current_file.name);
232: while (Current_file.gets(buf,sizeof(buf))) {
233: if (buf[0] == '.' && buf[1] == 'G' &&((buf[2] == 'D')||(buf[2] == 'R'))) {
234: /* they're playing our song */
235: graph_init();
236: if (buf[2] == 'R') User.set_rotate();
237: double userwidth = 0., userheight = 0.;
238: char fill[80]; fill[0] = 0;
239: sscanf(&buf[3],"%lf %lf %s",&userwidth,&userheight,fill);
240: User.set_size(userwidth,userheight);
241: if (!strcmp(fill,"fill"))
242: set_bounds(userwidth,userheight);
243: yyparse();
244: reclaim_storage();
245: }
246: else if ((Output_type == Pic) && buf[0] == '.' && buf[1] == 'l' && buf[2] == 'f') {
247: char auxbuf[BUFSIZ];
248: int line_number;
249: if (sscanf(buf + 3,"%d %s",&line_number,auxbuf) == 2) {
250: free(Current_file.name);
251: printf(".lf %d %s\n",Current_file.line_number = line_number,
252: Current_file.name = strcpy(new char[strlen(auxbuf)+1],auxbuf));
253: }
254: else
255: printf(".lf %d\n",Current_file.line_number = line_number);
256: }
257: else fputs(buf,stdout);
258: }
259: if (!use_stdin) {
260: free(Current_file.name);
261: fclose(Current_file.fp);
262: }
263: }
264: }
265:
266: /*** the lexer ***/
267:
268: static char tokenbuf[BUFSIZ];
269: static char lexbuf[BUFSIZ];
270: static char *lexbufptr;
271:
272: static char *eatwhitespace(char *p) {
273: while (isspace(*p)) p++;
274: return p;
275: }
276:
277: /* grab drawing-code enclosed in matching curly braces. strip braces. */
278: static char *scandesc() {
279: char sidebuf[BUFSIZ],*p;
280: int left = BUFSIZ - 1;
281: int depth = 1; // eat opening curlybrace
282:
283: p = sidebuf;
284: while (left) {
285: if (!*lexbufptr) {
286: lexbufptr = Current_file.gets(lexbuf,sizeof(lexbuf));
287: if (!lexbufptr) {
288: yyerror("unmatched '{' in drawing information");
289: return 0;
290: }
291: }
292: if (*lexbufptr == '}') {
293: depth--;
294: if (depth == 0) {
295: *p = 0;
296: lexbufptr++;
297: return newstring(sidebuf);
298: }
299: }
300: else if (*lexbufptr == '{') depth++;
301: *p++ = *lexbufptr++;
302: left--;
303: }
304: yyerror("overran buffer for drawing info");
305: return 0;
306: }
307:
308: /* bump p and return pointer to (static) null delimited copy of name token */
309: char *delimitname(char* &p) {
310: char *q = tokenbuf;
311:
312: p = eatwhitespace(p);
313: if (!*p) return 0;
314: while ((*p) && !isspace(*p) && (*p != ';') && (*p != '{') && (*p != '}')
315: && (*p != ',') && (*p != '\"'))
316: *q++ = *p++;
317: *q = 0;
318: return tokenbuf;
319: }
320:
321: /* delimit a quoted string */
322: char *quotelimit(char* &p) {
323: char *q = tokenbuf;
324:
325: ++p;
326: while ((*p) && *p != '\"') {
327: if ((*p == '\\') && (*(p + 1) == '\"')) p++;
328: *q++ = *p++;
329: }
330: if (!*p) yyerror("quoted string ran off end of line");
331: p++;
332: *q = 0;
333: return tokenbuf;
334: }
335:
336: int squirrelbufinuse,squirrelbufsize;
337: char *squirrelbuf;
338: void squirrel(const char*p)
339: {
340: int l = strlen(p);
341: if (l > squirrelbufsize - squirrelbufinuse) {
342: if (!squirrelbuf) squirrelbuf = (char*)malloc(BUFSIZ);
343: else squirrelbuf = (char*)realloc(squirrelbuf,squirrelbufsize += BUFSIZ);
344: }
345: strcpy(squirrelbuf + squirrelbufinuse,p);
346: squirrelbufinuse += l;
347: }
348: void unsquirrel()
349: {
350: if (squirrelbuf) fputs(squirrelbuf,stdout);
351: squirrelbufinuse = 0;
352: }
353:
354: void copyPS()
355: {
356: char buf[BUFSIZ];
357: char *p;
358: while (p = Current_file.gets(buf,sizeof(buf))) {
359: if (p[0] == '.' && p[1] == 'P' && p[2] == 'E') return;
360: else squirrel(buf);
361: }
362: yyerror("unmatched .PS inside .GS");
363: }
364:
365: int myyylex()
366: {
367: int rv = myyylex();
368: fprintf(stderr,"returning %d\n",rv);
369: if (rv == STRING || rv == DESC ) fprintf(stderr,"string val is %s\n",yylval.s);
370: return rv;
371: }
372:
373: int yylex()
374: {
375: if (lexbufptr) lexbufptr = eatwhitespace(lexbufptr);
376: while (!lexbufptr || !*lexbufptr) {
377: while ((lexbufptr = Current_file.gets(lexbuf,sizeof(lexbuf)))
378: && (lexbuf[0] == '.')) {
379: if (lexbuf[1] == 'P' && lexbuf[2] == 'S') copyPS();
380: else {
381: if (lexbuf[1] == 'G' && lexbuf[2] == 'E') {lexbufptr = 0;return EOF;}
382: else squirrel(lexbuf); // assume it's a troff control
383: }
384: }
385: if (!lexbufptr) {
386: yyerror("unmatched .GS");
387: return EOF;
388: }
389: lexbufptr = eatwhitespace(lexbufptr);
390: }
391:
392: switch(*lexbufptr) {
393: case ',':
394: case ';':
395: return *lexbufptr++;
396: case '\"':
397: yylval.s = newstring(quotelimit(lexbufptr));
398: return STRING;
399: case '}':
400: yyerror("unexpected '}'");
401: lexbufptr++;
402: return ';';
403: case '{' :
404: lexbufptr++;
405: yylval.s = scandesc();
406: return DESC;
407: }
408: char *tokenptr = delimitname(lexbufptr);
409: char *p = tokenptr;
410:
411: TFA_Init();
412: while (*p) {
413: TFA_Advance(*p);
414: p++;
415: }
416: int token = TFA_Definition();
417: if (token != -1) return token;
418: yylval.s = newstring(tokenptr);
419: return STRING;
420: }
421:
422: void error_context()
423: {
424: char *p,*q;
425: if (!lexbufptr) return;
426: fprintf(stderr,"context is: ");
427: for (p = lexbufptr - 1; (p > lexbuf) && (!isspace(*p)); p--);
428: for (q = lexbuf; q < p; q++) fputc(*q,stderr);
429: fputs(" >>> ",stderr);
430: for (; q < lexbufptr; q++)fputc(*q,stderr);
431: fputs(" <<< ",stderr);
432: fputs(lexbufptr,stderr);
433: }
434: void yyerror(char*s,char *s1, char* s2, char *s3, char *s4) {
435: extern void error_context();
436:
437: if (Syntax_error) return;
438: Syntax_error = 1;
439: fprintf(stderr, "%s: ", Cmd_name);
440: fprintf(stderr, s, s1, s2, s3, s4);
441: fprintf(stderr, " near line %d, file %s\n",Current_file.line_number,
442: Current_file.name);
443: error_context();
444: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.