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-intermediate-lambda-reader.ss" "lang")((modname |28.1|) (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 #f #t none #f ((lib "draw.ss" "teachpack" "htdp") (lib "arrow.ss" "teachpack" "htdp") (lib "gui.ss" "teachpack" "htdp")))))
14 (list (list 'A (list 'B 'E))
15 (list 'B (list 'E 'F))
18 (list 'E (list 'C 'F))
19 (list 'F (list 'D 'G))
24 A path is a list of the form
26 where no is a node and lon is a (listof nodes). A path represents a node and the nodes that can be accessed from the node.
31 where pa is a path and gr is a graph.
33 find-route : node node graph -> (listof nodes) or false
34 Given dest, ori, and G, find a route from dest to ori in G and return is as a (listof nodes). The destination and origin are included in the (listof nodes). If no route is available, return false.
36 (define (find-route ori dest G)
38 [(symbol=? ori dest) (list ori)]
39 [else ... (find-route/list (neighbors ori G) dest G) ...]))
41 find-route/list : (listof nodes) node graph -> (listof nodes) or false
42 Given lo-ori (listof origins), dest, and G, produce a route from some node on lo-ori to dest in G. Return the route as a (listof nodes) or false if no route is available.
44 (define (find-route/list lo-ori dest G)
47 ;neighbors : node graph -> (listof nodes)
48 ;Given anode and G, find all the neighboring nodes of anode in G. If there are no neighboring nodes, return empty.
50 (define (neighbors anode G)
51 (assf (lambda (x) (equal? anode x)) G))
53 ;; assf : (X -> boolean) (listof (list X Y)) -> (list X Y) or false
54 ;; to find the first item on alop for whose first item p? holds
56 (define (assf op aloxy)
58 [(empty? aloxy) false]
59 [(op (first (first aloxy))) (first aloxy)]
60 [else (assf op (rest aloxy))]))