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