Blob


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 |29.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 (define (find-route1 ori dest G)
5 (local ((define (find-route ori dest G)
6 (cond
7 [(symbol=? ori dest) (list ori)]
8 [else (local ((define possible-route (find-route/list (neighbors ori G) dest G)))
9 (cond
10 [(boolean? possible-route) false]
11 [else (cons ori possible-route)]))]))
12 (define (find-route/list lo-ori dest G)
13 (cond
14 [(empty? lo-ori) false]
15 [else (local ((define possible-route (find-route (first lo-ori) dest G)))
16 (cond [(boolean? possible-route) (find-route/list (rest lo-ori) dest G)]
17 [else possible-route]))]))
18 (define (neighbors anode G)
19 (first (rest (assf (lambda (x) (equal? anode x)) G)))))
20 find-route ori dest G))
22 (define (neighbors anode agraph)
23 (vector-ref agraph anode))
26 (define G (vector '(1 4)
27 '(4 5)
28 '(3)
29 empty
30 '(2 5)
31 '(3 6)
32 empty))
34 ;find-route : node node graph -> (listof nodes)
35 ;Find a route from ori to dest given G and return the route as a (listof nodes).
37 (define (find-route ori dest G)
38 (cond
39 [(= ori dest) (list ori)]
40 [else (local ((define possible-route (find-route/list (neighbors ori G) dest G)))
41 (cond [(boolean? possible-route) false]
42 [else (cons ori possible-route)]))]))
44 ;find-route/list : (listof nodes) node graph -> (listof nodes)
45 ;Find a route from lo-ori (listof nodes) to dest given G and return the route as a (listof nodes).
47 (define (find-route/list lo-ori dest G)
48 (cond
49 [(empty? lo-ori) false]
50 [else (local ((define possible-route (find-route (first lo-ori) dest G)))
51 (cond
52 [(boolean? possible-route) (find-route/list (rest lo-ori) dest G)]
53 [else possible-route]))]))