Assignment 17

Due Date Monday 11/19 at 9pm

Purpose To process graphs.

Below is a data definition for a network consisting of people who have names, beliefs, and a list of friends. You do not need to provide a template for this data definition.

; A Network is a [List-of Person]

; A Person is a (make-person String Belief [List-of String])

(define-struct person [name belief friends])

; and represents their name, their belief, and the name of their friends

; A Belief is one of:

; - "blue"

; - "red"

(define NETWORK

(list

(make-person "Alice" "red" (list "Carol" "Heidi"))

(make-person "Bob" "blue" (list "Carol" "Dan"))

(make-person "Carol" "red" (list))

(make-person "Dan" "blue" (list "Carol" "Eric" "Frank" "Grace"))

(make-person "Eric" "red" (list "Alice" "Bob" "Carol" "Dan" "Frank" "Grace"))

(make-person "Frank" "blue" (list "Alice" "Bob" "Carol" "Dan" "Grace"))

(make-person "Grace" "red" (list "Bob" "Frank"))

(make-person "Heidi" "blue" (list "Alice" "Bob" "Carol" "Dan" "Eric" "Grace"))))

Exercise 1 Design the function update-network, which takes a Network and updates every individual’s belief to become the belief the majority of their friends have. If there is no majority amongst their friends (a tie), then their belief is unchanged. Note that this update is atomic which means everyone’s beliefs updates at once based only on the previous network’s state. In other words, where someone appears in the network should have no effect on the update process.

Exercise 2 Design the function can-reach?, which takes the names of two people and a network asks if the first person can reach the second. Anyone can reach themselves, and anyone can reach another person through their friends if that friend has the same belief as them.

Assume the network given to this function is acyclic and specify as such in your purpose statement. Be sure to only test on acyclic networks; the provided network is not acyclic.