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 |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 ;A node is a symbol.
5 ;
6 ;A pair is a list
7 ;(cons n1 (cons n2)), ie, (list n1 n2)
8 ;where n1 and n2 are symbols representing nodes.
9 ;
10 ;A simple-graph is a (listof pairs).
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   (cond
31     [(empty? sg) (error 'neighbor "node does not exist")]
32     [(symbol=? (first (first sg)) anode) (second (first sg))]
33     [else (neighbor anode (rest sg))]))
34 
35 ;contains : X (listof X) -> boolean
36 ;Determines if alox contains x.
37 
38 (define (contains x alox)
39   (ormap (lambda (item) (equal? x item)) alox))
40 #|
41   Old Body
42   (cond
43     [(empty? alox) false]
44     [(equal? x (first alox)) true]
45     [else (contains x (rest alox))]))
46 |#
47 (define SimpleG
48   '((A B)
49     (B C)
50     (C E)
51     (D E)
52     (E B)
53     (F F)))
54 
55 (not (route-exists? 'A 'D SimpleG))
56 (route-exists? 'D 'B SimpleG)
57 (not (route-exists? 'F 'D SimpleG))
58 (route-exists? 'D 'C SimpleG)