View article

Consider the following depth-first-search program for computing the predicate" there is a path from node x to node y" in a finite out-regular binary graph: funct ispath=(node x, node y) bool: I-(var set n, vat sequence s):=(emptyset, append (emptysequence, x)); while-a isempty (s) do node v= top (s); if contains (n, v) then s:= rest (s) else (n, s):=(add (n, v), append (append (rest (s), left (v)), right (v))) fi od; contains (n, y) _1