Assignment P5

Assignment P5#

This assignment uses regular Java 23, and JUnit Jupiter 5.9.0. You may optionally import the Functional Java Standard Libraries. Do not import other libraries into your project. Your code may not:

• Explicitly throw exceptions, or annotate methods with a throws clause, except where explicitly permitted
• Catch exceptions outside of the allowed pattern for reading/writing files (see Slides of Workshop 6B).
• Use concurrency (if you do not know what that is, you will not be using it so long as you write the code on your own).
• Use reflection (if you do not know what that is, you will not be using it so long as you write the code on your own).
• Interact with the environment outside of the file system operations described on the Slides of Workshop 6B.
• Write to or read from files other than described in the assignment.

In everything you do, you must follow the Design Recipe. The minor adjustments to the Design Recipe for class definitions are available in Slides of Workshop 6B To see roughly how this assignment will be marked, check out the Skeleton Rubric.

You still need to follow the Design Recipe and write appropriate documentation and tests. In particular, the (minor) adjustments to the Design Recipe for class definitions were covered in workshop 6B. Do not write code that is overly complicated.

Formalities#

This assignment is submitted via GitLab.

Access to Your Repository#

In order for us to be able to collect and mark it, you need to satisfy the following conditions:

• Your repository’s name must be comp6710-2025s1-p5 (exactly), placed directly in your user namespace (the default). That is, if your uid is u1234567, the address of your GitLab project should read as https://gitlab.cecs.anu.edu.au/u1234567/comp6710-2025s1-p5.
• Your repository must have our marker bot (comp1110-2025-s1-marker) added as a Maintainer.

You can achieve both these points by creating your project through forking our template repository and not changing the name, or by just using the correct name when creating the project and then manually adding the bot.

Notebooks and Push Requirement#

You need to keep a notebook file as explained on the Git and Notebooks page. You need to commit and push the current state of your files:

• at the end of every session where you work on the assignment
• at least once per hour (our checks implement this that no two pushes during sessions recorded in the notebook are more than 70 minutes apart).
• at least once per major part of the assignment (i.e. for this assignment, at least four times). You are absolutely free to commit and/or push more often than that.

You need to write informative commit messages, and informative notes for each session in your notebook, which describe what it is that you did for this particular commit or session, respectively.

Statement of Originality#

Your submission (and therefore your git repository) needs to include a signed statement of originality. This must be a text file named soo.txt. That file must contain the following text, with the placeholders [your name here] and [your UID here] replaced with your name and UID (remove the brackets!), respectively:

I declare that this work upholds the principles of academic
integrity, as defined in the University Academic Misconduct
Rule; is entirely my own work; is produced for the purposes
of this assessment task and has not been submitted for
assessment in any other context, except where authorised in
writing by the course convener; gives appropriate
acknowledgement of the ideas, scholarship and intellectual
property of others insofar as these have been used; in no part
involves copying, cheating, collusion, fabrication, plagiarism
or recycling.

I declare that I have not used any form of generative AI in
preparing this work.

I declare that I have the rights to use and submit any assets
included in this work.

[your name here]
[your UID here]

Files Summary#

Your repository must be accessible to us and must have the following structure:

• notebook.yml - your Notebook
• soo.txt - your signed Statement of Originality
• src - a folder containing your source files:
  • Graph.java - containing part of your work for parts 1, 2, and 4
  • ContactTracing.java - containing you work for part 3
  • AmbulanceDispatch.java - containing your work for part 5
• tests - a folder containing your test files:
  • GraphTests.java - containing your tests for your graph class
  • ContactTracingTests.java - containing your tests for part 3
  • AmbulanceDispatchTests.java - containing your tests for part 5

You may have additional files in src for additional classes, and additional files in tests for additional tests.

Project Configuration and Running Programs#

We recommend that you use IntelliJ IDEA for this assignment. However, you do not have to. If you do, the standard settings that result from following the IntelliJ Project Setup Guide should make your project work with our testing environment.

If you do not want to (or cannot) use IntelliJ IDEA, or if you want to make sure you can run your program like our automated testing framework, then you can follow the guide available here. This will allow you to trigger your tests directly from the console, in a similar way we did in the first half of the course with the functional Java library support for tests.

