Backtracking infinite loop
- by Greenhorn
This is Exercise 28.1.2 from HtDP. I've successfully implemented the neighbors function and all test cases pass.
(define Graph (list
(list 'A (list 'B 'E))
(list 'B (list 'E 'F))
(list 'C (list 'D))
(list 'D empty)
(list 'E (list 'C 'F))
(list 'F (list 'D 'G))
(list 'G empty)))
(define (first-line n alist)
(cond
[(symbol=? (first alist) n) alist]
[else empty]))
;; returns empty if node is not in graph
(define (neighbors n g)
(cond
[(empty? g) empty]
[(cons? (first g))
(cond
[(symbol=? (first (first g)) n) (first-line n (first g))]
[else (neighbors n (rest g))])]))
; test cases
(equal? (neighbors 'A Graph) (list 'A (list 'B 'E)))
(equal? (neighbors 'B Graph) (list 'B (list 'E 'F)))
(equal? (neighbors 'C Graph) (list 'C (list 'D)))
(equal? (neighbors 'D Graph) (list 'D empty))
(equal? (neighbors 'E Graph) (list 'E (list 'C 'F)))
(equal? (neighbors 'F Graph) (list 'F (list 'D 'G)))
(equal? (neighbors 'G Graph) (list 'G empty))
(equal? (neighbors 'H Graph) empty)
The problem comes when I copy-paste the code from Figure 77 of the text. It is supposed to determine whether a destination node is reachable from an origin node. However it appears that the code goes into an infinite loop except for the most trivial case where the origin and destination nodes are the same.
;; find-route : node node graph -> (listof node) or false
;; to create a path from origination to destination in G
;; if there is no path, the function produces false
(define (find-route origination destination G)
(cond
[(symbol=? origination destination) (list destination)]
[else (local ((define possible-route
(find-route/list (neighbors origination G) destination G)))
(cond
[(boolean? possible-route) false]
[else (cons origination possible-route)]))]))
;; find-route/list : (listof node) node graph -> (listof node) or false
;; to create a path from some node on lo-Os to D
;; if there is no path, the function produces false
(define (find-route/list lo-Os D G)
(cond
[(empty? lo-Os) false]
[else (local ((define possible-route (find-route (first lo-Os) D G)))
(cond
[(boolean? possible-route) (find-route/list (rest lo-Os) D G)]
[else possible-route]))]))
Does the problem lie in my code? Thank you.
