Lab 9: Graphs

This week’s lab is about working with graphs with additional fields in the nodes (vertices).

Consider the following data definitions:

; A Color is any string representing a valid color.

; 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]

1. Write a few example of the Graph.

2. Write graph-colors which produces a list of colors in the graph.

3. Write the function get-node-by-id which find the node for the given id in the graph.

4. Design the function can-reach-n-steps 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.

5. Write the function majority-color which produces the most frequent color of the node in the graph.

6. Write the function majority-color-update which updates each node in the graph to the majority color of its neighbors.

7. Write the function closest-same-color which produces the nearest id of the node in the graph that has the same color, given an id and a graph. The nearest node is defined as the node that can be reached by the shortest non-empty path. If no such node exist, produce #false. If multiple candidate answer exist, produce any one of them.