set REACH[v] = w if w is only node outside subtree of v which is reached from within
subtree of v, REACH[v] = UNDEFINED otherwise
/* strategy in obtaining REACH(v) for each node v:
Since only need to know whether there is exactly one exit from subtree of v,
need keep track only of 2 farthest exits from each subtree rather than all exits.
The first may be the unique exit, while the second is used when the children
of a node has the same first exit.
To obtain 2 farthest exits of v, look at 2 farthest exits of children of v and
the nodes entered by arcs from v. Farthest exits are identified by numbering
the nodes from -2 to -(accessnum-2) starting at the bottom left corner of tree
using procedure number(). The farthest exit from the subtree of v is the one
with the least number according NUM to this numbering. If a node w is an exit from the
subtree of v, then NUM(w) < NUM(v). The negative numbers allow NUM(v) to be stored
in the same location as REACH(v). REACH(w) may already be set when an arc (v,w) to a child
is searched, but the negative numbering is consistent, i.e. NUM(v) < NUM(w) in this case
as in other cases where w is not an exit from the subtree of v.
getreach() /* obtain REACH(v) for each node v */
for (v
= 0; v
< nodenum
; ++v
)
for (v
= START
; DEFINED(v
); v
= RSIB(v
))
pr
= exits(v
); /* need to free the space for pr */
exits(v
) /* set REACH(v) = w if w is only node outside subtree of v which is reached from within
subtree of v, leave REACH(v) UNDEFINED otherwise */
struct pair
*vpair
, *chpair
;
vpair
= challoc(sizeof(*vpair
));
vpair
->smallest
= vpair
->second
= UNDEFINED
;
for (i
= 0; i
< CHILDNUM(v
); ++i
)
if (!DEFINED(w
)) continue;
for (t
= w
; DEFINED(t
); t
= RSIB(t
))
/* set vpair->smallest,second to two smallest of vpair->smallest,second,
chpair->smallest,second */
if (inspr(chpair
->smallest
,vpair
))
inspr(chpair
->second
,vpair
);
chfree(chpair
, sizeof(*chpair
));
for (i
= 0; i
< ARCNUM(v
); ++i
)
if (!DEFINED(w
)) continue;
/* throw out nodes in subtree of v */
if (NUM(vpair
->second
) >= NUM(v
))
vpair
->second
= UNDEFINED
;
if (NUM(vpair
->smallest
) >= NUM(v
))
vpair
->smallest
= UNDEFINED
;
if (vpair
->second
== UNDEFINED
)
REACH(v
) = vpair
->smallest
; /* vpair->smallest possibly UNDEFINED */
/* number nodes from -2 to -(accessnum+2) starting at bottom left corner of tree */
for (i
= 0; i
< CHILDNUM(v
); ++i
)
if (!DEFINED(v
)) return(UNDEFINED
);
/* this reuses REACH to save space;
/* appears to be no conflict with setting true value of REACH later */
LOGICAL
inspr(w
,pr
) /* insert w in order in pr, return TRUE if <= smaller of pr */
/* don't insert duplicates */
if (w
== pr
-> smallest
) return(TRUE
);
if (NUM(w
) < NUM(pr
->smallest
))
pr
->second
= pr
->smallest
;
if (w
== pr
->second
) return(FALSE
);
if (NUM(w
) < NUM(pr
->second
))