On DirectedGraph.java, implement the method getDepthFirstTraversal. You may follow the pseudocode from the book.

Pseudocode

Algorithm getDepthFirstTraversal(originVertex) traversalOrder = a new queue for the resulting traversal order vertexStack = a new stack to hold vertices as they are visited Mark originVertex as visited traversalOrder.enqueue(originVertex) vertexStack.push(originVertex) while (!vertexStack.isEmpty()) topVertex = vertexStack.peek() if (topVertex has an unvisited neighbor) nextNeighbor = next unvisited neighbor of topVertex Mark nextNeighbor as visited traversalOrder.enqueue(nextNeighbor) vertexStack.push(nextNeighbor) else vertexStack.pop() return traversalOrder

DirectedGraph.java

package GraphPackage; import QueuePackage.LinkedQueue; import QueuePackage.QueueInterface; import StackPackage.ArrayStack; import StackPackage.StackInterface; import java.util.HashMap; import java.util.Iterator; public class DirectedGraph implements GraphInterface { private HashMap> vertices; private int edgeCount; public DirectedGraph() { vertices = new HashMap<>(); edgeCount = 0; } @Override public QueueInterface getBreathFirstTraversal(T origin) { resetVertices(); QueueInterface traversalOrder = new LinkedQueue<>(); QueueInterface> vertexQueue = new LinkedQueue<>(); VertexInterface originVertex = vertices.get(origin); originVertex.visit(); traversalOrder.enqueue(origin); vertexQueue.enqueue(originVertex); while (!vertexQueue.isEmpty()) { VertexInterface frontVertex = vertexQueue.dequeue(); Iterator> neighbors = frontVertex.getNeighborIterator(); while(neighbors.hasNext()) { VertexInterface nextNeighbor = neighbors.next(); if(!nextNeighbor.isVisited()) { nextNeighbor.visit(); traversalOrder.enqueue(nextNeighbor.getLabel()); vertexQueue.enqueue(nextNeighbor); } } } return traversalOrder; } @Override public QueueInterface getDepthFirstTraversal(T origin) { return null; } @Override public StackInterface getTopologicalOrder() { return null; } @Override public int getShortestPath(T begin, T end, StackInterface path) { resetVertices(); boolean done = false; QueueInterface> vertexQueue = new LinkedQueue<>(); VertexInterface originVertex = vertices.get(begin); VertexInterface endVertex = vertices.get(end); originVertex.visit(); 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); } if (nextNeighbor.equals(endVertex)) { done = true; } } } // 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()); } return pathLength; } @Override public boolean addVertex(T vertexLabel) { VertexInterface addOutcome = vertices.put(vertexLabel, new Vertex<>(vertexLabel)); return addOutcome == null; } @Override public int getCheapestPath(T begin, T end, StackInterface path) { return 0; } @Override public boolean addEdge(T begin, T end, double edgeWeight) { boolean result = false; VertexInterface beginVertex = vertices.get(begin); VertexInterface endVertex = vertices.get(end); if ((beginVertex != null) && (endVertex != null)) result = beginVertex.connect(endVertex, edgeWeight); if (result) edgeCount++; return result; } @Override public boolean addEdge(T begin, T end) { return addEdge(begin, end, 0); } @Override public boolean hasEdge(T begin, T end) { boolean found = false; VertexInterface beginVertex = vertices.get(begin); VertexInterface endVertex = vertices.get(end); if((beginVertex != null) && (endVertex != null)) { Iterator> neighbors = beginVertex.getNeighborIterator(); while(!found && neighbors.hasNext()) { VertexInterface nextNeighbor = neighbors.next(); if (endVertex.equals(nextNeighbor)) found = true; } } return found; } @Override public boolean isEmpty() { return vertices.isEmpty(); } @Override public int getNumberOfVertices() { return vertices.size(); } @Override public int getNumberOfEdges() { return edgeCount; } @Override public void clear() { } public boolean isConnect() { return false; } protected void resetVertices() { Iterator> vertexIterator = vertices.values().iterator(); while(vertexIterator.hasNext()) { VertexInterface nextVertex = vertexIterator.next(); nextVertex.unvisit(); nextVertex.setCost(0); nextVertex.setPredecessor(null); } } }