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

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.