Homework Assignment 2#
✅ Put your name here.
#✅ Put your GitHub username here.
#Goals for this homework assignment#
By the end of this assignment, you should be able to:
Define custom classes and show they are implemented correctly through tests.
Implement agent based models and observe emergent phenomena.
Use Pandas and NetworkX to create, analyze, and visualize graphs.
Read documentation to learn about new code.
Read and understand provided code.
Work through the following assignment, making sure to follow all of the directions and answer all of the questions.
There are 88 points possible on this assignment. Point values for each part are included in the section headers and question prompts.
This assignment is due on Friday, October 17th at 11:59pm ET. It should be uploaded into the “Homework Assignments” submission folder for Homework #2. Submission instructions can be found at the end of the notebook.
Table of contents#
Part 1: Git and CLI (8 points)
Part 2: Agent based modeling (11 points)
Part 3: Graph theory (8 points)
Part 1: Add to your Git repository to track your progress on your assignment (8 points)#
For this assignment, you’re going to add it to the cmse202-f25-turnin repository you created in class so that you can track your progress on the assignment and preserve the final version that you turn in. In order to do this you need to
✅ Do the following:
Navigate to your
cmse202-f25-turninrepository and create a new directory calledhw-02.Move this notebook into that new directory in your repository, then add it and commit it to your repository.
Finally, to test that everything is working, “git push” the file so that it ends up in your GitHub repository.
Important: Double check you’ve added your Professor and your TA as collaborators to your “turnin” repository (you should have done this in the previous homework assignment).
Also important: Make sure that the version of this notebook that you are working on is the same one that you just added to your repository! If you are working on a different copy of the notebook, none of your changes will be tracked!
If everything went as intended, the file should now show up on your GitHub account in the “cmse202-f25-turnin” repository inside the hw-02 directory that you just created. Periodically, you’ll be asked to commit your changes to the repository and push them to the remote GitHub location. Of course, you can always commit your changes more often than that, if you wish. It can be good to get into a habit of committing your changes any time you make a significant modification, or when you stop working on the project for a bit.
✅ 1.1 Do this: Before you move on, put the command that your instructor should run to clone your repository in the markdown cell below.
# Put the command to clone your repository here.
You MUST commit and push your notebook multiple times during this assignment.
Part 2: Build an agent based model for Conway’s game of life (52 points)#
Conway’s game of life is a classic example of a system with simple rules that exhibits interesting emergent phenomena. In this problem you will implement an ABM to simulate Conway’s game of life and explore some of this emergent phenomena.
Conway’s game of life consists of cells which have a location (\(x\) coordinate and \(y\) coordinate) and can be alive or dead. Cells interact via the following rules, taken from the Wikipedia entry:
Any live cell with fewer than two live neighbors dies, as if by underpopulation.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by overpopulation.
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
✅ Question 2.1 (6 points): Complete the following Cell class provided the template and docstrings. Some methods are completed for you. You may add data or attributes if convenient, but you must not remove or change any given attributes or methods from the template.
# Complete the following class!
class Cell:
def __init__(self, x, y, alive=False):
"""Initializes a Cell.
Args:
x (int): The x-coordinate of the cell.
y (int): The y-coordinate of the cell.
alive (bool): Whether the cell is alive (True) or dead (False).
"""
# Do not modify this method!
self.x = x
self.y = y
self.alive = alive
def is_alive(self):
"""Returns True if the cell is alive, else returns False."""
pass # Your code here.
def kill(self):
"""Sets the Cell's alive attribute to False. Does not return a value."""
pass # Your code here.
def live(self):
"""Sets the Cell's alive attribute to True. Does not return a value."""
pass # Your code here.
def copy(self):
"""Returns a copy of the Cell - that is, returns a new Cell with the
same x, y, and alive attributes.
"""
pass # Your code here.
def has_same_location(self, other):
"""Returns True if the other Cell has the same location as this Cell, else returns False.
Args:
other (Cell): The other Cell to compare locations with.
"""
pass # Your code here.
def __eq__(self, other):
"""Returns True if the other Cell is equal to this cell, else returns False.
Two cells are equal if they have they same x, y, and alive attributes.
Args:
other (Cell): The other Cell to check equality with.
"""
pass # Your code here.
def __repr__(self):
"""Returns a representation of the cell, useful for printing/displaying
in notebooks.
"""
# Do not modify this method!
return f"Cell(x={self.x}, y={self.y}, alive={self.alive})"
✅ Question 2.2 (4 points): Run the following code cell to show your Cell class passes the following tests. Add (at least) one more test for correct behavior and show your test passes using assert similar to the provided tests. (Note that the syntax assert statement raises an error if statement is False, and otherwise does nothing. This is both an intuitive and powerful way to test code.)
cell = Cell(0, 0, alive=True)
assert cell.x == 0
assert cell.y == 0
assert cell.is_alive()
cell.kill()
assert not cell.is_alive()
cell.live()
assert cell.is_alive()
copy = cell.copy()
assert copy == cell # Note: The Python syntax `a == b` is shorthand for calling `a.__eq__(b)`.
assert copy is not cell
# Your code here. (Add another test for correctness with the Cell class.)
✅ Question 2.3 (16 points): Complete the following Board class provided the template and docstrings. This class consists of a collection of Cells and represents the ABM. Some methods are completed for you. You may add data or attributes if convenient, but you must not remove or change any given attributes or methods from the template.
Note: You are strongly encouraged to implement methods from first to last as organized in the class, implementing one method at a time and carefully checking your code. Subsequent questions provide tests which can be used to check correctness.
# Complete the following class!
import matplotlib.pyplot as plt
from matplotlib.patches import Patch
class Board:
def __init__(self, cells):
"""Initializes a Board.
Args:
cells (list[Cell]): A list of Cell's.
"""
# Do not modify this method!
self.cells = {}
for cell in cells:
self.add_cell(cell)
def add_cell(self, cell):
"""Adds a new Cell to the board. Does not return a value.
Args:
cell (Cell): The new cell to add to the board.
Raises:
ValueError: If the board already contains a Cell at the provided Cell's location.
"""
# Do not modify this method!
if (cell.x, cell.y) in self.cells.keys():
raise ValueError(
f"Board already has a cell at the same location of the provided {cell}."
)
self.cells[(cell.x, cell.y)] = cell
def get_cell_at(self, x, y):
"""Returns the Cell located at (x, y) on the Board if there is one, else returns None.
Args:
x (int): The x-coordinate of the Cell to get.
y (int): The y-coordinate of the Cell to get.
"""
pass # Your code here.
def get_cells(self):
"""Returns a list of all Cell's on the Board."""
pass # Your code here.
def get_alive_cells(self):
"""Returns a list of Cell's on the Board which are alive."""
pass # Your code here.
def copy(self):
"""Returns a copy of the Board - that is, a new Board with a copy of all Cell's in the current board."""
pass # Your code here.
def get_neighbors(self, x: int, y: int):
"""Returns the neighboring Cell's at the provided (x, y) location on the Board.
There are eight potential neighbors of the point (x, y), shown in the following diagram
(excluding the center (x, y) point):
|----------------------------------------------|
| (x - 1, y + 1) | (x, y + 1) | (x + 1, y + 1) |
|----------------------------------------------|
| (x - 1, y) | (x, y) | (x + 1, y) |
|----------------------------------------------|
| (x - 1, y - 1) | (x, y - 1) | (x + 1, y - 1) |
|----------------------------------------------|
Args:
x (int): The x-coordinate of the Board.
y (int): The y-coordinate of the Board.
Returns:
A list of neighboring Cell's.
Examples:
```python
board = Board([Cell(-1, 0), Cell(0, 0), Cell(1, 1)])
board.get_neighbors(0, 0) # [Cell(x=-1, y=0, alive=False), Cell(x=1, y=1, alive=False)]
board.get_neighbors(-1, 0) # [Cell(x=0, y=0, alive=False)]
board.get_neighbors(2, 2) # [Cell(x=1, y=1, alive=False)]
board.get_neighbors(10, 10) # []
```
"""
pass # Your code here.
def get_alive_neighbors(self, x, y):
"""Returns the alive neighboring cells at the (x, y) location on the Board.
Args:
x (int): The x-coordinate of the Board.
y (int): The y-coordinate of the Board.
Returns:
A list of neighboring Cell's which are alive.
Note: See Board.get_neighbors for an explanation of neighbors.
"""
pass # Your code here.
def run(self):
"""Advances the simulation by one time step, modifying the cells of the board.
Does not return a value.
Update rules:
1. Any live cell with fewer than two live neighbors dies, as if by underpopulation.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by overpopulation.
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
"""
pass # Your code here.
def show(self, alive_color="green", dead_color="white", markersize=500, xlim=None, ylim=None):
"""Plots the state of the board.
Args:
alive_color (str): Color for alive cells.
dead_color (str): Color for dead cells.
markersize (int): Size of markers.
xlim (tuple(int)): The x limits for the plot.
ylim (tuple(int)): The y limits for the plot.
"""
# Do not modify this method!
for cell in self.get_cells():
plt.scatter(
cell.x,
cell.y,
marker="s",
s=markersize,
color=alive_color if cell.alive else dead_color,
edgecolor="black",
zorder=2,
)
plt.legend(
handles=[
Patch(facecolor=dead_color, edgecolor="black", label="Dead cell"),
Patch(facecolor=alive_color, edgecolor="black", label="Alive cell")
],
bbox_to_anchor=(1.25, 1)
)
plt.grid()
if xlim:
plt.xlim(xlim)
plt.xticks(range(xlim[0], xlim[1] + 1, 1))
if ylim:
plt.ylim(ylim)
plt.yticks(range(ylim[0], ylim[1] + 1, 1))
✅ Question 2.4 (2 points): The first test of your Board class is to initialize and show a board. Create a simple Board with an alive cell at (0, 0), a dead cell at (0, 1), and an alive cell at (1, 1). Use the show method to show that your board is correct.
# Your code here.
✅ Question 2.5 (6 points): Using the provided random state (Don’t change this!):
Create a
BoardwithCells at locations (x, y) for all \(x\) in the range 0 to 10 and for all \(y\) in the range 0 to 10. (This means there should be 100 totalCells.)Run the simulation for 32 iterations and show the board after each iteration, putting the title “Timestep t” (where t is the current timestep) on the plot. Note that code is provided for you to clear and update the figure from one timestep to the next.
There should be four alive cells remaining at the end of the simulation. Will these cells stay alive forever? Why or why not?
import time
import numpy as np
from IPython.display import display, clear_output
rng = np.random.RandomState(1)
# Your code here to initialize the board.
fig, ax = plt.subplots()
for t in range(32 + 1):
# Your code here to update and show the board.
# After calling Board.show, run the following lines of code to make the animation smooth.
clear_output(wait=True) # Clear output for dynamic display
display(fig) # Reset display
fig.clear() # Prevent overlapping and layered plots
time.sleep(0.1) # Wait a certain amount of time before showing the next plot. You can modify this as appropriate.
✎ Your answer here.
✅ Question 2.6 (4 points): There are several configurations which persist indefinitely in Conway’s game of life. One of them is a “blinker”. Create a three by three array of cells with only the middle row alive. Advance the simulation ten time steps and show that the pattern repeats every two time steps.
# Your code here.
✅ Question 2.7 (4 points): Other configurations travel across the board. One of these is a “glider”. Create a square ten by ten array of cells with coordinates (0, 0), (0, 1), …, (0, 9), (1, 0), (1, 1), …, (1, 0), …, (9, 0), (9, 1), …, (9, 9). All cells should be dead except those with coordinates (0, 7), (1, 7), (2, 7), (2, 8), and (1, 9). Run the simulation and show that your glider advances from the top left to the lower right, retaining the same configuration. How many timesteps does it take for the glider to reach the lower right with the same shape as the initial glider? Set the total number of timesteps to this number.
# Your code here.
✅ Question 2.8 (6 points): If your simulation exhibits the correct behavior for the previous two questions, it’s likely (though not guarunteed) that your implementation is correct. Now, we can study behavior for random initial configurations.
Given the following random state, board dimensions (xdim and ydim), and total number of time steps, do the following.
For each initial probability of a cell being alive \(p\) in the given list:
Create the board where each cell is alive with probability \(p\).
Then, for each time step:
Record the fraction of cells alive.
Advance the simulation.
Make a plot of fraction of cells alive (vertical axis) vs time step (horizontal axis), with one curve for each probability \(p\).
import numpy as np
rng = np.random.RandomState(1)
xdim = 20
ydim = 20
time_steps = 100
alive_probabilities = [0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6]
# Your code here.
✅ Question 2.9 (4 points): Interpret your results from the previous question:
What values of \(p\) have the highest fraction of alive cells throughout the simulation? Does this make sense based on the rules of Conway’s game of life?
Do all curves tend to zero? Why or why not?
✎ Your answer here.
🛑 STOP#
Pause to commit your changes to your Git repository!
Take a moment to save your notebook, commit the changes to your Git repository using the commit message “Committing Part 2”, and push the changes to GitHub.
Part 3: Graph theory with transportation data (45 points)#
In this part of the homework, we will look at a dataset which contains the whole UK public transport system for a week in October 2010 [1, 2, data file]. We will model this data as a graph where each team is terminal where travel starts/stops is a node. We will later add directionarlity to capture the departure arrival relationship, and weights on edges that represent travel time.
✅ Question 3.1 (3 points): Go to this website and download the full data set. Unpack the .zip file into your working directory. The data we need is in the folder Data_Release_v1.11. After you unzip the folder, you will see edges.csv and nodes.csv, plus some other files. The former two are the ones we will primarily work with here.
Do This: Load the nodes.csv and edges.csv in this file into Pandas DataFrames. Display the first few and last few rows of each.
# Your code here.
Now, you will construct a graph of the nodes (stops).
✅ Question 3.2 (5 points): Create an empty (undirected, unweighted)Graph object from the networkx package. For each row of the DataFrame where both the destination and origin are associated to “Rail,” i.e., the integer 2 in both ori_layer and des_layer of edges.csv, add an edge between the origin (ori_node) and the destination (des_node) nodes.
# Your code here.
Plotting the graph.
✅ Question 3.3 (5 points): Plot the graph using the latitude and longitude of each node as its position, labeled by the columns lat and lon, respectively in nodes.csv.
# Your code here.
Next, you will construct the weighted directed graph to represent this data.
✅ Question 3.4 (5 points): Create an empty DiGraph object from the networkx package. For each row of the DataFramewhere both the destination and origin are associated to “Rail,” i.e., the integer 2 in both ori_layer and des_layer of edges.csv, add a directed edge from the node corresponding to the origin node (ori_node) to the destination_node (des_node).
For directed graphs, the parameter weight can be used to specify the weight of each edge. Use the kilometers distance (km in edges.csv) between the origin and destination nodes as the weight for each edge.
Note: Remember that each edge in a directed graph has an orientation. So adding an edge from node A to node B is not the same thing as adding an edge from node B to node A.
# Your code here.
✅ Question 3.5 (5 points): Plot the directed graph using the spring_layout option, not the spatial coordinates you used in 3.4., for nodes’ positions.
# Your code here.
✅ Question 3.6 (5 points): When making travel plans for individuals and freight, it is often helpful to find the shortest path from origin to destination stations. Write code that identifies the shortest path between two points and then prints out the ID for each of the nodes along the path.
Specifically, make a function that takes in the directed graph that you created along with two nodes representing the origin and destination stations, and then prints a sequence of statements of the form “Take [origin_nodeID] to [destination_nodeID]” which can be used to make travel plans along the shortest path from the origin to the destination`. For multiple transitions, the code must print out the sequence of statements “Take [origin_nodeID]{i} to [destination_nodeID]{i+1}”.
Make sure to include an error in case a path does not exist between the requested source and origin. See the documentation on Exceptions in networkx to find an appropriate exception to raise.
# Fill out the following function.
def find_itinerary(digraph, origin_nodeID, destination_nodeID):
pass
# Use this command to test your code.
find_itinerary(DG, origin_nodeID=1, destination_nodeID=169164)
🛑 STOP#
Pause to commit your changes to your Git repository!
Take a moment to save your notebook, commit the changes to your Git repository using the commit message “Committing Part 3”, and push the changes to GitHub.
Congratulations, you’re done!#
Submit this assignment by uploading it to the course Desire2Learn web page. Go to the “Homework Assignments” folder, find the dropbox link for Homework #2, and upload your notebook there.
© Copyright 2025, Department of Computational Mathematics, Science and Engineering at Michigan State University