BSD 4_3_Reno release

[unix-history] / usr / src / pgrm / struct / struct / 2.head.c

#ifndef lint
static char sccsid[] = "@(#)2.head.c    4.1     (Berkeley)      2/11/83";
#endif not lint

#include <stdio.h>
#
/*
set head[v] to ITERVX heading smallest loop containing v, for each v
*/
#include "def.h"
#include "2.def.h"

/* define ANC(v,w) true if v == w or v is ancestor of w */
#define ANC(v,w)        (ntobef[v] <= ntobef[w] && ntoaft[v] <= ntoaft[w])      /* reflexive ancestor */


gethead(head)
VERT *head;
       {
       VERT v, w, adj; int i, j;
       /* search nodes in reverse of after numbering so that all paths from
               a node to an ancestor are searched before the node */
       /* at any point, the current value of head allows chains of nodes
               to be reached from any node v by taking head[v], head[head[v]], etc.
               until an UNDEFINED value is reached.  Upon searching each arc, 
               the appropriate chains must be merged to avoid losing information.
               For example, from one path out of a node v it may be known that
                v is in a loop headed by z, while from another
               it may be known that v is in a loop headed by w.
               Thus, head[v] must be set to whichever of z,w is the closer ancestor,
               and the fact that this node is in a loop headed by the other must be
               recorded in head.       */
       for (v = 0; v < nodenum; ++v)
               head[v] = UNDEFINED;
       for (i = accessnum -1; i >= 0; --i)
               {
               v = after[i];
               for (j = 0; j < ARCNUM(v); ++j)
                       {
                       adj = ARC(v,j);
                       if (!DEFINED(adj)) continue;
                       if (ntoaft[adj] < i)            /* back edge */
                               merge(v,adj,head);
                       else if (ANC(v,adj))            /* not back edge or cross edge */
                               {
                               /* need to do only tree edges - must not do edge (v,adj)
                                       when head[adj] is not ANC of v */
                               if (DEFINED(head[adj]) && ANC(head[adj],v))
                                       merge(v,head[adj],head);
                               }
                       else                            /* cross edge */
                               {
                               w = lowanc(adj,v,head);
                               if (DEFINED(w))
                                       merge(w,v,head);
                               }
                       }
               if (NTYPE(v) == LOOPVX || NTYPE(v) == DOVX)
                       head[ARC(v,0)] = head[v];       /* head of ITERVX must be different ITERVX */
               }
       }


lowanc(y,z,head)                /* find the first node in chain of y which is anc of z, if it exists */
VERT y,z, *head;
       {
       while (y != -1 && !ANC(y,z))
               y = head[y];
       return(y);
       }


merge(w,y,head)         /* merge chains of w and y according to ANC relation */
VERT w,y, *head;
       {
       VERT t, min;
       if (w == y) return;

       if (ANC(w,y))           /* set t to min of w,y */
               {
               t = y;
                y = head[y];
               }
       else
               {
               t = w;
                w = head[w];
               }

       while (w != -1 && y != -1)              /* construct chain at t by adding min of remaining elts */
               {
               if (ANC(w,y))
                       {
                       min = y;
                       y = head[y];
                       }
               else
                       {
                       min = w;
                       w = head[w];
                       }
               if (t != min)
                       {
                       head[t] = min;
                       t = min;
                       }
               }
       if (w == -1)  min = y;  else  min = w;
       if (t != min)  head[t] = min;

       }