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-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")))))
 4 12687dd9 2023-08-04 jrmu (define Graph 
 5 12687dd9 2023-08-04 jrmu   '((A (B E))
 6 12687dd9 2023-08-04 jrmu     (B (E F))
 7 12687dd9 2023-08-04 jrmu     (C (D))
 8 12687dd9 2023-08-04 jrmu     (D ())
 9 12687dd9 2023-08-04 jrmu     (E (C F))
10 12687dd9 2023-08-04 jrmu     (F (D G))
11 12687dd9 2023-08-04 jrmu     (G ())))
12 12687dd9 2023-08-04 jrmu 
13 12687dd9 2023-08-04 jrmu (define Graph2
14 12687dd9 2023-08-04 jrmu   (list (list 'A (list 'B 'E))
15 12687dd9 2023-08-04 jrmu         (list 'B (list 'E 'F))
16 12687dd9 2023-08-04 jrmu         (list 'C (list 'D))
17 12687dd9 2023-08-04 jrmu         (list 'D empty)
18 12687dd9 2023-08-04 jrmu         (list 'E (list 'C 'F))
19 12687dd9 2023-08-04 jrmu         (list 'F (list 'D 'G))
20 12687dd9 2023-08-04 jrmu         (list 'G empty)))
21 12687dd9 2023-08-04 jrmu 
22 12687dd9 2023-08-04 jrmu A node is a symbol.
23 12687dd9 2023-08-04 jrmu 
24 12687dd9 2023-08-04 jrmu A path is a list of the form
25 12687dd9 2023-08-04 jrmu (cons no lon)
26 12687dd9 2023-08-04 jrmu 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.
27 12687dd9 2023-08-04 jrmu 
28 12687dd9 2023-08-04 jrmu A graph is either
29 12687dd9 2023-08-04 jrmu 1. empty or
30 12687dd9 2023-08-04 jrmu 2. (cons pa gr)
31 12687dd9 2023-08-04 jrmu where pa is a path and gr is a graph.
32 12687dd9 2023-08-04 jrmu 
33 12687dd9 2023-08-04 jrmu find-route : node node graph -> (listof nodes) or false
34 12687dd9 2023-08-04 jrmu 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.
35 12687dd9 2023-08-04 jrmu 
36 12687dd9 2023-08-04 jrmu (define (find-route ori dest G)
37 12687dd9 2023-08-04 jrmu   (cond
38 12687dd9 2023-08-04 jrmu     [(symbol=? ori dest) (list ori)]
39 12687dd9 2023-08-04 jrmu     [else ... (find-route/list (neighbors ori G) dest G) ...]))
40 12687dd9 2023-08-04 jrmu 
41 12687dd9 2023-08-04 jrmu find-route/list : (listof nodes) node graph -> (listof nodes) or false
42 12687dd9 2023-08-04 jrmu 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.
43 12687dd9 2023-08-04 jrmu 
44 12687dd9 2023-08-04 jrmu (define (find-route/list lo-ori dest G)
45 12687dd9 2023-08-04 jrmu   ( ... ))
46 12687dd9 2023-08-04 jrmu 
47 12687dd9 2023-08-04 jrmu ;neighbors : node graph -> (listof nodes)
48 12687dd9 2023-08-04 jrmu ;Given anode and G, find all the neighboring nodes of anode in G.  If there are no neighboring nodes, return empty.
49 12687dd9 2023-08-04 jrmu 
50 12687dd9 2023-08-04 jrmu (define (neighbors anode G)
51 12687dd9 2023-08-04 jrmu   (assf (lambda (x) (equal? anode x)) G))
52 12687dd9 2023-08-04 jrmu 
53 12687dd9 2023-08-04 jrmu ;; assf : (X  ->  boolean) (listof (list X Y))  ->  (list X Y) or false
54 12687dd9 2023-08-04 jrmu ;; to find the first item on alop for whose first item p? holds
55 12687dd9 2023-08-04 jrmu 
56 12687dd9 2023-08-04 jrmu (define (assf op aloxy)
57 12687dd9 2023-08-04 jrmu   (cond
58 12687dd9 2023-08-04 jrmu     [(empty? aloxy) false]
59 12687dd9 2023-08-04 jrmu     [(op (first (first aloxy))) (first aloxy)]
60 12687dd9 2023-08-04 jrmu     [else (assf op (rest aloxy))]))
61 12687dd9 2023-08-04 jrmu 
62 12687dd9 2023-08-04 jrmu (neighbors 'A Graph2