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     ! 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.