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 |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")))))
4 12687dd9 2023-08-04 jrmu ;A node is a symbol.
6 12687dd9 2023-08-04 jrmu ;A pair is a vector
7 12687dd9 2023-08-04 jrmu ;(vector n1 n2)
8 12687dd9 2023-08-04 jrmu ;where n1 and n2 are symbols representing nodes.
10 12687dd9 2023-08-04 jrmu ;A simple-graph is a (vectorof pairs), that is, a (vectorof (vector n1 n2)), where n1 and n2 are nodes.
12 12687dd9 2023-08-04 jrmu ;route-exists? : node node simple-graph -> boolean
13 12687dd9 2023-08-04 jrmu ;Determines if there exists a route from orig to dest given the simple-graph sg.
15 12687dd9 2023-08-04 jrmu ;route-exists?-aux : node (listof nodes) -> boolean
16 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.
18 12687dd9 2023-08-04 jrmu (define (route-exists? orig dest sg)
19 12687dd9 2023-08-04 jrmu (local ((define (route-exists?-aux orig accu-seen)
21 12687dd9 2023-08-04 jrmu [(symbol=? orig dest) true]
22 12687dd9 2023-08-04 jrmu [(contains orig accu-seen) false]
23 12687dd9 2023-08-04 jrmu [else (route-exists?-aux (neighbor orig sg) (cons orig accu-seen))])))
24 12687dd9 2023-08-04 jrmu (route-exists?-aux orig empty)))
26 12687dd9 2023-08-04 jrmu ;neighbor : node simple-graph -> node
27 12687dd9 2023-08-04 jrmu ;Given anode, find its neighbor in simple-graph.
29 12687dd9 2023-08-04 jrmu (define (neighbor anode sg)
30 12687dd9 2023-08-04 jrmu (neighbor-aux anode sg 0))
32 12687dd9 2023-08-04 jrmu ;neighbor-aux : node simple-graph N -> node
33 12687dd9 2023-08-04 jrmu ;Find the neighbor of anode in sg using the index i.
35 12687dd9 2023-08-04 jrmu (define (neighbor-aux anode sg i)
37 12687dd9 2023-08-04 jrmu [(= (vector-length sg) i) (error 'neighbor-aux "node not found")]
38 12687dd9 2023-08-04 jrmu [(symbol=? (vector-ref (vector-ref sg i) 0) anode) (vector-ref (vector-ref sg i) 1)]
39 12687dd9 2023-08-04 jrmu [else (neighbor-aux anode sg (add1 i))]))
41 12687dd9 2023-08-04 jrmu ;contains : X (listof X) -> boolean
42 12687dd9 2023-08-04 jrmu ;Determines if alox contains x.
44 12687dd9 2023-08-04 jrmu (define (contains x alox)
45 12687dd9 2023-08-04 jrmu (ormap (lambda (item) (equal? x item)) alox))
49 12687dd9 2023-08-04 jrmu [(empty? alox) false]
50 12687dd9 2023-08-04 jrmu [(equal? x (first alox)) true]
51 12687dd9 2023-08-04 jrmu [else (contains x (rest alox))]))
53 12687dd9 2023-08-04 jrmu (define SimpleG
54 12687dd9 2023-08-04 jrmu (vector (vector 'A 'B)
55 12687dd9 2023-08-04 jrmu (vector 'B 'C)
56 12687dd9 2023-08-04 jrmu (vector 'C 'E)
57 12687dd9 2023-08-04 jrmu (vector 'D 'E)
58 12687dd9 2023-08-04 jrmu (vector 'E 'B)
59 12687dd9 2023-08-04 jrmu (vector 'F 'F)))
61 12687dd9 2023-08-04 jrmu (not (route-exists? 'A 'D SimpleG))
62 12687dd9 2023-08-04 jrmu (route-exists? 'D 'B SimpleG)
63 12687dd9 2023-08-04 jrmu (not (route-exists? 'F 'D SimpleG))
64 12687dd9 2023-08-04 jrmu (route-exists? 'D 'C SimpleG)
