Module 14 Assignment: MST

Please solve below question. 5 codings should be created.

1. Edge.java

2. Graph.java

3. GraphAlgorithms.java

4. Vertex.java

5. VertexDistance.java

Below is questions.

Minimum Spanning Trees

Forthisassignment, you will be implementingPrim's algorithm for minimum spanning trees. This assignment has quite a few files in it, so please be sure to readALL of the documentation given to you.

IMPORTANT:

• You will be given 5 attempts on this assignment, with a 30 minute cooldown between submissions.
• Please run your code before each submission to ensure that there are no formatting errors! If there are formatting errors in your code, your code will not be graded and a submission attempt will be logged. For more information, please review the Vocareum overview below.

Graph Data Structure

Note: This section on the Graph data structure is the exact same as the one in the module 13 coding assignment.

You are provided aGraph class. The important methods to note from this class are:

• getVertices provides a Set ofVertex objects (another class provided to you) associated with a graph.
• getAdjListprovides a Map that mapsVertex objects to Lists ofVertexDistance objects. This Map is especially important for traversing the graph, as it will efficiently provide you the edges associated with any vertex. For example, consider an adjacency list map where vertex A is associated with a list that includes aVertexDistance object with vertex B and distance 2 and anotherVertexDistance object with vertex C and distance 3. This implies that in this graph, there is an edge from vertex A to vertex B of weight 2 and another edge from vertex A to vertex C of weight 3.

Vertex Distance Data Structure

In theGraph class, you will be using theVertexDistance class implementation that we have provided. This data structure is used by the adjacency list to represent which vertices a vertex is connected to. In Prim's algorithm, you should use this data structure along with aPriorityQueue.

