![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to 2.dfs.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 40BSD / cmd / struct|
Return to 2.dfs.c CVS log | Up to [CSRG BSD Unix] / 40BSD / cmd / struct |
1.1 root 1: #include <stdio.h>
2: #
3: /* depth-first search used to identify back edges, unreachable nodes;
4: each node v entered by back edge replaced by
5: LOOPVX ->ITERVX -> v,
6: so that back edges entering v now enter the ITERVX,
7: and other edges entering v now enter the LOOPVX.
8: Nodes are numbered according to depth-first search:
9: before numbering- ntobef[v] = i => node numbered v is i'th
10: node in order of first visit during the search;
11: after numbering- ntoaft[v] = i => node numbered v is i'th
12: node visited in order of last visit during the search.
13: Also, in this case after[i] = v.
14: */
15:
16: #include "def.h"
17: #include "2.def.h"
18:
19: #define MAXINS 3 /* spacing needed between numbers generated during depth first search */
20:
21: int *status;
22: int befcount, aftcount;
23: /* following defines used to mark back edges and nodes entered by back edges */
24: #define UNPROCESSED 0
25: #define STACKED 1
26: #define FINISHED 2
27: #define MARK(v) {REACH(v) = 1; } /* mark node v */
28: #define UNMARK(v) {REACH(v) = 0; }
29: #define MARKED(v) (REACH(v))
30: #define MKEDGE(e) {if (e >= -1) e = -(e+3); } /* mark edge e */
31: #define UNMKEDGE(e) {if (e < -1) e = -(e+3); }
32: #define BACKEDGE(e) (e < -1)
33:
34:
35: dfs(v) /* depth first search */
36: VERT v;
37: {
38: int i; VERT w;
39: accessnum = 0;
40: status = challoc(sizeof(*status) * nodenum);
41: for (w = 0; w < nodenum; ++w)
42: {
43: status[w] = UNPROCESSED;
44: UNMARK(w);
45: }
46: search(v);
47: chreach();
48: chfree(status, sizeof(*status) * nodenum);
49: addloop();
50: after = challoc(sizeof(*after) * accessnum);
51: for (i = 0; i < accessnum; ++i)
52: after[i] = UNDEFINED;
53: ntoaft = challoc(sizeof(*ntoaft) * nodenum);
54: ntobef = challoc(sizeof(*ntobef) * nodenum);
55: for (w = 0; w < nodenum; ++w)
56: ntobef[w] = ntoaft[w] = UNDEFINED;
57: befcount = 0;
58: aftcount = 0;
59: repsearch(v);
60: }
61:
62:
63: search(v)
64: /* using depth first search, mark back edges using MKEDGE, and nodes entered by back
65: edges using MARK */
66: VERT v;
67: {
68: VERT adj; int i;
69: status[v] = STACKED;
70: for(i = 0; i < ARCNUM(v); ++i)
71: {
72: adj = ARC(v,i);
73: if (!DEFINED(adj)) continue;
74: else if (status[adj] == UNPROCESSED)
75: search(adj);
76: else if (status[adj] == STACKED)
77: {
78: MARK(adj); /* mark adj as entered by back edge */
79: MKEDGE(ARC(v,i)); /* mark edge ARC(v,i) as being back edge */
80: }
81: }
82: status[v] = FINISHED;
83: ++accessnum;
84: }
85:
86: chreach() /* look for unreachable nodes */
87: {
88: VERT v;
89: LOGICAL unreach;
90: unreach = FALSE;
91: for (v = 0; v < nodenum; ++v)
92: if (status[v] == UNPROCESSED && NTYPE(v) != FMTVX
93: && NTYPE(v) != STOPVX && NTYPE(v) != RETVX)
94: {
95: unreach = TRUE;
96: if (debug)
97: fprintf(stderr,"node %d unreachable\n",v);
98: }
99: if (unreach)
100: error(": unreachable statements - ","will be ignored","");
101: }
102:
103:
104: addloop() /* add LOOPVX, ITERVX at nodes entered by back edges, and adjust edges */
105: {
106: VERT v, adj;
107: int j, oldnum;
108: for (v = 0, oldnum = nodenum; v < oldnum; ++v) /* insloop increases nodenum */
109: if (MARKED(v))
110: {
111: UNMARK(v); /* remove mark indicating v entered by back edge */
112: if (NTYPE(v) != ITERVX) /* DO loops already have ITERVX */
113: insloop(v); /* add LOOPVX, ITERVX since v entered by back edge*/
114: }
115: /* arcs which used to enter v now enter LOOPVX; must make back edges enter ITERVX */
116: for (v = 0; v < nodenum; ++v)
117: for (j = 0; j < ARCNUM(v); ++j)
118: {
119: if (BACKEDGE(ARC(v,j)))
120: {
121: UNMKEDGE(ARC(v,j)); /* return edge to normal value */
122: adj = ARC(v,j);
123: if (NTYPE(adj) == ITERVX) continue;
124: ASSERT(NTYPE(adj) == LOOPVX,addloop);
125: ARC(v,j) = ARC(adj,0); /* change arc to point to ITERVX */
126: ASSERT(NTYPE(ARC(v,j)) == ITERVX,addloop);
127: }
128: }
129: }
130:
131: insloop(v) /* insert LOOPVX, ITERVX at node number v */
132: VERT v;
133: {
134: VERT loo, iter;
135: loo = create(LOOPVX, 1);
136: iter = create(ITERVX,1);
137: accessnum += 2;
138: /* want LOOPVX to take on node number v, so that arcs other than back arcs
139: entering v will enter the LOOPVX automatically */
140: exchange(&graph[v], &graph[loo]);
141: exchange(&v, &loo);
142: ARC(loo,0) = iter;
143: ARC(iter,0) = v;
144: FATH(iter) = UNDEFINED; /* will be defined later along with FATH for DOVX */
145: }
146:
147: exchange(p1,p2) /* exchange values of p1,p2 */
148: int *p1,*p2;
149: {
150: int temp;
151: temp = *p1;
152: *p1 = *p2;
153: *p2 = temp;
154: }
155:
156:
157: repsearch(v) /* repeat df search in order to fill in after, ntoaft, ntobef tables */
158: VERT v;
159: {
160: VERT adj; int i,temp;
161: ntobef[v] = befcount;
162: ++befcount;
163: for(i = 0; i < ARCNUM(v); ++i)
164: {
165: adj = ARC(v,i);
166: if (DEFINED(adj) && ntobef[adj] == UNDEFINED)
167: repsearch(adj);
168: }
169: ++aftcount;
170: temp = accessnum - aftcount;
171: after[temp] = v;
172: ntoaft[v] = temp;
173: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.