On this page:
Readings
Supplemental Materials
Pre-lecture
Goals
In-class
Homework

Module 10

Last updated: Thu, 26 Mar 2015 13:23:36 -0400

Readings
Supplemental Materials
Pre-lecture
  1. Read the Readings and Supplemental Materials.

Goals
In-class

Revise find-path from Chapter 33 such that it always terminates. Be sure to state accumulator invariants and termination arguments as necessary.
Start with the following code given in the chapter:
(require rackunit)
(require racket/set)
 
; A Node is a Symbol
; Represents a vertex in a graph.
 
; A Path is a ListOf<Node>
; Represents a sequence of connected Nodes.
 
; A Graph is a ListOf<(cons Node ListOf<Nodes>)>
; A list of adjacency lists representing a directed graph.
; WHERE: (map first G) has no duplicates and represents the nodes in G
; and the rest of each adj list are the neighbors of the first node.
 
(define SAMPLE-G
  '((A B E)
    (B E F)
    (C D)
    (D)
    (E C F)
    (F D G)
    (G)))
 
; get-nodes : Graph -> ListOf<Node>
; Returns the nodes in g.
(define (get-nodes g)
  (map first g))
 
; neighbors : Node Graph -> ListOf<Node>
; Returns a list of all nodes v such that G has edge u-v.
(define (neighbors u G)
  (rest (assq u G)))
 
; find-path : Node Node Graph -> Maybe<Path>
; Finds a path from orig to dest in G, or #f if no such path exists.
; Strategy: ???
; Termination argument: ???
(define (find-path orig dest G)
  (cond
    [(symbol=? orig dest) (list dest)]
    [else
     (local ((define next (neighbors orig G))
             (define path/#f (find-path/list next dest G)))
       (if (false? path/#f)
           #f
           (cons orig path/#f)))]))
 
; find-path/list : ListOf<Node> Node Graph -> Maybe<Path>
; Finds a path from some node in origs to dest in G.
; Returns #f is there is no path from any node in origs to dest.
; Strategy: data decomposition on origs : ListOf<Node>
(define (find-path/list origs dest G)
  (cond
    [(empty? origs) #f]
    [else
     (local ((define path/#f (find-path (first origs) dest G)))
       (if (false? path/#f)
           (find-path/list (rest origs) dest G)
           path/#f))]))
 
(check-equal? (find-path 'C 'D SAMPLE-G) '(C D))
(check set-member? '((E F D) (E C D)) (find-path 'E 'D SAMPLE-G))
(check-false (find-path 'C 'G SAMPLE-G))
Notes:
  • To help readability, use a /#f prefix for variables that represent Maybe<X> values.

  • Inlining one decomposition of a Maybe<X> result is acceptable.

  • From now on, you may require and use functions from racket/set if you wish.

Tasks:
  1. Complete the design strategy and termination argument for find-path.

  2. Implement the following list-processing function:
    ; find : (X -> Maybe<Y>) ListOf<X> -> Maybe<Y>
    ; Returns (f x) for the first element x in lst where (f x) != #f,
    ; otherwise returns #f.
    (define (find f lst) ...)

  3. Revise find-path to use find instead of find-path/list.

  4. Revise find-path such that the following test case does not loop forever:
    (define CYCLIC-G
      '((A B E)
        (B E F)
        (C B)
        (D)
        (E C F)
        (F D G)
        (G)))
     
    (check
     set-member?
     '((B F D) (B E F D) (B E C D))
     (find-path 'B 'D CYCLIC-G))
    Be sure to state a proper invariant if you use an accumulator. Also, update the termination argument such that it explains why the function always terminates.

Homework

Problem Set 10