Return to dag_stem.c CVS log

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

Annotation of researchv10no/cmd/dag/dag_stem.c, revision 1.1.1.1

1.1       root        1: #include       "draw_dag.h"
                      2: 
                      3: 
                      4: // Merge all stems from the same node into a single one
                      5: // The width of the remaining node is appropriately widened while
                      6: // its height should be largest of the whole bunch.
                      7: 
                      8: void dag_delstem()
                      9: {
                     10:        Istems = new edge_t*[N_real_nodes];
                     11:        Ostems = new edge_t*[N_real_nodes];
                     12:        Stems = new int[N_real_nodes];
                     13: 
                     14:        int n_remove = 0;
                     15:        int n_retain = 0;
                     16:        for(int in = 0; in < 2; ++in)
                     17:        {
                     18:                edge_t **these = in ? Inedges : Outedges;
                     19:                edge_t **those = in ? Outedges : Inedges;
                     20:                edge_t **edges = in ? Istems : Ostems;
                     21:                for(int v = 0; v < N_real_nodes; ++v)
                     22:                {
                     23:                        // remove all stems from the edge list
                     24:                        edge_t *e, *elast, *stem;
                     25:                        edges[v] = NULL;
                     26:                        elast = NULL;
                     27:                        stem = NULL;
                     28:                        for(e = these[v]; e; e = elast ? elast->next : these[v])
                     29:                        {
                     30:                                if(these[e->node] || those[e->node]->next)
                     31:                                        elast = e;
                     32:                                else if(!stem)
                     33:                                {
                     34:                                        stem = e;
                     35:                                        elast = e;
                     36:                                        n_retain++;
                     37:                                }
                     38:                                else
                     39:                                {
                     40:                                        if(elast)
                     41:                                                elast->next = e->next;
                     42:                                        else    these[v] = e->next;
                     43:                                        e->next = edges[v];
                     44:                                        edges[v] = e;
                     45:                                        n_remove++;
                     46:                                }
                     47:                        }
                     48: 
                     49:                        if(edges[v])
                     50:                        {
                     51:                                // merge edges
                     52:                                int w = stem->node;
                     53:                                for(e = edges[v]; e; e = e->next)
                     54:                                {
                     55:                                        stem->count += e->count;
                     56:                                        stem->weight += e->weight;
                     57:                                        those[e->node] = NULL;
                     58:                                        Stems[e->node] = 1;
                     59:                                }
                     60:                                stem->link->count = stem->count;
                     61:                                stem->link->weight = stem->weight;
                     62:                                edges[v]->chain = stem;
                     63:                        }
                     64:                }
                     65:        }
                     66: }
                     67: 
                     68: 
                     69: // reinsert the stems
                     70: void dag_insstem()
                     71: {
                     72:        for(int down = 0; down < 2; ++down)
                     73:        {
                     74:                edge_t **edges = down ? Ostems : Istems;
                     75:                edge_t **these = down ? Outedges : Inedges;
                     76:                edge_t **those = down ? Inedges : Outedges;
                     77:                for(int v = 0; v < N_real_nodes; ++v)
                     78:                {
                     79:                        if(!edges[v])
                     80:                                continue;
                     81: 
                     82:                        // our representative
                     83:                        edge_t *stem = edges[v]->chain;
                     84:                        edges[v]->chain = NULL;
                     85: 
                     86:                        // number of friends
                     87:                        int n_edges = 0;
                     88:                        for(edge_t *e = edges[v]; e; e = e->next)
                     89:                                n_edges += 1;
                     90: 
                     91:                        // insert the nodes in the rank listing
                     92:                        int w = stem->node;
                     93:                        int *rank = Rank[Level[w]];
                     94:                        for(int n_rank = 0; rank[n_rank] != -1; ++n_rank)
                     95:                                ;
                     96:                        rank[n_rank+n_edges] = -1;
                     97:                        int pos = Invert[stem->node];
                     98:                        for(int i = n_rank+n_edges-1; i > pos+n_edges; --i)
                     99:                        {
                    100:                                rank[i] = rank[i-n_edges];
                    101:                                Invert[rank[i]] = i;
                    102:                        }
                    103: 
                    104:                        edge_t *elast;
                    105:                        for(e = edges[v], i = pos+1; e; i++, elast = e, e = e->next)
                    106:                        {
                    107:                                int n = e->node;
                    108:                                those[n] = e->link;
                    109:                                stem->count -= e->count;
                    110:                                stem->weight -= e->weight;
                    111:                                Component[n] = Component[w];
                    112:                                rank[i] = n;
                    113:                                Invert[n] = i;
                    114:                        }
                    115:                        stem->link->count = stem->count;
                    116:                        stem->link->weight = stem->weight;
                    117: 
                    118:                        // put these edges back in the proper edge list
                    119:                        elast->next = these[v];
                    120:                        these[v] = edges[v];
                    121:                        edges[v] = NULL;
                    122:                }
                    123:        }
                    124: }

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