Hi please help me complete the following code. And if it is possible tell me where you edit the code.

Create a class Directed Weighted Graph. A class that implements the ADT-directed graph.

import java.util.Iterator;

public class DirectedGraph implements GraphInterface { private DictionaryInterface> vertices; private int edgeCount; public DirectedGraph() { vertices = new LinkedDictionary<>(); edgeCount = 0; } // end default constructor

protected void resetVertices() { Iterator> vertexIterator = vertices.getValueIterator(); while (vertexIterator.hasNext()) { VertexInterface nextVertex = vertexIterator.next(); nextVertex.unvisit(); nextVertex.setCost(0); nextVertex.setPredecessor(null); } // end while } // end resetVertices

public QueueInterface getDepthFirstTraversal(T origin) { // Assumes graph is not empty resetVertices(); QueueInterface traversalOrder = new LinkedQueue(); StackInterface> vertexStack = new LinkedStack<>(); VertexInterface originVertex = vertices.getValue(origin); originVertex.visit(); traversalOrder.enqueue(origin); // Enqueue vertex label vertexStack.push(originVertex); // Enqueue vertex while (!vertexStack.isEmpty()) { VertexInterface topVertex = vertexStack.peek(); VertexInterface nextNeighbor = topVertex.getUnvisitedNeighbor();

if (nextNeighbor != null) { nextNeighbor.visit(); traversalOrder.enqueue(nextNeighbor.getLabel()); vertexStack.push(nextNeighbor); } else // All neighbors are visited vertexStack.pop(); } // end while return traversalOrder; } // end getDepthFirstTraversal

public StackInterface getTopologicalOrder() { resetVertices();

StackInterface vertexStack = new LinkedStack<>(); int numberOfVertices = getNumberOfVertices(); for (int counter = 1; counter <= numberOfVertices; counter++) { VertexInterface nextVertex = findTerminal(); nextVertex.visit(); vertexStack.push(nextVertex.getLabel()); } // end for return vertexStack; } // end getTopologicalOrder

/** Precondition: path is an empty stack (NOT null) */ public int getShortestPath(T begin, T end, StackInterface path) { resetVertices(); boolean done = false; QueueInterface> vertexQueue = new LinkedQueue<>();

VertexInterface originVertex = vertices.getValue(begin); VertexInterface endVertex = vertices.getValue(end);

originVertex.visit(); // Assertion: resetVertices() has executed setCost(0) // and setPredecessor(null) for originVertex

vertexQueue.enqueue(originVertex);

while (!done && !vertexQueue.isEmpty()) { VertexInterface frontVertex = vertexQueue.dequeue();

Iterator> neighbors = frontVertex.getNeighborIterator(); while (!done && neighbors.hasNext()) { VertexInterface nextNeighbor = neighbors.next();

if (!nextNeighbor.isVisited()) { nextNeighbor.visit(); nextNeighbor.setCost(1 + frontVertex.getCost()); nextNeighbor.setPredecessor(frontVertex); vertexQueue.enqueue(nextNeighbor); } // end if

if (nextNeighbor.equals(endVertex)) done = true; } // end while } // end while

// Traversal ends; construct shortest path int pathLength = (int)endVertex.getCost(); path.push(endVertex.getLabel());

VertexInterface vertex = endVertex; while (vertex.hasPredecessor()) { vertex = vertex.getPredecessor(); path.push(vertex.getLabel()); } // end while

return pathLength; } // end getShortestPath

/** Precondition: path is an empty stack (NOT null) */ public double getCheapestPath(T begin, T end, StackInterface path) { resetVertices(); boolean done = false;

// Use EntryPQ instead of Vertex because multiple entries contain // the same vertex but different costs - cost of path to vertex is EntryPQ's priority value PriorityQueueInterface priorityQueue = new HeapPriorityQueue<>(); VertexInterface originVertex = vertices.getValue(begin); VertexInterface endVertex = vertices.getValue(end);

priorityQueue.add(new EntryPQ(originVertex, 0, null)); while (!done && !priorityQueue.isEmpty()) { EntryPQ frontEntry = priorityQueue.remove(); VertexInterface frontVertex = frontEntry.getVertex(); if (!frontVertex.isVisited()) { frontVertex.visit(); frontVertex.setCost(frontEntry.getCost()); frontVertex.setPredecessor(frontEntry.getPredecessor()); if (frontVertex.equals(endVertex)) done = true; else { Iterator> neighbors = frontVertex.getNeighborIterator(); Iterator edgeWeights = frontVertex.getWeightIterator(); while (neighbors.hasNext()) { VertexInterface nextNeighbor = neighbors.next(); Double weightOfEdgeToNeighbor = edgeWeights.next(); if (!nextNeighbor.isVisited()) { double nextCost = weightOfEdgeToNeighbor + frontVertex.getCost(); priorityQueue.add(new EntryPQ(nextNeighbor, nextCost, frontVertex)); } // end if } // end while } // end if } // end if } // end while

// Traversal ends, construct cheapest path double pathCost = endVertex.getCost(); path.push(endVertex.getLabel()); VertexInterface vertex = endVertex; while (vertex.hasPredecessor()) { vertex = vertex.getPredecessor(); path.push(vertex.getLabel()); } // end while

return pathCost; } // end getCheapestPath

protected VertexInterface findTerminal() { boolean found = false; VertexInterface result = null;

Iterator> vertexIterator = vertices.getValueIterator();

while (!found && vertexIterator.hasNext()) { VertexInterface nextVertex = vertexIterator.next(); // If nextVertex is unvisited AND has only visited neighbors) if (!nextVertex.isVisited()) { if (nextVertex.getUnvisitedNeighbor() == null ) { found = true; result = nextVertex; } // end if } // end if } // end while

return result; } // end findTerminal

// Used for testing public void displayEdges() { System.out.println(" Edges exist from the first vertex in each line to the other vertices in the line."); System.out.println("(Edge weights are given; weights are zero for unweighted graphs): "); Iterator> vertexIterator = vertices.getValueIterator(); while (vertexIterator.hasNext()) { ((Vertex)(vertexIterator.next())).display(); } // end while } // end displayEdges private class EntryPQ implements Comparable { private VertexInterface vertex; private VertexInterface previousVertex; private double cost; // cost to nextVertex private EntryPQ(VertexInterface vertex, double cost, VertexInterface previousVertex) { this.vertex = vertex; this.previousVertex = previousVertex; this.cost = cost; } // end constructor public VertexInterface getVertex() { return vertex; } // end getVertex public VertexInterface getPredecessor() { return previousVertex; } // end getPredecessor

public double getCost() { return cost; } // end getCost public int compareTo(EntryPQ otherEntry) { // Using opposite of reality since our priority queue uses a maxHeap; // could revise using a minheap return (int)Math.signum(otherEntry.cost - cost); } // end compareTo public String toString() { return vertex.toString() + " " + cost; } // end toString } // end EntryPQ } // end DirectedGraph