S[x=2](k) ... Set of nodes that are reachable from x in k or less steps. The considered graph is 1->(2)->3->4 (starting x=2) x-(k-1)->v-(1)->y ? 1) 2) 3) 4) u[curr] x-(k-1)->v goodPath u[curr]=v G(v,y) x=2 C[prev]=|S(0)|=1 k=1 C[curr]=|S(1)|=0 y=1 el S[x=2](1) ? san_count=0 reply=F v=1 goodPath=T u[curr]=2 2-0->1 T (2=1)=F v=2 goodPath=T u[curr]=2 2-0->2 T (2=2)=T san_count+=1 G(2,1)=F v=3 goodPath=T u[curr]=2 2-0->3 T (2=3)=F v=4 goodPath=T u[curr]=2 2-0->4 T (2=4)=F 1<1 : return F is not element ! y=2 el S[x=2](1) ? san_count=0 reply=F v=1 goodPath=T u[curr]=2 2-0->1 T (2=1)=F v=2 goodPath=T u[curr]=2 2-0->2 T (2=2)=T san_count+=1 G(2,2)=T reply=T v=3 goodPath=T u[curr]=2 2-0->3 T (2=3)=F v=4 goodPath=T u[curr]=2 2-0->4 T (2=4)=F 1<1 : return T isElement() -> C[curr]=|S(1)|=1 y=3 el S[x=2](1) ? san_count=0 reply=F v=1 goodPath=T u[curr]=2 2-0->1 T (2=1)=F v=2 goodPath=T u[curr]=2 2-0->2 T (2=2)=T san_count+=1 G(2,3)=T reply=T v=3 goodPath=T u[curr]=2 2-0->3 T (2=3)=F v=4 goodPath=T u[curr]=2 2-0->4 T (2=4)=F 1<1 : return T isElement() -> C[curr]=|S(1)|=2 y=4 el S[x=2](1) ? -- works similar to k=1,y=1 C[prev]=2 -- this is correct because S[x=2](1)={2,3} -- up to here everything was deterministic -> the only case where C[curr]=|S(1)| is incremented iff reply equals true, i.e. u[curr]=v and G(v,y) k=2 C[curr]=|S(2)|=0 y=1 el S[x=2](2) ? san_count=0 reply=F v=1 goodPath=T u[curr]=2 p=1 /1 (not G(2,1))=T 2-1->1 F / 2 (not G(2,2))=F 2-1->1 (2=1)=F guess \ 3 (not G(2,3))=F 2-1->1 (3=1)=F \4 (not G(2,4))=T 2-1->1 F v=2 goodPath=T u[curr]=2 p=1 1 (not G(2,1))=T 2-1->2 F 2 (not G(2,2))=F 2-1->2 (2=2)=T san_count+=1 G(2,1)=F 3 (not G(2,3))=F 2-1->2 (3=2)=F 4 (not G(2,4))=T 2-1->2 F v=3 goodPath=T u[curr]=2 p=1 1 (not G(2,1))=T 2-1->3 F 2 (not G(2,2))=F 2-1->3 (2=3)=F 3 (not G(2,3))=F 2-1->3 (3=3)=T san_count+=1 G(3,1)=F 4 (not G(2,4))=T 2-1->3 F v=4 goodPath=T u[curr]=2 p=1 1 (not G(2,1))=T 2-1->4 F 2 (not G(2,2))=F 2-1->4 (2=4)=F 3 (not G(2,3))=F 2-1->4 (3=4)=F 4 (not G(2,4))=T 2-1->4 F if san_count < 2 then abort else return reply (=F) y=2 el S[x=2](2) ? san_count=0 reply=F v=1 goodPath=T u[curr]=2 p=1 -- exactly the same as above (k=2, y=1, v=1) v=2 goodPath=T u[curr]=2 p=1 1 (not G(2,1))=T 2-1->2 F 2 (not G(2,2))=F 2-1->2 (2=2)=T san_count+=1 G(2,2)=T reply=T 3 (not G(2,3))=F 2-1->2 (3=2)=F 4 (not G(2,4))=T 2-1->2 F v=3 goodPath=T u[curr]=2 p=1 1 (not G(2,1))=T 2-1->3 F 2 (not G(2,2))=F 2-1->3 (2=3)=F 3 (not G(2,3))=F 2-1->3 (3=3)=T san_count+=1 G(3,2)=F 4 (not G(2,4))=T 2-1->3 F v=4 goodPath=T u[curr]=2 p=1 -- exactly the same as above (k=2, y=1, v=4) if san_count < 2 then abort else return reply (=T) -- the only positive result (reply=true), is 2-2->2. isElement() -> C[curr]=|S(2)|=1 -- for the only case y=3 el S[x=2](2) ? san_count=0 reply=F v=1 goodPath=T u[curr]=2 p=1 -- exactly the same as above (k=2, y=1, v=1) v=2 goodPath=T u[curr]=2 p=1 1 (not G(2,1))=T 2-1->2 F 2 (not G(2,2))=F 2-1->2 (2=2)=T san_count+=1 G(2,3)=T reply=T 3 (not G(2,3))=F 2-1->2 (3=2)=F 4 (not G(2,4))=T 2-1->2 F v=3 goodPath=T u[curr]=2 p=1 1 (not G(2,1))=T 2-1->3 F 2 (not G(2,2))=F 2-1->3 (2=3)=F 3 (not G(2,3))=F 2-1->3 (3=3)=T san_count+=1 G(3,3)=T reply=T 4 (not G(2,4))=T 2-1->3 F v=4 goodPath=T u[curr]=2 p=1 -- exactly the same as above (k=2, y=1, v=4) if san_count < 2 then abort else return reply (=T) isElement() -> C[curr]=|S(2)|=2 y=4 el S[x=2](2) ? san_count=0 reply=F v=1 goodPath=T u[curr]=2 p=1 -- exactly the same as above (k=2, y=1, v=1) v=2 goodPath=T u[curr]=2 p=1 1 (not G(2,1))=T 2-1->2 F 2 (not G(2,2))=F 2-1->2 (2=2)=T san_count+=1 G(2,4)=F 3 (not G(2,3))=F 2-1->2 (3=2)=F 4 (not G(2,4))=T 2-1->2 F v=3 goodPath=T u[curr]=2 p=1 1 (not G(2,1))=T 2-1->3 F 2 (not G(2,2))=F 2-1->3 (2=3)=F 3 (not G(2,3))=F 2-1->3 (3=3)=T san_count+=1 G(3,4)=T reply=T 4 (not G(2,4))=T 2-1->3 F v=4 goodPath=T u[curr]=2 p=1 -- exactly the same as above (k=2, y=1, v=4) if san_count < 2 then abort else return reply (=T) -- the only positive result for 2-2->4 (reply=true), is from 2 to 3 to 4. isElement() -> C[curr]=|S(2)|=3 -- for the only case of y=3 C[prev]=3 -- this is correct because S[x=2](2)={2,3,4} k=3 C[curr]=|S(3)|=0 y=1 el S[x=2](3) ? san_count=0 reply=F v=1 goodPath=T u[curr]=2 p=1 1 (not G(2,1))=T 2-1->1 F (1=1)=T p=2 1 (not G(1,1))=T 2-1->1 F 2 (not G(1,2))=F 2-1->1 (2=1)=F 3 (not G(1,3))=F 2-1->1 (3=1)=F 4 (not G(1,4))=T 2-1->1 F 2 (not G(2,2))=F 2-1->1 (2=1)=F p=2 1 (not G(2,1))=T 2-1->1 F 2 (not G(2,2))=F 2-1->1 (2=1)=F 3 (not G(2,3))=F 2-1->1 (3=1)=F 4 (not G(2,4))=T 2-1->1 F 3 (not G(2,3))=F 2-1->1 (3=1)=F p=2 1 (not G(3,1))=T 2-1->1 F 2 (not G(3,2))=F 2-1->1 (2=1)=F 3 (not G(3,3))=F 2-1->1 (3=1)=F 4 (not G(3,4))=T 2-1->1 F 4 (not G(2,4))=T 2-1->1 F (4=1)=F p=2 1 (not G(4,1))=T 2-1->1 F 2 (not G(4,2))=F 2-1->1 (2=1)=F 3 (not G(4,3))=F 2-1->1 (3=1)=F 4 (not G(4,4))=T 2-1->1 F -- we have here 16 branches of execution out of only the "for p=1 to k-1" loop -- since san_count