I need help with this Java Program, I need both parts done program and the extra credit one.

Please provide all the code and tell me how to compile it. thank you

WeightedGraphInterface.java

//---------------------------------------------------------------------------- // WeightedGraphInterface.java by Dale/Joyce/Weems Chapter 9 // // Interface for a class that implements a directed graph with weighted edges. // Vertices are objects of class T and can be marked as having been visited. // Edge weights are integers. // Equivalence of vertices is determined by the vertices' equals method. // // General precondition: Except for the addVertex and hasVertex methods, // any vertex passed as an argument to a method is in this graph. //----------------------------------------------------------------------------

package ch09.graphs;

import ch05.queues.*;

public interface WeightedGraphInterface { boolean isEmpty(); // Returns true if this graph is empty; otherwise, returns false.

boolean isFull(); // Returns true if this graph is full; otherwise, returns false. void addVertex(T vertex); // Preconditions: This graph is not full. // Vertex is not already in this graph. // Vertex is not null. // // Adds vertex to this graph.

boolean hasVertex(T vertex); // Returns true if this graph contains vertex; otherwise, returns false.

void addEdge(T fromVertex, T toVertex, int weight); // Adds an edge with the specified weight from fromVertex to toVertex.

int weightIs(T fromVertex, T toVertex); // If edge from fromVertex to toVertex exists, returns the weight of edge; // otherwise, returns a special null-edge value.

UnboundedQueueInterface getToVertices(T vertex); // Returns a queue of the vertices that are adjacent from vertex.

void clearMarks(); // Sets marks for all vertices to false.

void markVertex(T vertex); // Sets mark for vertex to true.

boolean isMarked(T vertex); // Returns true if vertex is marked; otherwise, returns false. T getUnmarked(); // Returns an unmarked vertex if any exist; otherwise, returns null.

int getNumVertices();

String getToVertexNotVisited(WeightedGraphInterface graph, String vertex);

UnboundedQueueInterface getToVerticesStack(T vertex);

UnboundedQueueInterface getToVerticesQueue(T vertex);

}

WeightedGraph.java

// Incomplete version

//---------------------------------------------------------------------------- // WeightedGraph.java by Dale/Joyce/Weems Chapter 9 // // Implements a directed graph with weighted edges. // Vertices are objects of class T and can be marked as having been visited. // Edge weights are integers. // Equivalence of vertices is determined by the vertices' equals method. // // General precondition: Except for the addVertex and hasVertex methods, // any vertex passed as an argument to a method is in this graph. //----------------------------------------------------------------------------

package graphs;

import queues.*;

public class WeightedGraph implements WeightedGraphInterface { public static final int NULL_EDGE = 0; private static final int DEFCAP = 50; // default capacity private int numVertices; private int maxVertices; private T[] vertices; private int[][] edges; private boolean[] marks; // marks[i] is mark for vertices[i]

public WeightedGraph() // Instantiates a graph with capacity DEFCAP vertices. { numVertices = 0; maxVertices = DEFCAP; vertices = (T[]) new Object[DEFCAP]; marks = new boolean[DEFCAP]; edges = new int[DEFCAP][DEFCAP]; } public WeightedGraph(int maxV) // Instantiates a graph with capacity maxV. { numVertices = 0; maxVertices = maxV; vertices = (T[]) new Object[maxV]; marks = new boolean[maxV]; edges = new int[maxV][maxV]; }

public boolean isEmpty() // Returns true if this graph is empty; otherwise, returns false. { return (numVertices == 0); }

public boolean isFull() // Returns true if this graph is full; otherwise, returns false. { return (numVertices == maxVertices); }

public void addVertex(T vertex) // Preconditions: This graph is not full. // Vertex is not already in this graph. // Vertex is not null. // // Adds vertex to this graph. { vertices[numVertices] = vertex; for (int index = 0; index

public boolean hasVertex(T vertex) // Returns true if this graph contains vertex; otherwise, returns false. { for (int i = 0; i

} private int indexIs(T vertex) // Returns the index of vertex in vertices. { int index = 0; while (!vertex.equals(vertices[index])) index++; return index; }

public void addEdge(T fromVertex, T toVertex, int weight) // Adds an edge with the specified weight from fromVertex to toVertex. { int row; int column; row = indexIs(fromVertex); column = indexIs(toVertex); edges[row][column] = weight; }

public int weightIs(T fromVertex, T toVertex) // If edge from fromVertex to toVertex exists, returns the weight of edge; // otherwise, returns a special null-edge value. { int row; int column; row = indexIs(fromVertex); column = indexIs(toVertex); return edges[row][column]; }

public UnboundedQueueInterface getToVertices(T vertex) // Returns a queue of the vertices that are adjacent from vertex. { UnboundedQueueInterface adjVertices = new LinkedUnbndQueue(); int fromIndex; int toIndex; fromIndex = indexIs(vertex); for (toIndex = 0; toIndex

public void clearMarks() // Sets marks for all vertices to false. { for (int i = 0; i

public void markVertex(T vertex) // Sets mark for vertex to true. { int index; index = indexIs(vertex); marks[index] = true; }

public boolean isMarked(T vertex) // Returns true if vertex is marked; otherwise, returns false. { int index; index = indexIs(vertex); return(marks[index]); } public T getUnmarked() // Returns an unmarked vertex if any exist; otherwise, returns null. { boolean found = false; int index = 0; while ((index

Design and code a reference-based weighted graph class with the vertices stored in a linked list as in Figure 9.11(b). Your class should implement our WeightedGraphlnterface The WeightedGraph class is provided in the Extra Files folder via D2L Content. Implement and test an updated toString () method for the new WeightedGraphList class. Use the graph from the textbook on p. 637 Figure 9.9 EXTRA CREDIT+5 points: Implement an updated isPath2 algorithm for the following vertices in your driver program (this requires updating several other methods for the new WeightedGraphList class): isPath2(g, start, end); //starts is "Dallas" and ends is "Houston