1 ;; The first three lines of this file were inserted by DrScheme. They record metadata
2 ;; about the language level of this file in a form that our tools can easily process.
3 #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 ;A node is a symbol.
5 ;
6 ;A pair is a vector
7 ;(vector n1 n2)
8 ;where n1 and n2 are symbols representing nodes.
9 ;
10 ;A simple-graph is a (vectorof pairs), that is, a (vectorof (vector n1 n2)), where n1 and n2 are nodes.
11 
12 ;route-exists? : node node simple-graph -> boolean
13 ;Determines if there exists a route from orig to dest given the simple-graph sg.
14 
15 ;route-exists?-aux : node (listof nodes) -> boolean
16 ;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.
17 
18 (define (route-exists? orig dest sg)
19   (local ((define (route-exists?-aux orig accu-seen)
20             (cond
21               [(symbol=? orig dest) true]
22               [(contains orig accu-seen) false]
23               [else (route-exists?-aux (neighbor orig sg) (cons orig accu-seen))])))
24     (route-exists?-aux orig empty)))
25 
26 ;neighbor : node simple-graph -> node
27 ;Given anode, find its neighbor in simple-graph.
28 
29 (define (neighbor anode sg)
30   (neighbor-aux anode sg 0))
31 
32 ;neighbor-aux : node simple-graph N -> node
33 ;Find the neighbor of anode in sg using the index i.
34 
35 (define (neighbor-aux anode sg i)
36   (cond
37     [(= (vector-length sg) i) (error 'neighbor-aux "node not found")]
38     [(symbol=? (vector-ref (vector-ref sg i) 0) anode) (vector-ref (vector-ref sg i) 1)]
39     [else (neighbor-aux anode sg (add1 i))]))
40 
41 ;contains : X (listof X) -> boolean
42 ;Determines if alox contains x.
43 
44 (define (contains x alox)
45   (ormap (lambda (item) (equal? x item)) alox))
46 #|
47   Old Body
48   (cond
49     [(empty? alox) false]
50     [(equal? x (first alox)) true]
51     [else (contains x (rest alox))]))
52 |#
53 (define SimpleG
54   (vector (vector 'A 'B)
55           (vector 'B 'C)
56           (vector 'C 'E)
57           (vector 'D 'E)
58           (vector 'E 'B)
59           (vector 'F 'F)))
60 
61 (not (route-exists? 'A 'D SimpleG))
62 (route-exists? 'D 'B SimpleG)
63 (not (route-exists? 'F 'D SimpleG))
64 (route-exists? 'D 'C SimpleG)