In-class Assignment: Graph Theory and Cell Towers

In-class Assignment: Graph Theory and Cell Towers#

Day 11#

CMSE 202#

In this assignment you will work with your group to develop a program to use a color graphing algorithm to select frequencies for cell towers around MSU. There are four major parts to this assignment. Try to make sure you get through all of it, but don’t stress too much if you don’t finish.

Agenda for today’s class:#

Part 1: Download and import the data
Part 2: K-nearest neighbor graph
Part 3: Greedy graph coloring
Part 4: Plotting towers and their colors on a map

✅ Put your name here
#

✅ Put your group member names here
#

Problem Statement#

As was presented in the pre-class assignment, the signals from different cellphone towers that are close together can interfere.

From: http://www.onlivespot.com/2011/08/dido-wireless-technology-explained.html

In order to avoid this overlap cell phone companies use different frequency ranges in the Electromagnetic spectrum. Two towers that are close together but have differences in frequencies (shown as colors, red/green/black in the following figure) do not cause nearly as much interference.

From: http://www.onlivespot.com/2011/08/dido-wireless-technology-explained.html

However, cellphone towers are never distributed in such an even pattern. Consider the following map which shows the location of cell towers around Michigan State.

From: http://www.antennasearch.com/

Another problem is that cellphone companies have to pay for each frequency range they use. So they would like minimize the number of frequencies that they need to purchase while also minimizing the interference between the cell towers.

In this assignment you are going to work as a group to solve this problem using graph coloring.

Part 1: Download and import the data#

We will be using antenna data from the following website:

http://www.antennasearch.com/

✅ Do This: We previously downloaded a CSV file from this website for all of the towers in a 3 Mile radius from the MSU engineering building (428 S Shaw Lane, East Lansing, MI 48824). You can download this file from here:

https://raw.githubusercontent.com/msu-cmse-courses/cmse202-supplemental-data/main/data/TowersYYH730463QHM18572.csv

Make sure that the downloaded file is in the same directory as your in-class notebook.

Optional: Feel free to try running the same search and take a look at just the towers. When you start to visualize the data in the file we’ve shared you can see if any new towers have been added since the data was last pulled.

Finall, write a function to load the file into Python and generate a list of latitude and longitude for the towers.

# Put your function here!

✅ Do This: Generate a plot similar to the following showing the towers on the x-y plane.

# Put your plotting code here.

✅ Question 1: By default matplotlib.pyplot.scatter will scale the x-axis and y-axes to best fit the points. However, sometimes (as is the case here) we want the scaling of both axes to be equal. What command can you use for the above plot to ensure that the distances are the same in the x-direction as the y-direction?

✎ Do This - Erase the contents of this cell and replace it with your answer to the above question! (double-click on this text to edit this cell, and hit shift+enter to save the text)

Part 2: Generating a K-Nearest Neighbor Graph#

In the pre-class assignment, you were asked to try and write an algorithm that found the nearest neighbor for every point in a collection of points. There’s not necessarily one right way to solve this problem, so your solution might have looked quite a bit different this (or perhaps you didn’t quite get things working), but here’s one possible solution:

# Possible solution for the nearest-neighbor algorithm
import math
def distance(p1,p2):
    '''Returns the distance betwen two numpy points'''
    return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
    
def nearest_neighbors(points):
    '''Generates an adjacency list based on the Nearest neighbor graph algorithm.'''
    G = dict()
    for p in range(0,len(points)):
        min_distance = np.inf
        min_point = -1
        for n in range(0,len(points)):
            if p != n:
                d = distance(points[p], points[n])
                if d < min_distance:
                    min_distance = d
                    min_point = n
        if min_point == -1:
            print("ERROR-point not found")
        G[p] = [min_point]
    return G

But what if we wanted to find the nearest 2 neighbors? The nearest 3? More?

✅ Do This: Next write a function that generates a graph using the k-nearest neighbor graph algorithm. More information about the nearest neighbor and k-nearnest neighbor algorithm can be found here:

https://en.wikipedia.org/wiki/Nearest_neighbor_graph

The KNN graph is very similar to the nearest neighbor graph you did in the pre-class assignment. However, now instead of only finding the closest point to each point you find the k-closest points.

Important note: While the nearest-neighbor and KNN problems are similar, the same approach may not work well for both solutions! You should think this through and talk about it with your group. How will you tackle this problem?

# Put your k-nn function here

✅ Do This: It is important to test code. How do you know if your K-NN algorithm is working? Trying writing a function that tests if your code is right. Try changing the inputs and the values for k and make sure it behaves correctly. One important test would be ensuring it works when k=1 as this should reproduce the nearest neighbor graph.

# Put some testing code here

✅ Do This: Using the tower locations from Part 1, generate a figure similar to the following:

While the above graph displays the network, clearly not a lot of attention was given to the aesthetics!

# Put the code that makes your cell tower plot here

Part 3: Greedy Graph Coloring#

Next we will run a greedy graph coloring algorithm on your K-NN graph with k = 3 and plot the towers in the x-y plane colored to match the frequency selected. For example:

✅ Do This: Using networkx, apply the “greedy” graph coloring algorithm to the K-NN graph (K=3) developed in part 2 of the tower data downloaded in part 1.

# Plot your colored cell tower graph here.

Part 4: Plot tower colors on a map#

Finally plot the towers on a map and set the marker colors to your individual frequency colors. Something like the following:

Note: In order to overlay the tower locations as points on map, you’ll like need to find a python package that can help you do this. We explored some such options in a previous class period!

✅ Do This: First, write some test code to generate a map with colored points using whatever package you chose to use.

#Put your test code here

✅ Do This: Finally, put it all together. Generate a map with markers colored based on the frequencies selected in the graph coloring algorithm in part 3. Use the K-NN graph with k=3 generated from part 2 of the tower data downloaded from part 1.

# Put your map code here

Congratulations, we’re done!#

Now, you just need to submit this assignment by uploading it to the course Desire2Learn web page for today’s submission folder (Don’t forget to add your name in the first cell).