Color.java

package graph; public enum Color { //for coloring nodes BLACK, WHITE, GREY; }

 

Edge.java

package graph; public class Edge { Vertex from, to; int weight; public Edge(Vertex from, Vertex to, int weight) { this.from = from; this.to = to; this.weight = weight; } public Edge(Vertex from, Vertex to) { this.from = from; this.to = to; this.weight = 1; } public String toString() { return "(" + from + "->" + to + ", " + weight + ")"; } // auto-generated: hashes on all fields public int hashCode() { return weight+from.hashCode()+to.hashCode(); } // auto-generated: compares all fields public boolean equals(Object o) { Edge e = (Edge)o; return from.equals(e.from)&&to.equals(e.to)&& weight==e.weight;  } }

 

Graph.java

package graph; import java.util.*; public interface Graph { Collection getVertices(); ArrayList depthFirstSearch(); ArrayList topologicalSortDFS(); ArrayList topologicalSortQueue(); ArrayList shortestPath(int source, int target);   }

 

Vertex.java

package graph; public class Vertex implements Comparable{ int value; int discoveryTime; //for DFS and Shortest Path int finishTime; //for DFS Color color; Vertex p; //can be used for DFS Tree and Shortest Path int inDegree; //for topological sort Vertex(int val) { value = val; } public String toString() { return Integer.toString(value); }  /****** NOTE THAT WE REALLY ONLY CARE ABOUT VALUES ***********/ //This is not a great hashCode public int hashCode() { return value; } //Compare vertices public boolean equals(Object o) { Vertex v = (Vertex)o; return v.value==value;  } public int compareTo(Vertex v) { return value - v.value; }  }

Transcribed Image Text:

implement the Graph Interface which contains four methods on graphs. Graphs can be directed or undirected with either weighted edges or edges with equal weight (equivalent to an unweighted graph). To get started, import the starter files: Vertex.java, Edge.java, Color.java, and Graph.java into the graph package you create in a new Java Project. You CANNOT modify any of the given java files. Note that this homework does not require you to create JUnit tests. However just because I am not requiring you to create tests does not mean that you should not test your code. Testing your code frequently throughout the development process is an integral part of being a successful computer scientist (and it makes the debugging process significantly easier). Vertex.java This class represents a vertex in the graph. Note that the Vertex class contains several instance variables that you can use (or repurpose) to implement the graph algorithms. The equals/compareTo/hashCode only depend on the value of the vertex. You can assume that any graph has unique vertex values. Edge.java This class represents an edge in the graph. This class contains a from Vertex, a to Vertex, weight from to and a weight. This is equivalent to Color.java This is an enum that represents different node colors that can be used when implementing depth first search. Graph.java This is an interface that requires you to implement 4 methods described below. Note that each method returns an ArrayList<Integers>. These are the values of the vertices. implement the Graph Interface which contains four methods on graphs. Graphs can be directed or undirected with either weighted edges or edges with equal weight (equivalent to an unweighted graph). To get started, import the starter files: Vertex.java, Edge.java, Color.java, and Graph.java into the graph package you create in a new Java Project. You CANNOT modify any of the given java files. Note that this homework does not require you to create JUnit tests. However just because I am not requiring you to create tests does not mean that you should not test your code. Testing your code frequently throughout the development process is an integral part of being a successful computer scientist (and it makes the debugging process significantly easier). Vertex.java This class represents a vertex in the graph. Note that the Vertex class contains several instance variables that you can use (or repurpose) to implement the graph algorithms. The equals/compareTo/hashCode only depend on the value of the vertex. You can assume that any graph has unique vertex values. Edge.java This class represents an edge in the graph. This class contains a from Vertex, a to Vertex, weight from to and a weight. This is equivalent to Color.java This is an enum that represents different node colors that can be used when implementing depth first search. Graph.java This is an interface that requires you to implement 4 methods described below. Note that each method returns an ArrayList<Integers>. These are the values of the vertices.

Answer rating: 100% (QA)

I can provide you with an implementation of the GraphImp class that follows the requirements and methods you described Please note that Ill focus on providing the code for the GraphImp class and assum... View the full answer