Info: Java Standard Libraries#

Part of this assignment asks you to do things for which there are operations in the Java Standard Libraries. Consider particularly looking at the following pages:

• List
• Queue
• PriorityQueue
• File
• Function
• HashMap

Special Comment Requirement: Complexity#

Some methods you are required to implement for this assignment require you to analyse the worst-case time complexity of your code. Such a requirement is typically phrased as follows:

Analyse the worst-case time complexity of your implementation in terms of |V| as the number of vertices and |E| as the number of edges in the graph.

A prompt may include different variables, depending on the particular inputs. You may be given more variables than are needed to express the complexity of your method - if a particular variable does not factor into the worst-case bound, omit it.

Where you are required to analyse the worst-case time complexity of your code, do so and document your finding in the comments of your method, right below the design strategy. For example:

/**
 * Creates a new copy of the given list.
 * Examples:
 * - Given: []
 *   Expect: [] as a different object from given list
 * - Given: [1,2,3]
 *   Expect: [1,2,3] as a different object from given list
 * Strategy: Iteration
 * Time Complexity: O(n), where n is the size of the given list
 * @param list - the list of which to create a copy
 * @return a new copy of the given list
 */
public static <T> List<T> copyList(List<T> list) { ... }

Steep mark penalties apply if you omit the time complexity documentation where required.

Tasks#

As a a general rule in this assignment, you do not need to come up with examples or write tests for methods whose name starts with “get”, except if you have some logic in them beyond just returning a field variable of the class. You may of course use them in your tests of other methods. We note that depending on how you to decide to internally layout data inside your class implementations, you may indeed have some “get” methods with some logic inside.

In the non-distinction level part of the assignment, we will work with directed simple graphs. In directed graphs edges have a direction, i.e., a source vertex from which the edge departs, and a target vertex to which the edge points. Simple graphs do not have multiple edges from the same source to the same target, or self-edges from some vertex to itself. No data is associated with edges (in particular, there are no weights), but vertices have data associated with them (e.g. the name of a vertex).

You will have to be able to read graphs from files, whose format consists of three sections:

• The first section is a single line (the first line of the file), which contains an integer indicating number of vertices in the graph.
• After the first line, we have a second section of the file with as many lines as vertices (given by the integer in the first line). Each of these lines contains a string representation of the data that the corresponding vertex of the graph stores.
  Each vertex is implicitly assigned a unique integer identifier starting from 0 up to numVertices-1. The vertex identifiers are assigned following the order of the lines in the file. Thus, the second line in the file corresponds to the vertex with identifier 0, the third line of the file to the vertex with identifier 1, and so on.
• After the vertices, we have a third and last section of the file with some number of additional lines, until the end of the file. Each line contains two integer numbers separated by a single space. These integer numbers denote the vertex identifiers of the two vertices that the edge connects. The first number indicates the source vertex, whereas the second number indicates the target vertex of the edge.

You can assume that:

1. The first line contains an integer, i.e., Integer.parseInt won’t throw an exception when processing the characters of the first line.
2. The second section of the file must have as many lines as the number provided in the first line.
3. The lines of the second section of the file must have at least one character different from the \n character, i.e., they cannot be empty.
4. There cannot be self-edges, i.e., edges where the two connecting vertex identifiers match.
5. There cannot be repeated edges in the file.
6. The edges in the file always refer to vertex identifiers within valid bounds.
7. The edges in the file might be listed in an arbitrary order.
8. Two different vertices may have the same value, and thus there might be different edges that connect vertices with the same value.

An example simple directed graph, along with its file representation, is provided below:

9
A
B
C
L
D
X
M
G
A
1 0
2 1
3 0
1 4
5 2
3 1
5 1 
3 4
4 5
3 6
4 7
8 5
3 7
5 7
7 6
7 8

Part 1#

In the file src/Graph.java

Part 1 is a regular part of the assignment and will be included in marking it. However, it is designed as an on-ramp. Tutors may help you with the code here if you ask for help - though you should still try to do as much as possible yourself.

