;; 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)