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