On this page:
Working with Nodes
Here Be Dragons

Lab 11 Graphs and Accumulators


Purpose: Practice working with graphs and accumulators.

Working with Nodes

Consider the following data definitions:
; A Node is a (make-node Nat Color [List-of Nat])
(define-struct node [id color neighbors])
; - where id is the unique identifier for the given node
; - color is the node's current color
; - and neighbors is a list of the ids of nodes this one is connected to
; A Graph is a [List-of Node]

Exercise 1 Finish the data design for the above data definitions.

Exercise 2 Design the function can-reach-in-time? which takes a Graph, the IDs of two nodes in the Graph, and a natural number. It determines whether you can get from the node with the first ID to the node with the second ID in the given number of steps. A step is when you move from a node to its neighbor.

Exercise 3 Design the function any-dead-ends? which takes a Graph and returns #true if there are any Nodes in the graph that have no neighbors.

Please submit the above exercise to the handin server by 10pm EDT on the day of lab.

Exercise 4 Design the function any-cycles? which takes a Graph and returns #true if there are any cygles in the graph. A cycle is when a node has a path leading back to itself in some way. For example, if node 1 goes to node 2 which goes to node 3 which goes to node 1, that is a cycle because you can get from node 1 back to node 1.

Here Be Dragons

For this part of the lab you will design functions to draw (and iterate) an interesting fractal design called the Dragon. This was used on the headings of chapters in the book Jurassic Park. We’ll start off by building a simple line drawing program. Then we’ll combine pieces into the fractal’s (generative) recursion.

Consider the following data definition:

; A Dir is one of:
; - 'left
; - 'right
; - 'up
; - 'down
; and represents one of the 4 cardinal directions
(define DIR-L 'left)
(define DIR-R 'right)
(define DIR-U 'up)
(define DIR-D 'down)
; dir-template : Dir -> ???
(define (dir-template d)
  (cond [(symbol=? d DIR-L) ...]
        [(symbol=? d DIR-R) ...]
        [(symbol=? d DIR-U) ...]
        [(symbol=? d DIR-D) ...]))

Exercise 5 Use a list abstraction to design the function rotate-all-dirs which takes a [List-of Dir and produces a list where each of the directions has been rotated 90 degrees counter-clockwise (to the left).

Exercise 6 Design the function get-end-point which takes a Posn and a Dir and produces a Posn representing the coordinates of the end of a line which starts at the given position and goes in the given direction. You may decide on a line length but it should be the same length every time.

Exercise 7 Use a list abstraction to design the function draw-all-dirs which takes a [List-of Dir, a Posn, and an Image. It then draws a line in each direction starting at the given position onto the given image. The pre-defined function add-line will come in handy, as will your get-end-point function.

This is enough to make a simple line-drawing program. Here is the code for that so you can try it out. You can start the program by calling etch-a-sketch with some starting coordinates. Then, use the arrow keys to draw lines and press "r" to rotate all the lines.

(define BACKGROUND (empty-scene 500 500))
; etch-a-sketch : Posn -> [List-of Dir]
; Draw lines starting at the given position
(define (etch-a-sketch start)
  (big-bang '()
    [to-draw (lambda (lod) (draw-all-dirs lod start BACKGROUND))]
    [on-key change-direction-list]))
; change-direction-list : [List-of Dir] KeyEvent -> [List-of Dir]
; Add a direction if the arrow key was pressed and rotate if the 'r' key was pressed
(check-expect (change-direction-list '() "left") (list DIR-L))
(check-expect (change-direction-list (list DIR-L DIR-D DIR-R) "r") (list DIR-D DIR-R DIR-U))
(check-expect (change-direction-list (list DIR-U DIR-U DIR-L) "x") (list DIR-U DIR-U DIR-L))
(define (change-direction-list lod key)
  (cond [(or (key=? key "left") (key=? key "right") (key=? key "up") (key=? key "down"))
         (append lod (list (string->symbol key)))]
        [(key=? key "r") (rotate-all-dirs lod)]
        [else lod]))

Now we need to generate our fractal! The algorithm takes a [List-of Dir] and a natural number that represents the iterations left to be done. It goes like this:
  • If the number of iterations is zero, we return the list unchanged.

  • Otherwise, return a new list modified as follows:
    • Rotate all the Dirs from the old list counter-clockwise.

    • Reverse the rotated list.

    • Append the new reversed/rotated list on the end of the old list.

    • Recur on the new list, with one less iteration to do.

Exercise 8 Design the function dragon-algo which takes a [List-of Dir] and a Nat that represents the iterations left to be done and implements the above algorithm, returning a [List-of Dir].

Now we can use the following big-bang code to run our dragon fractal program. You can start the program by calling dragon-fractal with a starting position. Then, press the up arrow key to increase the number of iterations and the down arrow key to decrease the number of iterations.

; dragon-fractal : Posn -> Nat
; Produce a dragon fractal starting at the given position
(define (dragon-fractal start)
  (big-bang 0
    [to-draw (lambda (n) (draw-all-dirs (dragon-algo (list DIR-D) n) start BACKGROUND))]
    [on-key update-iterations]))
; update-iterations : Nat KeyEvent -> Nat
; If the up arrow was pressed add 1, if the down arrow was pressed, subtract 1, otherwise
; make no change to the given number
(check-expect (update-iterations 10 "up") 11)
(check-expect (update-iterations 5 "down") 4)
(check-expect (update-iterations 3 "x") 3)
(define (update-iterations n key)
  (cond [(key=? key "up") (add1 n)]
        [(key=? key "down") (sub1 n)]
        [else n]))

NOTE: The program will most likely stop working correctly around iteration 12 because the fractal is too large to display properly. You may be able to increase the number of working iterations by increasing the size of the background, but not by much because the size of the fractal grows quite a bit on each iteration.