Homework answers / question archive / CE204 Programming Assignment 2, 2021/22 Academic offences warning You may not use any libraries except for the standard Java runtime, i

CE204 Programming Assignment 2, 2021/22 Academic offences warning You may not use any libraries except for the standard Java runtime, i

Computer Science

Share With

---

CE204 Programming Assignment 2, 2021/22

Academic offences warning

You may not use any libraries except for the standard Java runtime, i.e., libraries that are imported using import java.[something]. The work that you submit must be your own. It is an academic offence to submit somebody else’s work as your own. This includes submitting code that you have downloaded from the internet and code that was produced in collaboration with another student, even if you have modified this code. You may study internet resources, textbooks, etc. but the code you submit must be written by you, not taken from or modified from these resources. For details, please consult the University’s guidance or ask me.

Introduction

This assessed exercise constitutes 10% of your grade for CE204. The assignment is about graph algorithms. You will generate random graphs, check whether graphs are connected, and construct minimum spanning trees. You should represent graphs using the MatrixGraph class from lectures. Do not modify this class.

1. Setting up (5%)

Create a class called MST. Add a method static Graph getRandomGraph(int n) which creates a randomly weighted undirected graph with n vertices. The graph should contain every possible edge, and each edge should have a randomly chosen double weight between 0 and 10.

2. Total edge weight (15%)

Add a method double getTotalEdgeWeight (Graph g) which returns the total weight of the edges in g. The method should work correctly for both directed and undirected graphs.

(You could test your method for undirected graphs using the GraphOfEssex class, but you are not required to do this.)

1. 1. Connectivity (25%)

Write a method static boolean isConnected (Graph g) which determines whether the given graph g is connected. Use breadth-first search – mark the vertices that have been

1

visited and, at the end of the search, check that every vertex is visited. You should avoid adding any vertex to the queue more than once.

You may use Java’s ConcurrentLinkedQueue<Integer> for the queue, for which you’ll need to import java.util.concurrent.*. Note that this class uses the name “poll” for the operation that I called remove in the lectures.

3. Minimum spanning trees (25%)

Write a method static void makeMST (Graph g) which replaces the graph g with its minimum spanning tree computed in the following way:

create a list of the graph’s edges, in decreasing order of weight; for each edge in turn, delete that edge from the graph if the resulting graph is connected.

The resulting graph is a minimum spanning tree.^[1]

Your code may assume that the input graph g is connected.

I have supplied the file Edge.java, which you may use and adapt if you wish. If you do use this class, please include its source in the file MST.java. You may use Java’s standard list classes, and you may use Collections.sort() to sort the list.

4. Test code (20%)

Add a main method to your class. It should perform the following tests.

1. Compute the MST of the graph of Essex from lectures, using the class GraphOfEssex which I have supplied. Check that the MST has weight 95.
2. Compute the MSTs of 20 random graphs with 100 vertices each, created with getRandomGraph(). Compute and print the average weight of these MSTs. (The answer should be between about 11.2 and 12.5.)

Submission

Please submit only the file MST.java to Faser. Please do not submit a zip file. If you have written extra classes as part of your solution or used the Edge class, please include them in the same file as the main class. Please do not modify the MatrixGraph and GraphOfEssex classes, and please do not include those files in your submission.