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
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.
- 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
private Vertex
private Vertex
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
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
return u;
}
/**
* Gets the ending vertex(v).
*
* @return The ending vertex (v).
*/
public Vertex
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
private Set
private Map
/**
* 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
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
adjList.put(v, new ArrayList<>());
}
for (Edge
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
return vertices;
}
/**
* Gets the edge set.
*
* @return The edge set.
*/
public Set
return edges;
}
/**
* Gets the adjacency list.
*
* @return The adjacency list.
*/
public Map
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
* @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
PriorityQueue
Map
Set
visited.add(start);
while (!queue.isEmpty() && visited.size() != graph.getVertices().size()) {
Edge
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
if (!visited.contains(e.getV())) {
queue.add(e);
}
}
for (Edge
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
private final 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
this.vertex = vertex;
this.distance = distance;
}
/**
* Gets the vertex.
*
* @return The vertex.
*/
public Vertex
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;
}
}
Step by Step Solution
There are 3 Steps involved in it
Step: 1
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
31st Edition
1111972516, 978-1285586618, 1285586611, 978-1285613109, 978-1111972516
