Return to dag_edge.c CVS log

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

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

1.1     ! root        1: #include       "draw_dag.h"
        !             2: 
        !             3: 
        !             4: /*
        !             5:        Turn long edges into sequences of length-1 edges
        !             6: */
        !             7: 
        !             8: void dag_unitedges()
        !             9: {
        !            10:        // compute the thickness for each level
        !            11:        Levelheight = new int[Maxlevel+1];
        !            12:        for(int v = 0; v < N_real_nodes; ++v)
        !            13:                if(Height[v] > Levelheight[Level[v]])
        !            14:                        Levelheight[Level[v]] = Height[v];
        !            15: 
        !            16:        // count the number of new edges, and nodes
        !            17:        int n_dummies = 0;
        !            18:        for(v = 0; v < N_real_nodes; v++)
        !            19:        for(edge_t *e = Outedges[v]; e; e = e->next)
        !            20:        {
        !            21:                if(Level[e->node] <= Level[v])
        !            22:                        panic("Bad level assignment");
        !            23:                n_dummies += (Level[e->node] - Level[v]) - 1;
        !            24:        }
        !            25: 
        !            26:        // reset N_nodes
        !            27:        N_nodes += n_dummies;
        !            28: 
        !            29: #ifndef TIMING
        !            30:        if(Verbose)
        !            31:                fprintf(stderr,"Dummy nodes = %d\n",n_dummies);
        !            32: #endif
        !            33: 
        !            34:        // get more space for Level[], Outedges[] and Inedges[]
        !            35:        Width = (int *) realloc((char *)Width,N_nodes*sizeof(Width[0]));
        !            36:        Height = (int *) realloc((char *)Height,N_nodes*sizeof(Height[0]));
        !            37:        Level = (int *) realloc((char *)Level,N_nodes*sizeof(Level[0]));
        !            38:        Inedges = (edge_t **) realloc((char *)Inedges,N_nodes*sizeof(Inedges[0]));
        !            39:        Outedges = (edge_t **) realloc((char *)Outedges,N_nodes*sizeof(Outedges[0]));
        !            40:        if(!Width || !Height || !Level || !Inedges || !Outedges)
        !            41:                panic("out of memory");
        !            42:        for(v = N_real_nodes; v < N_nodes; v++)
        !            43:        {
        !            44:                Inedges[v] = Outedges[v] = (edge_t *)(NULL);
        !            45:                Level[v] = Width[v] = Height[v] = 0;
        !            46:        }
        !            47: 
        !            48:        // create new dummy nodes and edges
        !            49:        int dummy = N_real_nodes;
        !            50:        for(v = 0; v < N_real_nodes; v++)
        !            51:        for(e = Outedges[v]; e; e = e->next)
        !            52:        {
        !            53:                if(Level[v]+1 == Level[e->node])
        !            54:                        continue;
        !            55: 
        !            56:                // attributes of new edges
        !            57:                int     node = e->node;
        !            58:                int     weight = e->weight;
        !            59:                int     count = e->count;
        !            60:                int     width = e->width;
        !            61: 
        !            62:                // delete corresponding Inedge 
        !            63:                edge_t *lastf = (edge_t*)0;
        !            64:                for(edge_t *f = Inedges[node]; f; lastf = f, f = f->next)
        !            65:                        if(f->node == v)
        !            66:                                break;
        !            67:                if(lastf)
        !            68:                        lastf->next = f->next;
        !            69:                else    Inedges[node] = f->next;
        !            70: 
        !            71:                // make these edges short
        !            72:                f->next = NULL;
        !            73:                Inedges[dummy] = f;
        !            74:                e->node = dummy++;
        !            75: 
        !            76:                // make the rest of the short edges
        !            77:                int     lev = Level[v]+1;
        !            78:                int     maxlev = Level[node];
        !            79:                int     tail = e->node;
        !            80:                int     head = lev == maxlev-1 ? node : dummy++;
        !            81:                edge_t  *ochain = e, *ichain = f;
        !            82:                while(lev < maxlev)
        !            83:                {
        !            84:                        Level[tail] = lev;
        !            85:                        Width[tail] = width;
        !            86:                        Height[tail] = Levelheight[lev];
        !            87: 
        !            88:                        N_edges++;
        !            89:                        Outedges[tail] =
        !            90:                                new edge_t(head,weight,width,1,Outedges[tail]);
        !            91:                        Outedges[tail]->count = count;
        !            92:                        Inedges[head] =
        !            93:                                new edge_t(tail,weight,width,1,Inedges[head]);
        !            94:                        Inedges[head]->count = count;
        !            95:                        Outedges[tail]->link = Inedges[head];
        !            96:                        Inedges[head]->link = Outedges[tail];
        !            97: 
        !            98:                        // chain the broken edges
        !            99:                        ochain->chain = Outedges[tail];
        !           100:                        Inedges[head]->chain = ichain;
        !           101:                        ochain = Outedges[tail];
        !           102:                        ichain = Inedges[head];
        !           103: 
        !           104:                        if(++lev < maxlev)
        !           105:                        {
        !           106:                                tail = head;
        !           107:                                head = lev == maxlev-1 ? node : dummy++;
        !           108:                        }
        !           109:                }
        !           110:        }
        !           111: }
        !           112: 
        !           113: 
        !           114: #ifdef DEBUG
        !           115: static void d_chk_level()
        !           116: {
        !           117:        for(int i = 0; i < N_nodes; ++i)
        !           118:                if(Level[i] > Maxlevel || Level[i] < 0)
        !           119:                        (void) abort();
        !           120: }
        !           121: #endif

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