Project 2: Contact Tracing through Graphs
Project 2: Contact Tracing through Graphs
Introduction
You need a way to trace the cause of disease outbreaks as the occur within a community. To do this, you decide to build a back-end system for modelling the community and the contacts each member has. The idea is to provide a structured model of the community, so that you can trace the infectious community members and find the original source of an outbreak. As the community contains members who have multiple contacts, you decide that the best way to model this structure is to use a graph, with people as the vertices, and the edges representing the social contacts that each person has. You decide this will be the social graph, modelling the close contacts of individuals as an undirected, weighted graph.
You are also interested in tracing the spread of disease through a community in the locations where people may interact with those outside of their immediate social circles. To investigate this, you decide that you should add businesses and organizations to your model. You want to see how an outbreak could spread, and a directed graph seems like a great way to model this. This will be the business graph, which will model the way that people can spread a disease via businesses, in addition to their close social contacts.
In this assignment, you will implement two graph structures: one undirected (the social graph), and one directed (the business graph).
In the social graph, each graph vertex will represent a Person, and will contain information about that person, including their name, age, and an ArrayList of social contacts (representing edges to other People). The graph structure will be an undirected, weighted graph. The weights will be the infectiveness of the individual, which is a value you will calculate using a combination of the Person’s age and Social Hygiene -- a value that represents the degree to which the person will seek to distance themselves, wash their hands, use masks, etc.
In the business graph, the graph will contain both Business and Person objects. Each Business will have a list of Persons, and each Person will have a list of Businesses. This will represent a directed graph, so these lists will be asymmetric (a Person in the list of a Business may not have that Business in their own list).
You will implement two algorithms to search through these graphs: breadth-first search, and depth-first search. Using these algorithms, you will implement several different searches through the graph.
There are three parts to this assignment. In Part A, you will set up the basic class structure and ensure the provided test suite is able to run without error. In Part B, you will implement the basic structures needed to model and search the social graph. In Part C, you will implement the structures needed to model and search through the business graph.
You are free to add your own methods and fields to any of the classes in the ds.graph package, but do not change any existing method prototypes or field definitions.
You have been provided with the setup of the SocialGraph. You will need to create tests for the methods that you implement, but you can use the structure provided in the SocialGraphTest as a basis for testing your Graph. The creation of tests forms part of your marked submission.
It is suggested that you complete the assignment in the order outlined in the following sections.
Marking
In addition to the marking scheme outlined, some marks are allocated to code style (including commenting) and appropriate complexity/performance (are you doing loops or repeated operations where they are not needed). Your code’s performance does not need to be perfect, however having additional variables where not used or needed, or loops that are not required will lose you marks. Focus on the core task and ensure you code enables that.
Importing into eclipse
The Assignment has been provided as an eclipse project. You just need to import the project into an existing workspace. Make sure that your Java JDK has been setup. This can be found in Project → Properties → Java Build Path → Libraries.
Part A: Setting up the Social Graph
After importing the project, you will see that the provided tests do not work. That is because you are required to implement the classes used in this assignment. Once the classes and required methods have been added, the tests will begin to run.
Person
The Person class represents one individual within the Social Graph. It holds a name, a float representing the individuals social hygiene value (a percentage, stored as a number between 0 and 1). Within the Social Graph, the Person is a Vertex. The Social Graph is implemented using an adjacency list, so each vertex has a list of vertices it is associated with. In the Person class, this is implemented as a variable of type ArrayList<Person>, called contacts.
You need to implement the following attributes of the Person class:
float | socialHygine |
int | age |
String | name |
ArrayList<Person> | contacts |
Float | getInfectiveness |
You must also implement a method to calculate the Persons infectiveness. This is a float between 0 and 1, representing how infective a person is. Implement the ‘getInfectiveness()’ method within the person class, which should return a float between 0 and 1. To calculate this value take the person’s age divided by 100 then subtract this from their social hygiene multiplied by their age/100.
In addition, you must implement accessor methods for these properties, and equals() and hashCode() methods. Two Persons are equal if their names are the same. Finally, you must implement a toString() method, which should take the format:
Person: <Name>, <age>. Contacts: <length of contacts list>.
SocialGraph
The SocialGraph class represents the social graph. This is an undirected, weighted graph using Persons to represent the vertexes of the graph. Edges are represented by the Person list contained in each of the vertices.
The SocialGraph class has a list of all the vertices within the graph. This is stored as an ArrayList<Person> called vertices.
You need to add the ArrayList<Person> attribute to the SocialGraph class.
Exceptions
You will need to add several exception classes to the project. These should extend Exception. The @throws annotations in the SocialGraph will indicate the exceptions that should be added.
Part B: Implementing the Social Graph
You need to implement the methods in the SocialGraph class:
1. addVertex(Person p). Add the given person to the graph. The person needs to be added to the list of vertices.
2. removeVertex(Person p). Remove the given Person from the graph. Any edges to this person (contained in other Person objects) should also be removed.
3. addEdge(Person a, Person b). Add an edge between the two people (vertices) in the graph. The graph is undirected, so both People will need to list the other, in their list of contacts.
4. removeEdge(Person a, Person b). Remove the edge between the given People from the graph.
Now that you have got the base graph set up, you can implement two searching algorithms. These two methods should consider the graph unweighted. In these algorithms, the order that the edges are traversed is based on the order of each Persons contact list. The first Person in the contacts list should be visited first, the second person second, etc.
1. searchBFS(Person start, Person target): Implement a breadth-first search, from Person start to target.
2. searchDFS(Person start, Person target): Implement a depth-first search, from Person start to target.
Two other methods should let you search the graph while including the graph weights. When selecting the order of edges to traverse, the weight of each edge should be considered, and the highest-weight selected first. Weight is based on the infectiveness of the Person the edge connects to, obtained via the Persons getInfectiveness() method.
1. searchWeightedBFS(Person start, Person target): Implement a breadth-first search, from Person start to target.
2. searchWeightedDFS(Person start, Person target): Implement a depth-first search, from Person start to target.
With these methods in place, you can explore the social graph to see the minimum number of steps between two Persons. The final aspect you want to examine is to find the total number of Persons, reachable within two steps from any particular start Person. You should implement this in the method:
1. countContacts(Person start). This method should return an int value showing the total number of contacts-of-contacts of the start person. (This is the equivalent to doing a BFS around the start person, and counting the vertices 2 steps away from the start node).
Part C: The Business Graph
The business graph is a weighted, directed graph that shows the Persons who are travelling to, and from, Businesses. Accurately modelling the transmission of an outbreak through businesses would require tracking the time that each Person enters and leaves that business, but this is a challenging task outside of the scope of this assignment. Instead, you have decided that you can model a snapshot of a society on a particular day. This will represent an infectious outbreak in progress.
The business graph will use Persons to represent the edges in the graph. The graph will have edges in and out of Businesses, representing Persons who are travelling into and out of those businesses.
You will implement the business graph in the BuisnessGraph class, using Persons as the edges. You will have to add some attributes and methods to the Person class to accommodate this.
Business
The Business class will represent a vertex in the Business graph. Each Business has a name and a list of edges, stored as an ArrayList<Person>, called edges.
The addEdge method will create an edge from one Business to another, via a Person. The persons infectiveness value is the weight for the edge. The Person will be stored in the starting Business’ edges list. The destination vertex does not store the edge.
When adding an edge to the Business, your addEdge method should check if there is already an edge to that destination. If there is, the highest weighted edge is used – the original edge is replaced if the new edge’s weight is greater than the originals.
You will need to implement the following methods:
void | addEdge(Business dest, Person route) |
void | removeEdge(Business dest) |
Person
The Person class needs to have an additional attribute, the destination business, added. This should be of type Business. Additional methods will also be required:
void | setBusiness(Business bus) |
Business | getBusiness |
The Person toString() should be updated to include the name of the Business, or to clearly indicate that the Person does not have a Business set.
BusinessGraph
The business graph class, BusinessGraph, should store the vertices in an ArrayList<Business>, called vertices.
You will implement both a BFS and DFS to search the business graph. The weight of the edges should be considered when selecting an edge to traverse.
You are interested in the Persons that are infected when travelling the graph.
The goal of the BFS in the BusinessGraph is to find the total number of Persons infected, up to three Businesses away from the Business with the initial outbreak.
You will implement two methods using a DFS in the BusinessGraph:
1. Find the minimum number of steps required for an infection to reach the Destination Business, from the Starting Business. You will have to modify the DFS algorithm to accomplish this, as there is no guarantee that a DFS finds the shortest path.
2. Determine if the graph is strongly connected or not. The graph is strongly connected if there is a path from one node to every other node. The goal is to determine whether an outbreak in the start business will affect every other business, or whether there are some businesses that are disconnected (and thus protected from infection outbreaks).
You will need to implement the following methods. Your methods should throw appropriate exceptions where necessary.
void | addVertex(Business bus) |
void | removeVertex(Business bus) |
int | totalPersonsInfected(Business start) |
int | minStepsToDestFromStart(Business start, Business dest) |
bool | isStronglyConnected(Business start) |
