1 12687dd9 2023-08-04 jrmu ;; The first three lines of this file were inserted by DrScheme. They record metadata
 2 12687dd9 2023-08-04 jrmu ;; about the language level of this file in a form that our tools can easily process.
 3 12687dd9 2023-08-04 jrmu #reader(lib "htdp-advanced-reader.ss" "lang")((modname |37.3|) (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")))))
 4 12687dd9 2023-08-04 jrmu ;A node is a symbol.
 5 12687dd9 2023-08-04 jrmu ;
 6 12687dd9 2023-08-04 jrmu ;A pair is a list
 7 12687dd9 2023-08-04 jrmu ;(cons n1 (cons n2)), ie, (list n1 n2)
 8 12687dd9 2023-08-04 jrmu ;where n1 and n2 are symbols representing nodes.
 9 12687dd9 2023-08-04 jrmu ;
10 12687dd9 2023-08-04 jrmu ;A simple-graph is a (listof pairs).
11 12687dd9 2023-08-04 jrmu 
12 12687dd9 2023-08-04 jrmu ;;State Variables
13 12687dd9 2023-08-04 jrmu 
14 12687dd9 2023-08-04 jrmu ;;seen-before : (listof nodes)
15 12687dd9 2023-08-04 jrmu ;;Keeps track of all nodes that have been accessed in the past.
16 12687dd9 2023-08-04 jrmu 
17 12687dd9 2023-08-04 jrmu (define seen-before empty)
18 12687dd9 2023-08-04 jrmu 
19 12687dd9 2023-08-04 jrmu ;route-exists? : node node simple-graph -> boolean
20 12687dd9 2023-08-04 jrmu ;Determines if there exists a route from orig to dest given the simple-graph sg.
21 12687dd9 2023-08-04 jrmu 
22 12687dd9 2023-08-04 jrmu ;route-exists?-aux : node (listof nodes) -> boolean
23 12687dd9 2023-08-04 jrmu ;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.
24 12687dd9 2023-08-04 jrmu 
25 12687dd9 2023-08-04 jrmu (define (route-exists? orig dest sg)
26 12687dd9 2023-08-04 jrmu   (local ((define (route-exists?-aux orig dest sg)
27 12687dd9 2023-08-04 jrmu             (cond
28 12687dd9 2023-08-04 jrmu               [(symbol=? orig dest) true]
29 12687dd9 2023-08-04 jrmu               [(contains orig seen-before) false]
30 12687dd9 2023-08-04 jrmu               [else (begin (set! seen-before (cons orig seen-before))
31 12687dd9 2023-08-04 jrmu                            (route-exists?-aux (neighbor orig sg) dest sg))])))
32 12687dd9 2023-08-04 jrmu     (begin (set! seen-before empty)
33 12687dd9 2023-08-04 jrmu            (route-exists?-aux orig dest sg))))
34 12687dd9 2023-08-04 jrmu 
35 12687dd9 2023-08-04 jrmu ;neighbor : node simple-graph -> node
36 12687dd9 2023-08-04 jrmu ;Given anode, find its neighbor in simple-graph.
37 12687dd9 2023-08-04 jrmu 
38 12687dd9 2023-08-04 jrmu (define (neighbor anode sg)
39 12687dd9 2023-08-04 jrmu   (cond
40 12687dd9 2023-08-04 jrmu     [(empty? sg) (error 'neighbor "node does not exist")]
41 12687dd9 2023-08-04 jrmu     [(symbol=? (first (first sg)) anode) (second (first sg))]
42 12687dd9 2023-08-04 jrmu     [else (neighbor anode (rest sg))]))
43 12687dd9 2023-08-04 jrmu 
44 12687dd9 2023-08-04 jrmu ;contains : X (listof X) -> boolean
45 12687dd9 2023-08-04 jrmu ;Determines if alox contains x.
46 12687dd9 2023-08-04 jrmu 
47 12687dd9 2023-08-04 jrmu (define (contains x alox)
48 12687dd9 2023-08-04 jrmu   (ormap (lambda (item) (equal? x item)) alox))
49 12687dd9 2023-08-04 jrmu #|
50 12687dd9 2023-08-04 jrmu   Old Body
51 12687dd9 2023-08-04 jrmu   (cond
52 12687dd9 2023-08-04 jrmu     [(empty? alox) false]
53 12687dd9 2023-08-04 jrmu     [(equal? x (first alox)) true]
54 12687dd9 2023-08-04 jrmu     [else (contains x (rest alox))]))
55 12687dd9 2023-08-04 jrmu |#
56 12687dd9 2023-08-04 jrmu (define SimpleG
57 12687dd9 2023-08-04 jrmu   '((A B)
58 12687dd9 2023-08-04 jrmu     (B C)
59 12687dd9 2023-08-04 jrmu     (C E)
60 12687dd9 2023-08-04 jrmu     (D E)
61 12687dd9 2023-08-04 jrmu     (E B)
62 12687dd9 2023-08-04 jrmu     (F F)))
63 12687dd9 2023-08-04 jrmu 
64 12687dd9 2023-08-04 jrmu (not (route-exists? 'A 'D SimpleG))
65 12687dd9 2023-08-04 jrmu (route-exists? 'D 'B SimpleG)
66 12687dd9 2023-08-04 jrmu (not (route-exists? 'F 'D SimpleG))
67 12687dd9 2023-08-04 jrmu (route-exists? 'D 'C SimpleG)