COMP2123
Assignment 4
S1 2024
This assignment is due on May 10. All submitted work must be done individu- ally without consulting someone else’s solutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.
Question 1 [20 pts]
Given an undirected graph G = (V, E) with n vertices and m edges, and a positive (not necessarily unique) edge cost ce for each edge in E. We are also given q pairs of vertices Q = {(u1, v1), . . . , (uq, vq )}. Decide for each pair (u, v) in Q if there is a path between u and v in G.
Task: Design an algorithm that solves this problem in O(q · (m + n)) time.
Implementation and Testing: Implement your algorithm (in Ed) and test it on the following graph instances: Graph8, Graph250, Graph1000. Each instance is given as a text file using the following format:
|
n
|
|
|
|
m
|
|
|
|
vertexId
|
vertexId
|
weight
|
|
vertexId
...
|
vertexId
|
weight
|
|
vertexId
q
|
vertexId
|
weight
|
|
vertexId
|
vertexId
|
|
|
vertexId
...
|
vertexId
|
|
For example, the text below describes the instance depicted in Fig. 1. Note that the vertices are numbered from 0 to n − 1 and that the two queries are (0, 1) and (0, 2).
4
3
0 2 2
0 3 5
2 3 3
2
0 1
0 2
Your program should read input from the text file. Your program only needs to print out ‘ 1’ (= yes, there is a pathin G between u and v) or ‘0’ (= no, there is no path connecting u and v in G) for each of the q query pairs. You should separate each 1/0 with a new line. A scaffold is provided for Python for you.
Your code will not be benchmarked or tested for time complexity, but for full points it must be able to run instances similar to ”Graph1000”, and each test will time out after 5 seconds. Your program will also be tested on several hidden test cases.
If the query is (0, 1) on the figure 1 below then the answer should be ‘0’ while the answer to the query (0, 2) on the same graph should be ‘1’ .
Figure 1: Illustrating the graph described in Question 1, with n = 4 and m = 3.
Question 2 [40 pts]
Consider the following variant of the Minimum Spanning Tree (MST) problem. We are given an undirected graph G = (V, E) with n vertices (numbered from 0 to n − 1) and m edges, a positive (not necessarily unique) edge cost ce for each edge in E, and a subset of edges A ⊂ E (note that A may contain cycles). Suppose that E represents a set of possible direct fibre links between vertices and A represents the existing set of direct fibre links between vertices. We would like to find the cheapest way to connect all the vertices into one connected network.
The abstract problem we are interested in solving is to find a subset X ⊆ E \ A of edges of minimum cost such that (V, X ∪ A) is connected.
Task: Design an algorithm that solves this problem in O(m log n) time.
Implement your algorithm (in Ed) and test it on the following instances: Graph8, Graph250, Graph1000. Each instance is given in a text file as described in Question 1.
Each graph instance is given in a text file using the following format (where a is the number of edges in A):
n
m
vertexId vertexId weight
vertexId vertexId weight
...
a
vertexId vertexId
vertexId vertexId
...
For example, the following text describes the instance depicted in Fig. 2. Note that the vertices are numbered from 0 to n − 1.
4
5
0 2 2
0 1 6
0 3 5
1 3 8
2 3 3
2
0 2
1 3
Your program should read input from a text file, and calculate the cost of the solution generated by your algorithm, that is, the cost of the edges in X ∪ A. Your program does not need to return the actual edges, just print out the total cost rounded to two decimal places to standard output.
Your code will not be benchmarked or tested for time complexity, but for full points it must be able to run instances similar to "Graph1000", and each test will time out after 5 seconds. Your program will also be tested on hidden test cases.
Figure 2: Illustrating the graph described in Question 2, with n = 4, m = 5 and a = 2. Showing an optimal solution having cost 13.