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, 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. To make a "step" means to move from a node to one of its neighbors.

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 adopt the color of the majority of its neighbors.

Step 1: What stays the same?

We are providing 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)

(require 2htdp/universe)

(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: 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 need to create.

Step 4: Main Function

Now we can put together our main function, which calls big-bang. We provide the main function for this program for you, so that it works with the code we give you below.

; moody-graph : Graph -> Graph

; draw the graph, and change its nodes to have the color

; of the majority of their neighbors

(define (moody-graph graph)

(big-bang graph

[to-draw draw-graph]

[on-tick update-graph 0.5]))

Step 5: Design your handlers

The to-draw function is long and doesn’t contribute much to the purpose of this lab, so we provide this for you here:

https://course.ccs.neu.edu/cs2500sp21/lab10-students-to-draw.txt

Just copy this code into your file.

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

Exercise 4 Consider the data definition given below:

(define-struct count [element times])

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

; how often an element occurs in a list

Design the function count-strings which, given a [List-of String], returns a [List-of [Count String]] containing, for each given string, how often it appears in the list.

Exercise 5 Design the function majority-color, which takes a [List-of Node] and returns the color that is most common. If the list is empty, your function should return #f. Your signature should accommodate the fact that the function returns a color or #f.

Exercise 6 Design the function get-neighbor-nodes, which takes a Graph and a Node and returns all neighbors in the graph of the given node.

Exercise 7 Now use the above functions to design update-graph, which takes a Graph and returns a new Graph where each node has adopted the majority color of its neighbors in the original graph. If a node has no neighbors, its color should remain unchanged.

Bushy Trees

Exercise 8 Finish the Data Design for a 3Tree-of X

Exercise 9 Design a function 3tree-grab-x-coords which, given a [3Tree-of Posn] returns a tree with just the x-coordinates of each node.

Exercise 10 Design a function 3tree-count, which accepts a tree and a predicate and counts the number of nodes in the tree whose values pass the predicate. Hint: use the [3Tree-of X] template.

Exercise 11 Trees are just like lists but with a more interesting and flexible structure. So it stands to reason that we can create abstractions over trees like we do for lists. We can design the following abstractions for a ternary tree:

• 3tree-map: Given a tree and a function to transform the data at each node, return a tree with the given function applied to the value at every node.

• 3tree-ormap: Given a tree and a predicate, return whether any node’s value in the tree passes the given predicate.

Exercise 12 Can you redefine 3tree-grab-x-coords and 3tree-count with the abstractions? If so, redefine the function using the abstract. If not, what abstraction do you need?