;; The first three lines of this file were inserted by DrScheme. They record metadata ;; about the language level of this file in a form that our tools can easily process. #reader(lib "htdp-advanced-reader.ss" "lang")((modname |30.2|) (read-case-sensitive #t) (teachpacks ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))) (htdp-settings #(#t constructor repeating-decimal #t #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp"))))) ;A node is a symbol. ; ;A pair is a list ;(cons n1 (cons n2)), ie, (list n1 n2) ;where n1 and n2 are symbols representing nodes. ; ;A simple-graph is a (listof pairs). ;route-exists? : node node simple-graph -> boolean ;Determines if there exists a route from orig to dest given the simple-graph sg. ;route-exists?-aux : node (listof nodes) -> boolean ;Determine if there exists a route from orig to dest given the simple-graph sg. accu-seen represents nodes that have been visited before. If a node is visited twice and a route is not determined, return false. (define (route-exists? orig dest sg) (local ((define (route-exists?-aux orig accu-seen) (cond [(symbol=? orig dest) true] [(contains orig accu-seen) false] [else (route-exists?-aux (neighbor orig sg) (cons orig accu-seen))]))) (route-exists?-aux orig empty))) ;neighbor : node simple-graph -> node ;Given anode, find its neighbor in simple-graph. (define (neighbor anode sg) (cond [(empty? sg) (error 'neighbor "node does not exist")] [(symbol=? (first (first sg)) anode) (second (first sg))] [else (neighbor anode (rest sg))])) ;contains : X (listof X) -> boolean ;Determines if alox contains x. (define (contains x alox) (ormap (lambda (item) (equal? x item)) alox)) #| Old Body (cond [(empty? alox) false] [(equal? x (first alox)) true] [else (contains x (rest alox))])) |# (define SimpleG '((A B) (B C) (C E) (D E) (E B) (F F))) (not (route-exists? 'A 'D SimpleG)) (route-exists? 'D 'B SimpleG) (not (route-exists? 'F 'D SimpleG)) (route-exists? 'D 'C SimpleG)