Return to 2.head.c CVS log

Up to [CSRG BSD Unix] / 43BSD / usr.bin / struct

Annotation of 43BSD/usr.bin/struct/2.head.c, revision 1.1

1.1     ! root        1: #ifndef lint
        !             2: static char sccsid[] = "@(#)2.head.c   4.1     (Berkeley)      2/11/83";
        !             3: #endif not lint
        !             4: 
        !             5: #include <stdio.h>
        !             6: #
        !             7: /*
        !             8: set head[v] to ITERVX heading smallest loop containing v, for each v
        !             9: */
        !            10: #include "def.h"
        !            11: #include "2.def.h"
        !            12: 
        !            13: /* define ANC(v,w) true if v == w or v is ancestor of w */
        !            14: #define ANC(v,w)       (ntobef[v] <= ntobef[w] && ntoaft[v] <= ntoaft[w])      /* reflexive ancestor */
        !            15: 
        !            16: 
        !            17: gethead(head)
        !            18: VERT *head;
        !            19:        {
        !            20:        VERT v, w, adj; int i, j;
        !            21:        /* search nodes in reverse of after numbering so that all paths from
        !            22:                a node to an ancestor are searched before the node */
        !            23:        /* at any point, the current value of head allows chains of nodes
        !            24:                to be reached from any node v by taking head[v], head[head[v]], etc.
        !            25:                until an UNDEFINED value is reached.  Upon searching each arc, 
        !            26:                the appropriate chains must be merged to avoid losing information.
        !            27:                For example, from one path out of a node v it may be known that
        !            28:                 v is in a loop headed by z, while from another
        !            29:                it may be known that v is in a loop headed by w.
        !            30:                Thus, head[v] must be set to whichever of z,w is the closer ancestor,
        !            31:                and the fact that this node is in a loop headed by the other must be
        !            32:                recorded in head.       */
        !            33:        for (v = 0; v < nodenum; ++v)
        !            34:                head[v] = UNDEFINED;
        !            35:        for (i = accessnum -1; i >= 0; --i)
        !            36:                {
        !            37:                v = after[i];
        !            38:                for (j = 0; j < ARCNUM(v); ++j)
        !            39:                        {
        !            40:                        adj = ARC(v,j);
        !            41:                        if (!DEFINED(adj)) continue;
        !            42:                        if (ntoaft[adj] < i)            /* back edge */
        !            43:                                merge(v,adj,head);
        !            44:                        else if (ANC(v,adj))            /* not back edge or cross edge */
        !            45:                                {
        !            46:                                /* need to do only tree edges - must not do edge (v,adj)
        !            47:                                        when head[adj] is not ANC of v */
        !            48:                                if (DEFINED(head[adj]) && ANC(head[adj],v))
        !            49:                                        merge(v,head[adj],head);
        !            50:                                }
        !            51:                        else                            /* cross edge */
        !            52:                                {
        !            53:                                w = lowanc(adj,v,head);
        !            54:                                if (DEFINED(w))
        !            55:                                        merge(w,v,head);
        !            56:                                }
        !            57:                        }
        !            58:                if (NTYPE(v) == LOOPVX || NTYPE(v) == DOVX)
        !            59:                        head[ARC(v,0)] = head[v];       /* head of ITERVX must be different ITERVX */
        !            60:                }
        !            61:        }
        !            62: 
        !            63: 
        !            64: lowanc(y,z,head)               /* find the first node in chain of y which is anc of z, if it exists */
        !            65: VERT y,z, *head;
        !            66:        {
        !            67:        while (y != -1 && !ANC(y,z))
        !            68:                y = head[y];
        !            69:        return(y);
        !            70:        }
        !            71: 
        !            72: 
        !            73: merge(w,y,head)                /* merge chains of w and y according to ANC relation */
        !            74: VERT w,y, *head;
        !            75:        {
        !            76:        VERT t, min;
        !            77:        if (w == y) return;
        !            78: 
        !            79:        if (ANC(w,y))           /* set t to min of w,y */
        !            80:                {
        !            81:                t = y;
        !            82:                 y = head[y];
        !            83:                }
        !            84:        else
        !            85:                {
        !            86:                t = w;
        !            87:                 w = head[w];
        !            88:                }
        !            89: 
        !            90:        while (w != -1 && y != -1)              /* construct chain at t by adding min of remaining elts */
        !            91:                {
        !            92:                if (ANC(w,y))
        !            93:                        {
        !            94:                        min = y;
        !            95:                        y = head[y];
        !            96:                        }
        !            97:                else
        !            98:                        {
        !            99:                        min = w;
        !           100:                        w = head[w];
        !           101:                        }
        !           102:                if (t != min)
        !           103:                        {
        !           104:                        head[t] = min;
        !           105:                        t = min;
        !           106:                        }
        !           107:                }
        !           108:        if (w == -1)  min = y;  else  min = w;
        !           109:        if (t != min)  head[t] = min;
        !           110: 
        !           111:        }

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