Return to dag.c CVS log

Up to [Research Unix] / researchv10no / cmd / dag

Annotation of researchv10no/cmd/dag/dag.c, revision 1.1

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.