Design a generic class called Graph<T> to model simple directed graphs, according to the specifications below. The type parameter T is used to denote the type of the values stored within each graph vertex. You must design at least the following members, as these are the ones that we will subject to automatic testing:

// Here, File refers to java.io.File, 
// List to java.util.List and Function
// to java.util.function.Function. 
// Make sure to use to right import!

/**
 * Returns the number of vertices in the graph.
 */
public int getNumVertices()

/**
 * Returns a List<Vertex<T>> with the vertices of 
 * the graph. Vertex<T> is the name of the class that 
 * you need to design to represent graph vertices. 
 * More details on Vertex<T> below. The position
 * of a vertex within this list must match with its
 * vertex identifier.
 */
public List<Vertex<T>> getVertices()

/**
 * Returns the number of edges in the graph.
 */
public int getNumEdges()

/**
 * Returns a List<Edge<T>> with the edges of 
 * the graph. Edge<T> is the name of the class that 
 * you need to design to represent graph edges. 
 * More details on Edge<T> below.
 */
public List<Edge<T>> getEdges()

/**
 * Given a text file in the above format,
 * and a function that converts Strings
 * to values of type T, returns a 
 * Graph<T> instance that holds
 * the information stored in the file.
 */ 
public static <T> Graph<T> readGraph(
   File file, 
   Function<String, T> stringToT);

/**
 * Returns a list with the identifiers of all vertices that 
 * have maximum outgoing degree in the graph. The outgoing 
 * degree of a vertex is defined as the number of edges that
 * depart a vertex. The vertices should be ordered by increasing 
 * identifier in the returned list.
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the number of vertices and |E| as the number
 * of edges in the graph.
 */
public List<Integer> maxOutgoingDegreeVerticesIDs();


/**
 * Returns a list with the identifiers of all vertices that 
 * have maximum incoming degree in the graph. The incoming 
 * degree of a vertex is  defined as the number of edges in 
 * the graph that point to the vertex.The vertices should be 
 * ordered by increasing identifier in the returned list.
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the number of vertices and |E| as the number
 * of edges in the graph.
 */
public List<Integer> maxIncomingDegreeVerticesIDs();


/**
 * Returns how many vertices in the graph have the given value
 * stored within them.
 */
public int countVerticesWithValue(T value);

/**
 * Returns how many edges in the graph connect vertices storing 
 * the given values. sourceVertexValue denotes the value of the
 * vertex from which the edge departs, while targetVertexValue
 * the value of the vertex to which the edge points to.
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the number of vertices and |E| as the number
 * of edges in the graph.
 */
public int countEdgesWithValues(T sourceVertexValue, 
                                T targetVertexValue);

Where you are prompted to analyse the worst-case time complexity of a method, do so following the instructions above.

As mentioned above, you must also design the Vertex<T> and Edge<T> classes. These might be either in the same file as Graph<T>, or in separate files Vertex.java and Edge.java, respectively. Both approaches are valid for the assignment and may get full marks.

For Vertex<T> you must design at least the following members, as these are the ones that we will subject to automatic testing:

/**
 * Returns the vertex identifier.
 */
public int getID()


/**
 * Returns the value stored within the vertex.
 */
public T getValue()

/**
 * Returns a List<Edge<T>> with all the edges
 * the graph that depart from the vertex.
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the number of vertices, |E| as the number
 * of edges in the graph, and |O| as the number of edges that
 * depart from the vertex.
 */
public List<Edge<T>> getOutgoingEdges()

/**
 * Returns a List<Edge<T>> with all the edges
 * the graph that point to the vertex.
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the number of vertices, |E| as the number
 * of edges in the graph, and |I| as the number of edges that
 * point to the vertex.
 */
public List<Edge<T>> getIncomingEdges()

Where you are prompted to analyse the worst-case time complexity of a method, do so following the instructions above.

For Edge<T> you must design at least the following member, as these are the ones that we will subject to automatic testing:

/**
 * Returns the vertex from which the edge
 * departs.
 */
public Vertex<T> getSourceVertex()

/**
 * Returns the vertex to which the edge
 * points.
 */
public Vertex<T> getTargetVertex()

