Commit | Line | Data |
---|---|---|
6fd945b9 TL |
1 | #include <stdio.h> |
2 | # | |
3 | /* | |
4 | set REACH[v] = w if w is only node outside subtree of v which is reached from within | |
5 | subtree of v, REACH[v] = UNDEFINED otherwise | |
6 | */ | |
7 | #include "def.h" | |
8 | ||
9 | /* strategy in obtaining REACH(v) for each node v: | |
10 | Since only need to know whether there is exactly one exit from subtree of v, | |
11 | need keep track only of 2 farthest exits from each subtree rather than all exits. | |
12 | The first may be the unique exit, while the second is used when the children | |
13 | of a node has the same first exit. | |
14 | To obtain 2 farthest exits of v, look at 2 farthest exits of children of v and | |
15 | the nodes entered by arcs from v. Farthest exits are identified by numbering | |
16 | the nodes from -2 to -(accessnum-2) starting at the bottom left corner of tree | |
17 | using procedure number(). The farthest exit from the subtree of v is the one | |
18 | with the least number according NUM to this numbering. If a node w is an exit from the | |
19 | subtree of v, then NUM(w) < NUM(v). The negative numbers allow NUM(v) to be stored | |
20 | in the same location as REACH(v). REACH(w) may already be set when an arc (v,w) to a child | |
21 | is searched, but the negative numbering is consistent, i.e. NUM(v) < NUM(w) in this case | |
22 | as in other cases where w is not an exit from the subtree of v. | |
23 | */ | |
24 | ||
25 | struct pair { | |
26 | int smallest; | |
27 | int second; | |
28 | }; | |
29 | ||
30 | ||
31 | getreach() /* obtain REACH(v) for each node v */ | |
32 | { | |
33 | VERT v; | |
34 | struct pair *pr; | |
35 | for (v = 0; v < nodenum; ++v) | |
36 | REACH(v) = UNDEFINED; | |
37 | number(START); | |
38 | for (v = START; DEFINED(v); v = RSIB(v)) | |
39 | { | |
40 | pr = exits(v); /* need to free the space for pr */ | |
41 | chfree(pr,sizeof(*pr)); | |
42 | } | |
43 | } | |
44 | ||
45 | ||
46 | exits(v) /* set REACH(v) = w if w is only node outside subtree of v which is reached from within | |
47 | subtree of v, leave REACH(v) UNDEFINED otherwise */ | |
48 | VERT v; | |
49 | { | |
50 | struct pair *vpair, *chpair; | |
51 | VERT w,t; | |
52 | int i; | |
53 | vpair = challoc(sizeof(*vpair)); | |
54 | vpair ->smallest = vpair ->second = UNDEFINED; | |
55 | for (i = 0; i < CHILDNUM(v); ++i) | |
56 | { | |
57 | w = LCHILD(v,i); | |
58 | if (!DEFINED(w)) continue; | |
59 | for (t = w; DEFINED(t); t = RSIB(t)) | |
60 | { | |
61 | chpair = exits(t); | |
62 | ||
63 | /* set vpair->smallest,second to two smallest of vpair->smallest,second, | |
64 | chpair->smallest,second */ | |
65 | if (inspr(chpair->smallest,vpair)) | |
66 | inspr(chpair->second,vpair); | |
67 | chfree(chpair, sizeof(*chpair)); | |
68 | } | |
69 | } | |
70 | for (i = 0; i < ARCNUM(v); ++i) | |
71 | { | |
72 | w = ARC(v,i); | |
73 | if (!DEFINED(w)) continue; | |
74 | inspr(w,vpair); | |
75 | } | |
76 | /* throw out nodes in subtree of v */ | |
77 | if (NUM(vpair->second) >= NUM(v)) | |
78 | { | |
79 | vpair->second = UNDEFINED; | |
80 | if (NUM(vpair->smallest) >= NUM(v)) | |
81 | vpair->smallest = UNDEFINED; | |
82 | } | |
83 | if (vpair->second == UNDEFINED) | |
84 | REACH(v) = vpair->smallest; /* vpair->smallest possibly UNDEFINED */ | |
85 | else | |
86 | REACH(v) = UNDEFINED; | |
87 | return(vpair); | |
88 | } | |
89 | ||
90 | ||
91 | /* number nodes from -2 to -(accessnum+2) starting at bottom left corner of tree */ | |
92 | number(v) | |
93 | VERT v; | |
94 | { | |
95 | int i; | |
96 | VERT w; | |
97 | static int count; | |
98 | for (i = 0; i < CHILDNUM(v); ++i) | |
99 | { | |
100 | w = LCHILD(v,i); | |
101 | if (DEFINED(w)) | |
102 | number(w); | |
103 | } | |
104 | SETNUM(v,count-2); | |
105 | --count; | |
106 | if (DEFINED(RSIB(v))) | |
107 | number(RSIB(v)); | |
108 | } | |
109 | ||
110 | ||
111 | NUM(v) | |
112 | VERT v; | |
113 | { | |
114 | if (!DEFINED(v)) return(UNDEFINED); | |
115 | return(REACH(v)); | |
116 | } | |
117 | ||
118 | SETNUM(v,count) | |
119 | VERT v; int count; | |
120 | { | |
121 | /* this reuses REACH to save space; | |
122 | /* appears to be no conflict with setting true value of REACH later */ | |
123 | REACH(v) = count; | |
124 | } | |
125 | ||
126 | ||
127 | LOGICAL inspr(w,pr) /* insert w in order in pr, return TRUE if <= smaller of pr */ | |
128 | /* don't insert duplicates */ | |
129 | VERT w; | |
130 | struct pair *pr; | |
131 | { | |
132 | if (w == pr-> smallest) return(TRUE); | |
133 | if (NUM(w) < NUM(pr->smallest)) | |
134 | { | |
135 | pr->second = pr->smallest; | |
136 | pr->smallest = w; | |
137 | return(TRUE); | |
138 | } | |
139 | if (w == pr->second) return(FALSE); | |
140 | if (NUM(w) < NUM(pr->second)) | |
141 | pr->second = w; | |
142 | return(FALSE); | |
143 | } |