Homework 11

home work!

Programming Language ISL+Lambda

Due Date: Wednesday June 17, 10pm EDT.

Purpose: To do exercises with Graphs

Extra Credit This assignment is optional and will count as extra credit

Exercise 1 Consider again the data designs of Page and Wiki from Lecture last Thursday. Copy these designs into your homework file.

(define-struct page [title links])
; A Page is a (make-page String [List-of String])
; repr. a web page's title and links to other pages.
(define PAGE-0 (make-page "Khoury"        (list "NEU")))
(define PAGE-1 (make-page "NEU"           (list "Khoury" "Boston")))
(define PAGE-2 (make-page "Boston"        (list "NEU" "Shillman Hall")))
(define PAGE-3 (make-page "Shillman Hall" (list "NEU")))
(define PAGE-4 (make-page "New Orleans"   (list "Mardi Gras")))
; A Wiki is a [List-of WebPage]
; Interpretation: A list of webpages (like the Internet)
(define WIKI-0 (list PAGE-0 PAGE-1 PAGE-2 PAGE-3 PAGE-4))

Design the function find-path that takes two strings t1 and t2 representing page names in a wiki, and a wiki. If there is a path (following links) from t1 to t2 in the wiki, your function should return such a path as a list of strings, representing the pages visited along the path. Note that the first string in the output must be t1, and the last string must be t2.

If there is no such path, your function should return the empty list.

The length of the list your function returns should equal the number of links followed along the path PLUS 1. For example, if t1 and t2 are equal, then (list t1) is one valid answer (the number of links followed is 0; the list has length 1).

Hint: You will need a helper function that finds a path from one of t1’s links to t2. This function and find-path will call each other mutually recursively. Also, you may need the eliminate function (shown below) although you are not required to use it.

; eliminate : String Wiki -> Wiki
; the wiki without page with the given name
(check-expect (eliminate "NEU" (list PAGE-0 PAGE-1))
              (list (make-page "Khoury" '())))
(define (eliminate t w)
  (cond [(empty? w) '()]
        [(cons? w)  (if (string=? (page-title (first w)) t)
                        (eliminate t (rest w))
                        (cons (eliminate-links-to t (first w))
                              (eliminate t (rest w))))]))
; eliminate-links-to : String Page -> Page
; the page without any links to the page with the given name
(check-expect (eliminate-links-to "NEU" PAGE-3) (make-page "Shillman Hall" '()))
(define (eliminate-links-to t p)
  (make-page (page-title p)
             (filter (lambda (l) (not (string=? l t))) (page-links p))))