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")))))
4 (define Graph 
5   '((A (B E))
6     (B (E F))
7     (C (D))
8     (D ())
9     (E (C F))
10     (F (D G))
11     (G ())))
12 
13 (define Graph2
14   (list (list 'A (list 'B 'E))
15         (list 'B (list 'E 'F))
16         (list 'C (list 'D))
17         (list 'D empty)
18         (list 'E (list 'C 'F))
19         (list 'F (list 'D 'G))
20         (list 'G empty)))
21 
22 A node is a symbol.
23 
24 A path is a list of the form
25 (cons no lon)
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.
27 
28 A graph is either
29 1. empty or
30 2. (cons pa gr)
31 where pa is a path and gr is a graph.
32 
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.
35 
36 (define (find-route ori dest G)
37   (cond
38     [(symbol=? ori dest) (list ori)]
39     [else ... (find-route/list (neighbors ori G) dest G) ...]))
40 
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.
43 
44 (define (find-route/list lo-ori dest G)
45   ( ... ))
46 
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.
49 
50 (define (neighbors anode G)
51   (assf (lambda (x) (equal? anode x)) G))
52 
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
55 
56 (define (assf op aloxy)
57   (cond
58     [(empty? aloxy) false]
59     [(op (first (first aloxy))) (first aloxy)]
60     [else (assf op (rest aloxy))]))
61 
62 (assf (lambda (x) (equal? anode x)) G)