Minimum Spanning Trees (MST - Prim's Algorithm)

A MST has three components. By definition, it is a tree, which means that it is a graph that is acyclic and connected. A spanning tree is a tree that connects the entire graph. It must also be minimum, meaning the sum of edge weights of the tree must be the smallest of all possible spanning trees.

By the properties of a spanning tree, any valid MST must have edges in it. However, since all undirected edges are specified as two directional edges, a valid MST for your implementation will have edges in it.

Prim's algorithm builds the MST outward from a single component, beginning with a starting vertex. At each step, the algorithm adds the cheapest edge connected to the incomplete MST that does not cause a cycle. Cycle detection can be handled with a visited set.

Self-Loops and Parallel Edges

In this framework, self-loops and parallel edges work as you would expect. If you recall, self-loops are edges from a vertex to itself. Parallel edges are multiple edges with the same orientation between two vertices. These cases are valid test cases, and you should expect them to be tested. However, most implementations of these algorithms handle these cases automatically, so you shouldn't have to worry too much about them when implementing the algorithms.

General Tips

There are two stopping conditions for Prim's. The first is when you have found your MST, and the second is when you have considered all reachable vertices from the start. Prim's should continue to run until one of the stopping conditions have been met. How and where should you check for both of these conditions in your code?

Before returning your MST, it is important to ensure that the MST is valid, as it is possible that no valid MST exists due to a disconnected graph. How can you ensure that your MST is valid? How many edges must a valid MST have in relation to the number of vertices in the undirected graph?

• We highly recommend copying the starter code and working in your preferred IDE in order to have access to features such as code completion, auto-formatting, and much more!

Here are general assignment guidelines that should be followed.

• Do not include any package declarations in your classes.
• Do not change any existing class headers, constructors, instance/global variables, or method signatures. For example, do not add throws to the method headers since they are not necessary. Instead, exceptions should be thrown as follows: throw new InsertExceptionHere("Error: some exception was thrown");
• All helper methods you choose to write should be made private. Recall the idea of Encapsulation in Object-Oriented Programming!
• Do not use anything that would trivialize the assignment. (e.g. Don't import/use java.util.ArrayList for an ArrayList assignment.)
• Always be very conscious of efficiency. Even if your method is to be , traversing the structure multiple times is considered inefficient unless that is absolutely required (and that case is extremely rare).
• If applicable, use the generic type of the class; do not use the raw type of the class. For example, use new LinkedList() instead of new LinkedList().

Use of the following statements should be avoided at all times.

package	System.arraycopy()	clone()
assert()	Arrays class	Array class
Thread class	Collections class	Collection.toArray()
Reflection APIs	Inner or nested classes	Lambda Expressions

The Vocareum (code editor) interface has six main components:

• TheDrop-Down in the top left. This lets you choose from multiple available files. Note that this drop-down will only be visible in assignments that require multiple files.
• TheRun button. This will compile your code and run a file scan. Running your code will not count towards your total allowed submission attempts, therefore you are free to run as many times as needed.
• TheSubmit button. This will compile your code, run a file scan, grade your assignment, and output results to console. Note that for most assignments in this class, you will only be allowed a limited number of submissions. A submission is counted when the submit button is clicked, regardless of whether or not your code can compile or if there are any file issues. Therefore, wehighly recommend that you run your code before submitting to ensure that there are no issues that will prevent your code from being graded and that every submission attempt will generate meaningful results.
• TheReset button. This will revert all your changes and reset your code to the default code template.
• TheCode Window. This is where you will writeyour code. For large coding assignments, we highly recommend copying the starter code and working in your preferred IDE to have access to features such as code completion, auto-formatting, and much more!
• TheOutput Window. This window will appear whenever you run or submit your code and will display the output for you to view.

Please refer to given five codings as below and provide me answer for five codings.

1. Edge.java

/**

* Class representing a directed edge from u to v.

*

* DO NOT EDIT THIS CLASS!!

*

* @author CS 1332 TAs

* @version 1.0

*/

public class Edge implements Comparable> {

private Vertex u;

private Vertex v;

private int weight;

/**

* Creates a directed edge from vertex u to vertex v. Any single edge is

* always directed, so if you're trying to createan undirected edge, you

* must create the edges (u, v, weight) and (v, u, weight) when creating the

* graph.

*

* @param u The start vertex of the edge.

* @param v The end vertex of the edge.

* @param weight The weight value of the edge.

* @throws IllegalArgumentException if any of the arguments are null.

*/

public Edge(Vertex u, Vertex v, int weight) {

if (u == null || v == null) {

throw new IllegalArgumentException("Arguments cannot be null.");

}

this.u = u;

this.v = v;

this.weight = weight;

}

/**

* Gets the weight.

*

* @return The weight.

*/

public int getWeight() {

return weight;

}

/**

* Gets the starting vertex (u).

*

* @return The starting vertex (u).

*/

public Vertex getU() {

return u;

}

/**

* Gets the ending vertex(v).

*

* @return The ending vertex (v).

*/

public Vertex getV() {

return v;

}

@Override

public boolean equals(Object o) {

if (o != null && o instanceof Edge) {

Edge e = (Edge) o;

return weight == e.weight && u.equals(e.u) && v.equals(e.v);

} else {

return false;

}

}

@Override

public int hashCode() {

return u.hashCode() ^ v.hashCode() ^ weight;

}

@Override

public int compareTo(Edge e) {

return weight - e.getWeight();

}

@Override

public String toString() {

return "Edge from " + u + " to " + v + " with weight " + weight;

}

}

2.Graph.java

import java.util.Set;

import java.util.Map;

import java.util.HashMap;

import java.util.List;

import java.util.ArrayList;

import java.util.HashSet;

/**

* A class representing a directed graph, with a vertex set, edge set, and

* an adjacency list.

*

* DO NOT EDIT THIS CLASS!!!

*

* @author CS 1332 TAs

* @version 1.0

*/

public class Graph {

private Set> vertices;

private Set> edges;

private Map, List>> adjList;

/**

* Builds the graph from a set of vertices and an edge list. All edges in

* the edge set are assumed to be directed, so if you want to createan

* undirected edge, the edge set must contain both the forward and backwards

* edges.

*

* @param vertices The vertex set.

* @param edges The edge set.

* @throws IllegalArgumentException If any of the arguments are null or if

* the vertex set doesn't contain all of the vertices.

*/

public Graph(Set> vertices, Set> edges) {

if (vertices == null || edges == null) {

throw new IllegalArgumentException("Arguments cannot be null.");

}

this.vertices = new HashSet<>(vertices);

this.edges = new HashSet<>(edges);

adjList = new HashMap<>();

for (Vertex v : vertices) {

adjList.put(v, new ArrayList<>());

}

for (Edge e : edges) {

if (adjList.containsKey(e.getU())) {

adjList.get(e.getU()).add(new VertexDistance<>(e.getV(), e.getWeight()));

} else {

throw new IllegalArgumentException("Vertex set must contain all vertices of the graph.");

}

}

}

/**

* Gets the vertex set.

*

* @return The vertex set.

*/

public Set> getVertices() {

return vertices;

}

/**

* Gets the edge set.

*

* @return The edge set.

*/

public Set> getEdges() {

return edges;

}

/**

* Gets the adjacency list.

*

* @return The adjacency list.

*/

public Map, List>> getAdjList() {

return adjList;

}

}

3.GraphAlgorithms.java

import java.util.HashSet;

import java.util.Map;

import java.util.PriorityQueue;

import java.util.Queue;

import java.util.Set;

/**

* Your implementation of Prim's algorithm.

*/

public class GraphAlgorithms {

/**

* Runs Prim's algorithm on the given graph and returns the Minimum

* Spanning Tree (MST) in the form of a set of Edges. If the graph is

* disconnected and therefore no valid MST exists, return null.

*

* You may assume that the passed in graph is undirected. In this framework,

* this means that if (u, v, 3) is in the graph, then the opposite edge

* (v, u, 3) will also be in the graph, though as a separate Edge object.

*

* The returned set of edges should form an undirected graph. This means

* that every time you add an edge to your return set, you should add the

* reverse edge to the set as well. This is for testing purposes. This

* reverse edge does not need to be the one from the graph itself; you can

* just make a new edge object representing the reverse edge.

*

* You may assume that there will only be one valid MST that can be formed.

*

* You should NOT allow self-loops or parallel edges in the MST.

*

* You may import/use java.util.PriorityQueue, java.util.Set, and any

* class that implements the aforementioned interface.

*

* DO NOT modify the structure of the graph. The graph should be unmodified

* after this method terminates.

*

* The only instance of java.util.Map that you may use is the adjacency

* list from graph. DO NOT create new instances of Map for this method

* (storing the adjacency list in a variable is fine).

*

* You may assume that the passed in start vertex and graph will not be null.

* You may assume that the start vertex exists in the graph.

*

* @param The generic typing of the data.

* @param start The vertex to begin Prims on.

* @param graph The graph we are applying Prims to.

* @return The MST of the graph or null if there is no valid MST.

*/

public static Set> prims(Vertex start, Graph graph) {

Set> mst = new HashSet<>();

PriorityQueue> queue = new PriorityQueue<>(graph.getEdges());

Map, Set>> map = graph.getAdjacencyList();

Set> visited = new HashSet<>();

visited.add(start);

while (!queue.isEmpty() && visited.size() != graph.getVertices().size()) {

Edge edge = queue.poll();

if (visited.contains(edge.getU()) && visited.contains(edge.getV())) {

continue;

}

if (visited.contains(edge.getU())) {

visited.add(edge.getV());

} else {

visited.add(edge.getU());

}

mst.add(edge);

mst.add(new Edge<>(edge.getV(), edge.getU(), edge.getWeight()));

for (Edge e : map.get(edge.getU())) {

if (!visited.contains(e.getV())) {

queue.add(e);

}

}

for (Edge e : map.get(edge.getV())) {

if (!visited.contains(e.getV())) {

queue.add(e);

}

}

}

return mst;

}

}

4.Vertex.java

/**

* Class representing a vertex.

*

* DO NOT EDIT THIS CLASS!!!

*

* @author CS 1332 TAs

* @version 1.0

*/

public class Vertex {

private T data;

/**

* Creates a Vertex object holding the given data.

*

* @param data The object that is stored in this Vertex.

* @throws IllegalArgumentException If data is null.

*/

public Vertex(T data) {

if (data == null) {

throw new IllegalArgumentException("Data cannot be null.");

}

this.data = data;

}

/**

* Gets the data.

*

* @return The data of this vertex.

*/

public T getData() {

return data;

}

@Override

public boolean equals(Object o) {

if (o != null && o instanceof Vertex) {

return data.equals(((Vertex) o).data);

} else {

return false;

}

}

@Override

public int hashCode() {

return data.hashCode();

}

@Override

public String toString() {

return data.toString();

}

}

5. VertexDistance.java

/**

* Class to store a vertex in a graph and an integer associated with it

* representing the distance to this vertex from some other vertex.

*

* DO NOT EDIT THIS CLASS!!!

*

* @author CS 1332 TAs

* @version 1.0

*/

public final class VertexDistance implements Comparable> {

private final Vertex vertex;

private final int distance;

/**

* Creates a pairing of vertex and distance to that vertex.

*

* @param vertex the Vertex to be stored.

* @param distance the integer representing the distance to this Vertex

* from the previous Vertex.

*/

public VertexDistance(Vertex vertex, int distance) {

this.vertex = vertex;

this.distance = distance;

}

/**

* Gets the vertex.

*

* @return The vertex.

*/

public Vertex getVertex() {

return vertex;

}

/**

* Gets the distance

*

* @return The distance.

*/

public int getDistance() {

return distance;

}

@Override

public boolean equals(Object o) {

if (o != null && o instanceof VertexDistance) {

VertexDistance e = (VertexDistance) o;

return distance == e.distance && vertex.equals(e.vertex);

} else {

return false;

}

}

@Override

public int hashCode() {

return vertex.hashCode() ^ distance;

}

@Override

public int compareTo(VertexDistance pair) {

return this.getDistance() - pair.getDistance();

}

@Override

public String toString() {

return "Pair with vertex " + vertex + " and distance " + distance;

}

}