Complexity Classes - Models of Computation: Exploring the Power of Computing - page 345

COUNTING - REACHABILITY ( u )
{ R ( k , u ) = number of vertices at distance ≤ k from u in G =( V , E ) }

prev num dist := 1; { num dist = R ( 0, u ) }

for dist := 1 to n 1

num dist := #- VERTICES - AT -

−

≤ - DIST - FROM - u ( dist , u , prev num dist )

prev num dist := num dist
{ num dist = R ( dist , u ) }

return ( num dist )

≤

- DISTANCE - FROM - u ( dist , u , prev num dist ) #- VERTICES - AT -

{

Returns R ( dist , u ) given prev num dist = R ( dist

−

1, u ) or fails

}

num nodes := 0
for last node := 1 to n
if IS - NODE - AT -

- DIST - FROM - u ( dist , u , last node , prev num dist ) then
num nodes := num nodes + 1
return ( num nodes )

≤

≤

- DIST - FROM - u ( dist , u , last node , prev num dist )

IS - NODE - AT -

{ num node = number of vertices at distance ≤ dist from u found so far }

num node := 0;
reply := false
for next to last node := 1 to n
if EXISTS - PATH - FROM - u - TO - v - ≤ - LENGTH ( u , next to last node , dist − 1 ) then

num node := num node + 1 { count number of next-to-last nodes or fail }

if ADJACENT - OR - IDENTICAL ( next to last node , last node ) then
reply := true
if num node < prev num dist then
fail
else return ( reply )

EXISTS - PATH - FROM - u - TO - v -

≤

- LENGTH ( u , v , dist )

{

nondeterministically choose at most dist vertices, fail if they don't form a path

}

node 1:= u
for count := 1 to dist
node 2:= NONDETERMINISTIC - GUESS ([ 1, .. , n ])
if not ADJACENT - OR - IDENTICAL ( node 1, node 2 ) then
fail
else node 1:= node 2
if node 2= v then
return ( true )
else
return ( false )

Figure 8.9 A nondeterministic program counting vertices reachable from u . Comments are
enclosed in braces

{ }

, .