#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; }