Return to dag_start.c CVS log

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

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

1.1     ! root        1: #include       "draw_dag.h"
        !             2: 
        !             3: 
        !             4: /*
        !             5:        Routines to start and end draw_dag.
        !             6:        In the starting phase, make in/out edge lists with no self-loops,
        !             7:        multiple edges and cycles. This phase also makes sure that 
        !             8:        constraints of the form 'this set of nodes must be at the same level'
        !             9:        can be later satisfied.
        !            10: */
        !            11: static int     Clean_up;       // 1 if things need cleaned up before starting
        !            12: 
        !            13: static int     multiple(int, edge_t*, int),
        !            14:                findroot(int);
        !            15: static void    dfs(int, edge_t**, edge_t**, int*, int*, int**),
        !            16:                setunion(int*);
        !            17: 
        !            18: 
        !            19: 
        !            20: void dag_start(int n_nodes, node_t **nodes, edge_t **outedges, options_t options)
        !            21: {
        !            22:        // clean up previous space
        !            23:        if(Clean_up)
        !            24:        {
        !            25:                if(Verbose)
        !            26:                        fprintf(stderr,"Clean up space from last call\n");
        !            27:                Clean_up = 0;
        !            28: 
        !            29:                for(int v = 0; v < N_real_nodes; v++)
        !            30:                {
        !            31:                        for(edge_t *e = Outedges[v]; e; e = e->next)
        !            32:                                if(e->splinept)
        !            33:                                        delete e->splinept;
        !            34:                        if(Noedges)
        !            35:                                for(e = Noedges[v]; e; e = e->next)
        !            36:                                        if(e->splinept)
        !            37:                                                delete e->splinept;
        !            38:                }
        !            39: 
        !            40:                deledges(N_nodes,Inedges);
        !            41:                deledges(N_nodes,Outedges);
        !            42:                if(Noedges)
        !            43:                        deledges(N_real_nodes,Noedges);
        !            44:                Outedges = Inedges = Noedges = NULL;
        !            45:                if(Istems)
        !            46:                {
        !            47:                        delete Istems;
        !            48:                        delete Ostems;
        !            49:                        delete Stems;
        !            50:                        Istems = Ostems = NULL;
        !            51:                        Stems = NULL;
        !            52:                }
        !            53: 
        !            54:                for(v = 0; v <= Maxlevel; v++)
        !            55:                        delete Rank[v];
        !            56:                delete Rank; Rank = NULL;
        !            57: 
        !            58:                delete Root; Root = NULL;
        !            59:                delete Level; Level = NULL;
        !            60:                delete N_level; N_level = NULL;
        !            61:                delete Width; Width = NULL;
        !            62:                delete Height; Height = NULL;
        !            63:                delete Levelheight; Levelheight = NULL;
        !            64:                delete Levelpos; Levelpos = NULL;
        !            65:                delete Nodepos; Nodepos = NULL;
        !            66:                delete Deleted; Deleted = NULL;
        !            67:        }
        !            68: 
        !            69:        if (n_nodes <= 0)
        !            70:                return;
        !            71: 
        !            72:        // copy node Widths/Heights
        !            73:        Width = new int[n_nodes];
        !            74:        Height = new int[n_nodes];
        !            75:        for(int n = 0; n < n_nodes; ++n) {
        !            76:                Width[n] = nodes[n]->width;
        !            77:                Height[n] = nodes[n]->height;
        !            78:        }
        !            79:        Nodesep = options.nodesep;
        !            80:        Levelsep = options.ranksep;
        !            81:        Xbound = options.xbound;
        !            82:        Ybound = options.ybound;
        !            83: 
        !            84:        // construct equivalence class indices for vertices at same levels
        !            85:        int *srcs = options.source_nodes;
        !            86:        int *sinks = options.sink_nodes;
        !            87:        int **same = options.same_nodes;
        !            88:        Root = new int[n_nodes];
        !            89:        for(n = 0; n < n_nodes; ++n)
        !            90:                Root[n] = n;
        !            91:        if(srcs && srcs[0] != -1)
        !            92:                setunion(srcs);
        !            93:        if(sinks && sinks[0] != -1)
        !            94:                setunion(sinks);
        !            95:        if(same)
        !            96:                for(n = 0; same[n]; ++n)
        !            97:                        if(same[n][0] != -1)
        !            98:                                setunion(same[n]);
        !            99:        // compress union trees
        !           100:        for(n = 0; n < n_nodes; ++n)
        !           101:                (void)findroot(n);
        !           102: 
        !           103:        // construct auxilliary lists of edges turned around by min/max nodes
        !           104:        int source = (srcs && srcs[0] != -1) ? Root[srcs[0]] : -1;
        !           105:        int sink = (sinks && sinks[0] != -1) ? Root[sinks[0]] : -1;
        !           106:        if(sink == source)
        !           107:                sink = -1;
        !           108:        edge_t **aux = (edge_t **)0;
        !           109:        if(source >= 0 || sink >= 0)
        !           110:        {
        !           111:                aux = new edge_t*[n_nodes];
        !           112:                for(n = 0; n < n_nodes; ++n)
        !           113:                {
        !           114:                        if(Root[n] != source)
        !           115:                        {
        !           116:                                for(edge_t *e = outedges[n]; e; e = e->next)
        !           117:                                if(Root[e->node] == source)
        !           118:                                {
        !           119:                                        aux[e->node] = new edge_t(n,e->weight,
        !           120:                                                e->width,e->minlen,aux[e->node]);
        !           121:                                        aux[e->node]->chain = e;
        !           122:                                        e->chain = aux[e->node];
        !           123:                                }
        !           124:                        }
        !           125: 
        !           126:                        if(Root[n] == sink)
        !           127:                        {
        !           128:                                for(edge_t *e = outedges[n]; e; e = e->next)
        !           129:                                if(Root[e->node] != sink)
        !           130:                                {
        !           131:                                        aux[e->node] = new edge_t(n,e->weight,
        !           132:                                                e->width,e->minlen,aux[e->node]);
        !           133:                                        aux[e->node]->chain = e;
        !           134:                                        e->chain = aux[e->node];
        !           135:                                }
        !           136:                        }
        !           137:                }
        !           138:        }
        !           139: 
        !           140:        // make space for edges
        !           141:        N_edges = N_self_edges = N_repeat_edges = N_revert_edges = 0;
        !           142:        N_nodes = N_real_nodes = n_nodes;
        !           143:        Inedges = new edge_t*[n_nodes];
        !           144:        Outedges = new edge_t*[n_nodes];
        !           145: 
        !           146:        // use depth-first search to construct edge lists
        !           147:        int *active = new int[n_nodes];
        !           148:        int *marked = new int[n_nodes];
        !           149: 
        !           150:        // compute the squashed trees of equi-level nodes
        !           151:        int **sets = new int*[N_nodes];
        !           152:        for(n = 0; n < N_nodes; ++n)
        !           153:                active[Root[n]]++;
        !           154:        for(n = 0; n < N_nodes; ++n)
        !           155:                if(active[n] > 0) {
        !           156:                        sets[n] = new int[active[n]+1];
        !           157:                        sets[n][active[n]] = -1;
        !           158:                        active[n] = 0;
        !           159:                }
        !           160:        for(n = 0; n < N_nodes; ++n)
        !           161:                sets[Root[n]][active[Root[n]]++] = n;
        !           162:        for(n = 0; n < N_nodes; ++n)
        !           163:                active[n] = 0;
        !           164: 
        !           165:        for(n = 0; n < n_nodes; ++n)
        !           166:                if(n == Root[n] && !marked[n])
        !           167:                        dfs(n,outedges,aux,active,marked,sets);
        !           168:        delete active;
        !           169:        delete marked;
        !           170:        for(n = 0; n < n_nodes; ++n)
        !           171:                if(sets[n])
        !           172:                        delete sets[n];
        !           173:        delete sets;
        !           174: 
        !           175:        // restore space used by auxilliary edges
        !           176:        if(source >= 0 || sink >= 0)
        !           177:        {
        !           178:                for(n = 0; n < n_nodes; ++n)
        !           179:                {
        !           180:                        edge_t *nexte;
        !           181:                        for(edge_t *e = aux[n]; e; e = nexte)
        !           182:                        {
        !           183:                                nexte = e->next;
        !           184:                                delete e;
        !           185:                        }
        !           186:                }
        !           187:                delete aux;
        !           188:        }
        !           189: 
        !           190:        if (Verbose)
        !           191:        {
        !           192: #ifdef TIMING
        !           193:                fprintf(stderr,"%d\t%d\t",N_nodes,N_edges);
        !           194: #else
        !           195:                fprintf(stderr,"N_nodes = %d, N_edges=%d\n",N_nodes,N_edges);
        !           196:                fprintf(stderr,"N_self_edges = %d\n", N_self_edges);
        !           197:                fprintf(stderr,"N_flat_edges = %d\n", N_flat_edges);
        !           198:                fprintf(stderr,"N_repeat_edges = %d\n", N_repeat_edges);
        !           199:                fprintf(stderr,"N_revert_edges = %d\n", N_revert_edges);
        !           200: #endif
        !           201:        }
        !           202: }
        !           203: 
        !           204: 
        !           205: void dag_end(node_t **nodes, edge_t **outedges)
        !           206: {
        !           207:        // output node positions
        !           208:        for(int v = 0; v < N_real_nodes; v++)
        !           209:        {
        !           210:                nodes[v]->pos.x = Nodepos[v];
        !           211:                nodes[v]->pos.y = Levelpos[Level[v]];
        !           212:        }
        !           213: 
        !           214:        // output edge splines
        !           215:        for(v = 0; v < N_real_nodes; ++v)
        !           216:        for(edge_t *e = outedges[v]; e; e = e->next)
        !           217:        {
        !           218:                // copy the points
        !           219:                Point *sp = e->chain->splinept;
        !           220:                for(int n_points = 0; sp[n_points].x >= 0; ++n_points)
        !           221:                        ;
        !           222: 
        !           223:                Point *pt;
        !           224:                if(e->chain->count > 1)
        !           225:                {
        !           226:                        pt = new Point[n_points+1];
        !           227:                        for(int n = 0; n <= n_points; ++n)
        !           228:                        {
        !           229:                                pt[n].x = sp[n].x;
        !           230:                                pt[n].y = sp[n].y;
        !           231:                        }
        !           232:                }
        !           233:                else
        !           234:                {
        !           235:                        pt = sp;
        !           236:                        e->chain->splinept = NULL;
        !           237:                }
        !           238: 
        !           239:                // reverse the order of inverted edges
        !           240:                if(Level[v] > Level[e->node])
        !           241:                {
        !           242:                        int n = 0, m = n_points-1;
        !           243:                        for(; n < m; ++n, --m)
        !           244:                        {
        !           245:                                swap(pt[n].x,pt[m].x);
        !           246:                                swap(pt[n].y,pt[m].y);
        !           247:                        }
        !           248:                }
        !           249: 
        !           250:                e->top.x = pt[1].x;
        !           251:                e->top.y = pt[1].y;
        !           252:                e->bottom.x = pt[n_points-2].x;
        !           253:                e->bottom.y = pt[n_points-2].y;
        !           254: 
        !           255:                // adjust for multiple edges
        !           256:                if(e->chain->count > 1)
        !           257:                {
        !           258:                        int place = e->place;
        !           259:                        int width = e->chain->width;
        !           260:                        if(v == e->node)
        !           261:                        {
        !           262:                                place -= width/2;
        !           263:                                pt[2].x += place;
        !           264:                                pt[1].y -= place/2;
        !           265:                                pt[3].y += place/2;
        !           266:                        }
        !           267:                        else if(Level[v] == Level[e->node])
        !           268:                        {
        !           269:                                if(e->chain->weight > 0)
        !           270:                                        place = -place;
        !           271:                                int mx = iabs(pt[n_points/2].x - pt[0].x);
        !           272:                                for(int n = 1; n < n_points-1; ++n)
        !           273:                                {
        !           274:                                        int d = iabs(pt[n].x - pt[0].x);
        !           275:                                        d = min(d,iabs(pt[n].x - pt[n_points-1].x));
        !           276:                                        pt[n].y += (int)(place*(((double)d)/mx));
        !           277:                                }
        !           278:                        }
        !           279:                        else
        !           280:                        {
        !           281:                                place -= width/2;
        !           282:                                for(int n = 1; n < n_points-1; ++n)
        !           283:                                        pt[n].x += place;
        !           284:                        }
        !           285:                }
        !           286: 
        !           287:                e->splinept = pt;
        !           288:        }
        !           289: 
        !           290:        // so we'll remember to clean up next time around
        !           291:        Clean_up = 1;
        !           292: }
        !           293: 
        !           294: 
        !           295: // search for the root of the union tree containing this vertex
        !           296: static int findroot(int v)
        !           297: {
        !           298:        // if this is root, return it
        !           299:        if(v == Root[v])
        !           300:                return v;
        !           301:        // search for root and compress the path
        !           302:        return (Root[v] = findroot(Root[v]));
        !           303: }
        !           304: 
        !           305: // union a set of nodes
        !           306: static void setunion(int *set)
        !           307: {
        !           308:        int root = findroot(set[0]);
        !           309:        for(int i = 0; set[i] != -1; ++i)
        !           310:        {
        !           311:                int r = findroot(set[i]);
        !           312:                if(r == set[i])
        !           313:                        Root[set[i]] = root;
        !           314:                else
        !           315:                {
        !           316:                        Root[root] = r;
        !           317:                        root = r;
        !           318:                }
        !           319:        }
        !           320: }
        !           321: 
        !           322: 
        !           323: 
        !           324: // check for multiple edges
        !           325: static int multiple(int node, edge_t *edge, int isaux)
        !           326: {
        !           327:        for(int dohead = 0; dohead < 2; ++dohead)
        !           328:        {
        !           329:                /* check for forward multiple edges */
        !           330:                edge_t *e = dohead ? Outedges[edge->node] : Outedges[node];
        !           331:                int     match = dohead ? node : edge->node;
        !           332: 
        !           333:                for(; e; e = e->next)
        !           334:                if(e->node == match)
        !           335:                {
        !           336:                        e->count += 1;
        !           337:                        e->weight += edge->weight;
        !           338:                        e->width += 3*Nodesep/4 + edge->width;
        !           339: 
        !           340:                        // identify user's edge with our edge and set its order
        !           341:                        if(isaux)
        !           342:                        {
        !           343:                                edge->chain->chain = e;
        !           344:                                edge->chain->place = e->width - edge->width;
        !           345:                        }
        !           346:                        else
        !           347:                        {
        !           348:                                edge->chain = e;
        !           349:                                edge->place = e->width - edge->width;
        !           350:                        }
        !           351: 
        !           352:                        // update the corresponding version in Inedges
        !           353:                        e = e->link;
        !           354:                        e->count += 1;
        !           355:                        e->weight += edge->weight;
        !           356:                        e->width += Nodesep + edge->width;
        !           357: 
        !           358:                        return 1;
        !           359:                }
        !           360:        }
        !           361: 
        !           362:        return 0;
        !           363: } 
        !           364: 
        !           365: 
        !           366: // keep track of self and flat edges for position assignment
        !           367: static void noedge(int tail, edge_t *edge)
        !           368: {
        !           369:        if(!Noedges)
        !           370:                Noedges = new edge_t*[N_real_nodes];
        !           371: 
        !           372:        // check for multiple edge
        !           373:        for(edge_t *e = Noedges[tail]; e; e = e->next)
        !           374:                if(e->node == edge->node)
        !           375:                {
        !           376:                        e->count += 1;
        !           377:                        e->weight += edge->weight;
        !           378:                        e->width += Nodesep/2 + edge->width;
        !           379:                        edge->chain = e;
        !           380:                        edge->place = e->width - edge->width;
        !           381:                        return;
        !           382:                }
        !           383: 
        !           384:        // making a new edge
        !           385:        Noedges[tail] = new edge_t(edge->node,edge->weight,edge->width,0,Noedges[tail]);
        !           386:        edge->chain = Noedges[tail];
        !           387: }
        !           388: 
        !           389: 
        !           390: 
        !           391: // construct new edge lists ensuring no cycles, multiple edges and self edges.
        !           392: static void dfs(int node, edge_t **outedges, edge_t **auxedges,
        !           393:                 int *active, int *marked, int **sets)
        !           394: {
        !           395:        if(marked[node])
        !           396:                return;
        !           397:        marked[node] = 1;
        !           398: 
        !           399:        // mark this node as being on the search stack
        !           400:        active[node] = 1;
        !           401: 
        !           402:        for(int *set = sets[node]; *set != -1; ++set)
        !           403:        {
        !           404:                int tail = *set;
        !           405: 
        !           406:                for(int isaux = 0; isaux < 2; ++isaux)
        !           407:                {
        !           408:                        if(isaux && !auxedges)
        !           409:                                continue;
        !           410: 
        !           411:                        edge_t *e = isaux ? auxedges[tail] : outedges[tail];
        !           412:                        for(; e; e = e->next)
        !           413:                        {
        !           414:                                // there is a corresponding aux edge
        !           415:                                if(!isaux && e->chain)
        !           416:                                        continue;
        !           417: 
        !           418:                                // ignore self-edges or squashed edges
        !           419:                                if(e->node == tail || Root[e->node] == node)
        !           420:                                {
        !           421:                                        if(e->node == tail)
        !           422:                                                N_self_edges++;
        !           423:                                        else    N_flat_edges++;
        !           424:                                        noedge(tail,e);
        !           425:                                        continue;
        !           426:                                }
        !           427: 
        !           428:                                // check for multiple edges
        !           429:                                if(multiple(tail,e,isaux))
        !           430:                                {
        !           431:                                        N_repeat_edges++;
        !           432:                                        continue;
        !           433:                                }
        !           434: 
        !           435:                                // a new edge is to be constructed
        !           436:                                N_edges++;
        !           437: 
        !           438:                                // a cycle is detected, reverse the edge
        !           439:                                if(active[Root[e->node]])
        !           440:                                {
        !           441:                                        N_revert_edges++;
        !           442: 
        !           443:                                        Outedges[e->node] =
        !           444:                                                new edge_t(tail,e->weight,e->width,e->minlen,
        !           445:                                                           Outedges[e->node]);
        !           446:                                        Inedges[tail] =
        !           447:                                                new edge_t(e->node,e->weight,e->width,e->minlen,
        !           448:                                                           Inedges[tail]);
        !           449:                                        Outedges[e->node]->link = Inedges[tail];
        !           450:                                        Inedges[tail]->link = Outedges[e->node];
        !           451: 
        !           452:                                        // identify user's edge with our edge
        !           453:                                        if(isaux)
        !           454:                                        {
        !           455:                                                e->chain->chain = Outedges[e->node];
        !           456:                                                e->chain->place = 0;
        !           457:                                        }
        !           458:                                        else
        !           459:                                        {
        !           460:                                                e->chain = Outedges[e->node];
        !           461:                                                e->place = 0;
        !           462:                                        }
        !           463: 
        !           464:                                        continue;
        !           465:                                }
        !           466: 
        !           467:                                // forward or cross-edges
        !           468:                                Outedges[tail] = new edge_t(e->node,e->weight,e->width,e->minlen,
        !           469:                                                        Outedges[tail]);
        !           470:                                Inedges[e->node] = new edge_t(tail,e->weight,e->width,e->minlen,
        !           471:                                                        Inedges[e->node]);
        !           472:                                Outedges[tail]->link = Inedges[e->node];
        !           473:                                Inedges[e->node]->link = Outedges[tail];
        !           474: 
        !           475:                                // identify user's edge with our edge
        !           476:                                if(isaux)
        !           477:                                {
        !           478:                                        N_revert_edges++;
        !           479:                                        e->chain->chain = Outedges[tail];
        !           480:                                        e->chain->place = 0;
        !           481:                                }
        !           482:                                else
        !           483:                                {
        !           484:                                        e->chain = Outedges[tail];
        !           485:                                        e->place = 0;
        !           486:                                }
        !           487: 
        !           488:                                // recursion
        !           489:                                if(!marked[Root[e->node]])
        !           490:                                        dfs(Root[e->node],outedges,auxedges,
        !           491:                                            active,marked,sets);
        !           492:                        }
        !           493:                }
        !           494:        }
        !           495: 
        !           496:        // this node is now off the search stack
        !           497:        active[node] = 0;
        !           498: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.