Follow the Design Recipe!

Part 2#

In the file src/Graph.java

Design the following method of Graph<T>:

/**
 * Given a value, compute the length of the shortest paths 
 * from the vertex of the graph storing such value (source vertex) 
 * to every other vertex of the graph (end vertex). Returns a map
 * with as many entries as vertices in the graph. 
 * For each entry, the key stores the value of the end vertex of 
 * the path, and the value stores the distance of the shortest path
 * between the source vertex and such end vertex. If there is no 
 * path from the source vertex to another vertex, the latter should
 * still be in the resulting map, with distance equal to -1, 
 * indicating that it is unreachable.
 * 
 * For simplicity you can assume: (1) there is a vertex
 * in the graph storing the given value. (2) the graph cannot have
 * two vertices with the same value.
 * 
 * You MUST use iteration to solve the problem (recursion is NOT
 * permitted).
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the number of vertices, |E| as the number
 * of edges in the graph.
 */ 
public Map<T,Integer> computeShortestPaths(T value);

Analyse the worst-case time complexity of the method, and do so following the instructions above.

Follow the Design Recipe!

Part 3#

In the file src/ContactTracing.java

In this part, we will work with a graph where the vertices store Strings representing people names, and the edges interactions between people. A mosquito bite infects a person in this graph. An infected person also infects another person if the former interacts with the latter.

People interactions are always bidirectional, i.e., that is if person named A interacts with another person named B, then B also interacts with A. We will model such interactions using the simple directed graph that we designed in Part 1. Thus, in such a representation, there will actually be two edges, one per direction, for every pair of interacting people. You can also safely assume that both edges will also be listed in the text file from which the graph is imported.

Create a class ContractTracing with the following two static methods:

/**
 * Given a Graph<String> representing interactions 
 * between people, and the name of a person that has 
 * been infected by a mosquito  bite, generate a list 
 * with the names of all people that have been infected.
 * The order of the names in the returned list does
 * not matter.
 * 
 * You MUST use recursion to solve the problem (iteration is not
 * permitted).
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the number of vertices, |E| as the number
 * of edges in the graph.
 * 
 * You can assume that:
 * (1) There is a person in the graph with the provided name.
 * (2) There cannot be two people in the graph with the same
 *     name.
 * (3) The graph may have several disconnected components,
 *     corresponding to different clusters of people that 
 *     may have not interacted with each other
 */
public static List<String> determineInfectedPeopleNames(
   Graph<String> interactions,
   String name)

/**
 * Given an Graph<String> representing interactions between
 * people, returns the minimum number of mosquito bites
 * required to infect all people in the graph.
 * 
 * You MUST use recursion to solve the problem (iteration is not
 * permitted).
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the number of vertices, |E| as the number
 * of edges in the graph.
 * 
 * The graph may have several disconnected components,
 * corresponding to different clusters of people that 
 * may have not interacted with each other.
 */
public static int minBitesForFullInfection(
   Graph<String> interactions)

Analyse the worst-case time complexity of the methods, and do so following the instructions above.

Follow the Design Recipe!

Part 4 (Distinction-Level Part)#

In the file src/Graph.java

In this part, and the following one, we will work with weighted simple directed graphs. In a weighted graph, each edge stores a non-negative integer number representing its weight.

Modify your Graph<T> and Edge<T> classes such that they also store the edge weights. For compatibility with the previous parts, the default weight should be 0. Besides, the following instance method must be added to the Edge<T> class:

/**
 * Returns an integer number with the 
 * weight associated to the edge. 
 */
public int getWeight()

The file format for graphs also needs to be extended to support weighted edges. To this end, the edge lines in the file are extended with a third column which contains the edge weight. The second and third columns are separated by a single space. You can also assume that there will be always three columns for each edge in the file, and that these columns will always store integer numbers. The weights will always be non-negative integer numbers.

An example weighted directed graph, along with its file representation, are provided below:

9
S
B
C
L
D
X
M
G
A
1 0 7
2 1 2
3 0 40
1 4 9
5 2 0
3 1 20
5 1 4
3 4 10
4 5 5
3 6 35
4 7 25
8 5 3
3 7 30
5 7 6
7 6 8
7 8 15

