Please create total 5 codings for below questions.

1. Edge.java

2.Graph.java

3.GraphAlgorithms.java

4.Vertex.java

5.VertexDistance.java

Below is a question.

Graph Traversals

Forthisassignment, you will be implementingthe Breadth-First Search and Depth-First Search graph traversal algorithms. This assignment has quite a few files in it, so please be sure to read ALL of the documentation given to you.

IMPORTANT:

• You will begiven 5 attempts on this assignment, with a30 minutecooldownbetween 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

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

• getVertices provides a Set of Vertex objects (another class provided to you) associated with a graph.
• getAdjListprovides a Map that maps Vertex objects to Lists of VertexDistance 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 a VertexDistance object with vertex B and distance 2 and another VertexDistance 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 the Graph class, you will be using the VertexDistance class implementation that we have provided. This data structure is used by the adjacency list to represent which vertices a vertex is connected to.

Search Algorithms

Breadth-First Search is a search algorithm that visits vertices in order of "level", visiting all vertices one edge away from start, then two edges away from start, etc. Similar to levelorder traversal in BSTs,it utilizes a Queue data structure.

Depth-First Search is a search algorithm that visits vertices in a depth based order. In your implementation of DFS, you will be using the recursive stack rather than a Stack data structure. It searches along one path of vertices from the start vertex and backtracks once it hits a dead end or a visited vertex until it finds another path to continue along. Your implementation of DFS must be recursive.

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

Keeping track of visited vertices is important. It allows for your traversal to be efficient and to avoid traversing through cycles over and over again. Using a Set to store visited vertices will allow forconstant time look up, versus a list where searching is done in linear time.

Your BFS implementation should utilize three data structures, while your DFS implementation should utilize two.

• We highly recommend copying the starter codeand 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 exceptionwas 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 consideredinefficientunless that is absolutely required (and that case is extremelyrare).
• If applicable, use the generic type of the class; do not use the raw type of the class. For example, usenewLinkedList()instead ofnew 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-Downin 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.
• TheRunbutton.This willcompile your code and run a file scan. Running your code will notcount towards your total allowed submission attempts, therefore you are free to run as many times as needed.
• TheSubmitbutton. 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 limitednumber of submissions. A submission is counted when the submit button is clicked, regardless of whether or not your codecan compile or if there are any file issues. Therefore, wehighly recommendthat 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.
• TheResetbutton. 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 codeand 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 yourun or submit your code and will display the output for you to view.

Please refer to given coding as below

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.ArrayDeque; import java.util.ArrayList; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Queue; import java.util.Set;

/** * Your implementation of various graph traversal algorithms. */ public class GraphAlgorithms {

/** * Performs a breadth first search (bfs) on the input graph, starting at * the parameterized starting vertex. * * When exploring a vertex, explore in the order of neighbors returned by * the adjacency list. Failure to do so may cause you to lose points. * * You may import/use java.util.Set, java.util.List, java.util.Queue, and * any classes that implement the aforementioned interfaces, as long as they * are efficient. * * The only instance of java.util.Map that you should use is the adjacency * list from graph. DO NOT create new instances of Map for BFS * (storing the adjacency list in a variable is fine). * * DO NOT modify the structure of the graph. The graph should be unmodified * after this method terminates. * * 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 the bfs on. * @param graph The graph to search through. * @return List of vertices in visited order. */ public static List> bfs(Vertex start, Graph graph) { // WRITEYOUR CODE HERE (DO NOT MODIFY METHOD HEADER)! }

/** * Performs a depth first search (dfs) on the input graph, starting at * the parameterized starting vertex. * * When exploring a vertex, explore in the order of neighbors returned by * the adjacency list. Failure to do so may cause you to lose points. * * NOTE: This method should be implemented recursively. You may need to * createa helper method. * * You may import/use java.util.Set, java.util.List, and any classes that * implement the aforementioned interfaces, as long as they are efficient. * * 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 DFS * (storing the adjacency list in a variable is fine). * * DO NOT modify the structure of the graph. The graph should be unmodified * after this method terminates. * * 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 the dfs on. * @param graph The graph to search through. * @return List of vertices in visited order. */ public static List> dfs(Vertex start, Graph graph) { // WRITEYOUR CODE HERE (DO NOT MODIFY METHOD HEADER)! } }

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; } }