Lab 10 Color Changing Graphs

Purpose: Practice working with graphs.

Working with Nodes

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.

Moody Graphs

In this section we will design a program that displays a graph and changes the color of its nodes on every clock tick. Each node will become the same color as the majority of their neighbors.

Step 1: What stays the same?

For your convenience we have provided some constants to use below. You can modify them or add to them if you find that you need to keep track of something else.

(require 2htdp/image)

(define WIDTH 500)

(define HEIGHT 500)

(define MARGIN-SIZE 25)

(define GRAPH-SIZE (- WIDTH (* MARGIN-SIZE 2)))

(define OFFSET (+ MARGIN-SIZE (/ GRAPH-SIZE 2)))

(define BACKGROUND (empty-scene WIDTH HEIGHT))

(define FONT-SIZE 15)

(define NODE-SIZE 20)

Step 2: What changes?

Luckily, we already have a data definition to work with! What a crazy random happenstance. We will use a Graph to keep track of the state of the world.

Step 3: Which handlers do we need?

Exercise 3 Write down the signatures and purpose statements for the handler functions you need. This is your "wishlist" of functions that you will need to create.

Step 4: Design your handlers

We will start by designing the function that draws the graph. Each node should be shown as a circle of the appropriate color with black lines drawn to each of the node’s neighbors. Since this can get a bit complicated we will break it down and design in a less top-down fashion than we normally do.

Exercise 4 To start, design the function draw-connections which takes a Posn (the position of a node), a [List-of Posn] (the positions of its neighbors), and an Image (the background). It draws a black line onto the image between the given Posn and each Posn in the given list. The pre-defined function add-line will be useful to you here.

Exercise 5 Now, design the function draw-all-connections which takes a Graph and a [List-of Posn] (representing the coordinates of the nodes in the graph) and draws lines between each node and its neighbors. Remember that list abstractions like map or foldr can take in more than one list at a time.

Exercise 6 In addition to the lines we want to draw circles for each node. Design the function draw-nodes-as-dots which takes a Graph, a [List-of Posn] (representing the coordinates of the nodes in the graph), and an Image (the background to draw on). The function draws a circle of the appropriate color for each node in the graph at the position indicated by its coordinates in the second list. The circle should be overlayed with an image of the node’s ID number so we can tell which node it is.

Exercise 7 Below we have provided some functions to get the coordinates for a given number of nodes. Using these functions and the ones you designed above, design the function draw-graph, which takes a Graph and produces an image of all its nodes and their connections. We recommend that you start by getting the coordinates for the nodes, then draw the lines connecting them, and then draw the nodes themselves. This way the nodes are drawn on top of the lines which tends to look cleaner.

; find-node-coordinates : Nat -> [List-of Posn]

; Produce coordinates for the given number of nodes

(check-expect (find-node-coordinates 0) empty)

(check-expect

(find-node-coordinates 2)

(list (make-posn 475 250) (make-posn 25 250)))

(define (find-node-coordinates num-nodes)

(build-list num-nodes (λ (index) (get-coordinates-at-index index num-nodes))))

; get-coordinates-at-index : Nat Nat -> Posn

; Find the coordinates for a node at the given index in a list of the given length

(check-expect (get-coordinates-at-index 10 20) (make-posn 25 250))

(check-expect (get-coordinates-at-index 7 8) (make-posn 409 91))

(define (get-coordinates-at-index index total)

(make-posn

(inexact->exact (round (+ (* (cos (* (/ index total) 2 pi)) 1/2 GRAPH-SIZE) OFFSET)))

(inexact->exact (round (+ (* (sin (* (/ index total) 2 pi)) 1/2 GRAPH-SIZE) OFFSET)))))

Now we will design the function that updates the graph as time goes by. At each tick we want each node in the graph to become the color shared by the majority of its neighbors. Again, we will break this down into smaller steps in the following exercises.

Exercise 8 Consider the data definition given below:

(define-struct count [element times])

; A [Count X] is a (make-count X Nat)

; and represents a count of the number of times an element has been seen in a list

Design the function count-all-colors which, given a [List-of Color], produces a [List-of [Count Color]] which contains the count of how many times each color appeared in the given list.

Exercise 9 Now design the function majority-color which takes a [List-of Node] and produces the Color that is most common. If there are no Nodes in the list your function should produce false.

Exercise 10 Design the function get-neighbor-nodes which takes a Graph and a Node and produces all the nodes in the graph that are neighbors of the given node.

Exercise 11 Now use the above functions to define update-graph which takes a Graph and produces a Graph where each node in the original graph now has the majority color of its neighbors. If it has no neighbors, the color of the node should remain unchanged.

Step 5: Put it all together!

Exercise 12 Design the function moody-graph which takes a Graph and displays it, changing the color of each node to match the majority of its neighbors on every tick. We recommend changing the tick-rate to something like 0.5 so that the color changes don’t go by too fast.

Stretch Goals - Random Graphs

Exercise 13 Design the function random-neighbors which takes a [List-of Nat] (the list of IDs for nodes in a graph) and a Nat (the number of neighbors to produce) and produces a list of the given size with random elements selected from the list of IDs. It is okay if your function sometimes produces repeated elements.

Exercise 14 Design the function random-node which takes a Nat (the ID of the node) and a [List-of Nat] (the list of all the IDs for nodes in a graph), and produces a Node with a random color and a random number of neighbors, selected using your random-neighbors function from the previous exercise. To help you produce a random color we have defined a function that takes a Nat and produces a Color:

; get-color : Nat -> Color

; Get a color given an index (all numbers greater than 5 produce pink)

(check-expect (get-color 0) "red")

(check-expect (get-color 1) "orange")

(check-expect (get-color 2) "yellow")

(check-expect (get-color 3) "dark green")

(check-expect (get-color 4) "blue")

(check-expect (get-color 5) "purple")

(check-expect (get-color 6) "pink")

(define (get-color n)

(cond [(= n 0) "red"]

[(= n 1) "orange"]

[(= n 2) "yellow"]

[(= n 3) "dark green"]

[(= n 4) "blue"]

[(= n 5) "purple"]

[else "pink"]))

Exercise 15 Design the function random-graph which takes a natural number indicating how many nodes should be in the graph and produces a Graph with that many random nodes.

Exercise 16 Design the function moody-random which takes a natural number indicating how many nodes should be in the graph and runs the moody-graph function on a random graph of that size.

Exercise 17 *Challenge* Update your moody-graph program to stop when the graph either (a) has nodes that are all the same color or (b) is just changing back and forth between two states.