Add the following methods to the Graph<T> class:

/**
 * Given a text file in the above format,
 * and a function that converts Strings
 * to values of type T, returns a 
 * Graph<T> instance that holds
 * the information stored in the file,
 * including the edge weights. When writing 
 * this function, you should think how you
 * could reuse as much code as possible from
 * the readGraph function written above. You are
 * allowed to modify your implementation of readGraph 
 * if that helps you achieve this goal.
 */ 
public static <T> Graph<T> readWeightedGraph(
   File file, 
   Function<String, T> stringToT);


/**
 * Given a value, compute the weight of the minimum weight paths  
 * from a vertex of the graph storing such value (source vertex) 
 * to every other vertex of the graph (end vertex). 
 * The weight of a path is defined as the sum of all weights 
 * of the edges in the path.
 * 
 * Returns a map with as many entries as vertices in the graph. 
 * For each entry, the key stores the value of the end vertex of 
 * the path, and the value stores the weight of the shortest path
 * between the source vertex and such end vertex. If there is no
 * path from the source vertex to another vertex, the latter 
 * should still be in the resulting map, with weight equal to -1.
 * 
 * For simplicity you can assume: (1) there is a vertex
 * in the graph storing the given value. (2) the graph cannot
 * have two vertices with the same value.
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the number of vertices, |E| as the number
 * of edges in the graph.
 */ 
public static <T> Map<T,Integer> computeMinWeightPaths(
   Graph<T> weightedGraph,
   T value);

Analyse the worst-case time complexity of the methods, and do so following the instructions above.

Follow the Design Recipe!

Part 5 (Distinction-Level Part)#

In the file src/AmbulanceDispatch.java

In this part, we will leverage weighted graphs to represent locations in a city, and edges connecting two locations to denote how much time units it takes for an ambulance to arrive from the source to the end location of the edge. Due to the current status of the roads, it might be possible to go from a location A to a location B, but not the other way round. Also, assuming that it is possible to go both ways between two locations, the time in each way does not necessarily match.

Whenever an accident happens in a given location, the emergency services decide how many ambulances are required depending on the magnitude of the accident. Then, the emergency services need to locate the free ambulances that can arrive in the shortest time to the location of the accident.

Let us assume that each ambulance has a unique non-negative integer number. We have access to a map that, for every free ambulance, names the location of the ambulance. There might be by chance a free ambulance at the location of an accident.

Create a class AmbulanceDispatch and have it implement the following static method:

/**
 * Given the name of the vertex where an accident has occured,
 * the number of free ambulances required to handle the accident,
 * and the current locations of free ambulances, return a list 
 * of the ambulance identifiers that can arrive in the shortest
 * possible time to the location of the accident. If there are not
 * enough free ambulances, then the method should list the maximum
 * number of free ambulances that can reach the location of the
 * accident. If there are several ambulances that take the same time
 * to reach the location of the accident, but not all of them are needed,
 * the method arbitrarily decides which ambulances to be sent. The ambulances 
 * can be listed in arbitrary order.
 * 
 * Example: Given 
 *          the weighted graph above, 
 *          accidentLocation="G", 
 *          numberAmbulancesRequired=2,
 *          ambulanceLocations={1100:"B", 1730:"L", 1110:"A"}
 *          Expect:
 *            [1110,1100] or [1100,1110]
 *            (Note that 1110 would take at least 9 time units, 
 *             and 1100, at least 20 time units) 
 * 
 * For simplicity you can assume: (1) there is a vertex
 * in the graph with value equal to accidentLocation. 
 * (2) the graph cannot have two vertices with the same value.
 * 
 * Analyse the worst-case time complexity of your implementation
 * in terms of |V| as the number of vertices, |E| as the number
 * of edges in the graph, and |A| as the number of ambulances
 */ 
public static List<Integer> identifyAmbulances(
   Graph<String> locations,
   String accidentLocation,
   int numberAmbulancesRequired,
   Map<Integer, String> ambulanceLocations);

Analyse the worst-case time complexity of the method, and do so following the instructions above.

Follow the Design Recipe!

Updates#