```   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:
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
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
33:     for (v = 0; v < nodenum; ++v)
35:     for (i = accessnum -1; i >= 0; --i)
36:         {
37:         v = after[i];
38:         for (j = 0; j < ARCNUM(v); ++j)
39:             {
42:             if (ntoaft[adj] < i)        /* back edge */
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)
50:                 }
51:             else                /* cross edge */
52:                 {
54:                 if (DEFINED(w))
56:                 }
57:             }
58:         if (NTYPE(v) == LOOPVX || NTYPE(v) == DOVX)
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 */
66:     {
67:     while (y != -1 && !ANC(y,z))
69:     return(y);
70:     }
71:
72:
73: merge(w,y,head)     /* merge chains of w and y according to ANC relation */
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;
83:         }
84:     else
85:         {
86:         t = 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;
96:             }
97:         else
98:             {
99:             min = w;
101:             }
102:         if (t != min)
103:             {
105:             t = min;
106:             }
107:         }
108:     if (w == -1)  min = y;  else  min = w;
109:     if (t != min)  head[t] = min;
110:
111:     }
```

#### Defined functions

gethead defined in line 17; used 1 times
lowanc defined in line 64; used 1 times
• in line 53
merge defined in line 73; used 3 times

#### Defined variables

sccsid defined in line 2; never used

#### Defined macros

ANC defined in line 14; used 5 times
 Last modified: 1987-02-17 Generated: 2016-12-26 Generated by src2html V0.67 page hit count: 1741