Backtracking infinite loop

Posted by Greenhorn on Stack Overflow See other posts from Stack Overflow or by Greenhorn
Published on 2011-01-13T04:47:36Z Indexed on 2011/01/13 4:54 UTC
Read the original article Hit count: 231

Filed under:
|
|

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.

© Stack Overflow or respective owner

Related posts about Scheme

Related posts about racket