lab_contact

Covid Contact

Due: Nov 18, 23:59 PM
Lab slides

Learning Objectives

  • Use and modify an adjacency list graph implementation
  • Implement BFS traversal on unweighted, undirected graphs
  • Solve real world problems (COVID contact tracing) using data structures

Setup

From your CS 277 git directory, run the following:

git fetch release
git merge --allow-unrelated-histories release/lab_contact -m "Merging initial lab_contact files"

Upon a successful merge, your lab_contact files are now in your lab_contact directory.

To deal with the fast spread Covid-19 pandemic countries used contact tracing to help people track when to isolate and get tested. Even UIUC Safer Illinois existed for this purpose. However, this is not that easy to do, especially on large datasets (and in the real world not every interaction is obvious). If we assume our data is good and contains every interaction, one way to solve this problem is using graph based BFS (breadth-first search).

Part 1: Create the graph

# INPUT:
# A string containing a vertex value (person name)
# OUTPUT:
# A list of interaction objects for the input vertex
List(interaction()) adj_list.getEdges(str name):

# INPUT:
# a string u, which is the name of a person
# a string v, which is the name of a second person 
# (the edge implies a connection between two people)
# You may assume both individuals are vertices
# You may assume both individuals are separate individuals
# OUTPUT:
# None -- the graph should be modified to contain an edge between individuals
# (As the edges are undirected, this requires setting parallel edges for both directions)
None addEdge(str u, str v):

To help better detect and alert at-risk individuals, you have been tasked with writing up a graph infrastructure capable of storing all interactions between individuals. Most of this infrastructure (the adj_list() class) has been provided but you must finish the implementation by implementing two functions – addEdge() and getEdge().

addEdge() should directly modify the adj_list object’s edge storage to contain both directions of the input edge. For example, an edge between two vertices “Brad” and “Harsh” should be stored in “Brad”’s edge list as (Brad -> Harsh) as well as in “Harsh”’s edge list as (Harsh -> Brad). It should also connect these two edge objects (interaction()) as each other’s parallel.

getEdge() is a more straightforward accessor function – given a vertex name, you should return the list of interaction() objects stored in that vertex. Dont overthink this function – you should already be storing a list of interaction objects, its just a matter of identifying how to look up a particular list given a string name.

Every time a person tests positive for Covid-19, we want to be able to rapidly identify the distance (in interactions) between the COVID positive individual and other people in our network. The first part to setting up this system is to implement a breadth-first search on our interaction graph so that we can identify these distances.

# INPUT:
# a string s, which is the name of the starting node in the traversal
# OUTPUT:
# None -- the graph should be modified so that each vertex has appropriate depth
#
# NOTE: You are strongly encouraged to add edge / vertex labels as necessary.
# However, as there are multiple correct solutions based on the order you visit nodes in 
# a graph, these values will not be tested by the autograder
None adj_list.BFS(str s):

Implement BFS based on the in-class implementation using a queue. You can use the deque data type imported at the top of the file or make or import a queue object used in previous lectures and assignments. While in class we discussed how to label both vertices and edges, you will only be graded on the value of depth at each vertex as those values will be consistent regardless of the order of vertices you visit.

You are strongly encouraged to also implement edge labeling and manually check that the labels match your expectations. To assist with this, some of the in-class examples have been provided in ‘graph’ input form of vertices and edges.

Part 3: identifyRisks

# INPUT:
# An adj_list() object, iGraph, storing all people in the interaction graph
# positive is a string label corresponding to a positive-tested individual
# n is an integer representing the degrees of separation (depth) we have to warn
# OUTPUT:
# A list of strings with the names (vertex labels) of at-risk individuals
def identifyRisks(iGraph, pos, n):

To fully implement our contact tracing and alert system, implement one final function which will cause BFS on a positive-tested individual (the starting vertex) and return a list of strings with the names of the at-risk individuals within a distance of n from the COVID individual. To be clear:

  • n = 1 should give the direct neighbors to the COVID individual
  • n = 2 should give the direct neighbors as well as the neighbors of those neighbors.
  • n = 3 should give the direct neighbors, the neighbors of those, as well as the neighbors of the 2nd degree neighbors.

The order that you output these neighbors won’t matter to the autograder but you must return all the at-risk individuals (and none of the individuals not at risk).