;; The first three lines of this file were inserted by DrScheme. They record metadata
;; about the language level of this file in a form that our tools can easily process.
#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")))))
(define Graph
'((A (B E))
(B (E F))
(C (D))
(D ())
(E (C F))
(F (D G))
(G ())))
(define Graph2
(list (list 'A (list 'B 'E))
(list 'B (list 'E 'F))
(list 'C (list 'D))
(list 'D empty)
(list 'E (list 'C 'F))
(list 'F (list 'D 'G))
(list 'G empty)))
A node is a symbol.
A path is a list of the form
(cons no lon)
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.
A graph is either
1. empty or
2. (cons pa gr)
where pa is a path and gr is a graph.
find-route : node node graph -> (listof nodes) or false
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.
(define (find-route ori dest G)
(cond
[(symbol=? ori dest) (list ori)]
[else ... (find-route/list (neighbors ori G) dest G) ...]))
find-route/list : (listof nodes) node graph -> (listof nodes) or false
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.
(define (find-route/list lo-ori dest G)
( ... ))
;neighbors : node graph -> (listof nodes)
;Given anode and G, find all the neighboring nodes of anode in G. If there are no neighboring nodes, return empty.
(define (neighbors anode G)
(assf (lambda (x) (equal? anode x)) G))
;; assf : (X -> boolean) (listof (list X Y)) -> (list X Y) or false
;; to find the first item on alop for whose first item p? holds
(define (assf op aloxy)
(cond
[(empty? aloxy) false]
[(op (first (first aloxy))) (first aloxy)]
[else (assf op (rest aloxy))]))
(assf (lambda (x) (equal? anode x)) G)