The code below contains some defined methods (things I think you might be unfamiliar with, e.g., Iterators and Maps). Most of the methods contain a
// TO DO
comment, which means you need to replace with the correct implementation!
One other hint: when marking a vertex as visited or not, use the GraphVertex's attributes, e.g.,
// mark this vertex v.setAttribute( "visited", true );// if v is not visitedif ( !(boolean)v.getAttribute("visited") )import java.util.Iterator;import java.util.List;import java.util.ArrayList;import java.util.Queue;import java.util.LinkedList;/** * Implements a simple directed graph. */public class DirectedGraph implements Graph { // instance properties private List<GraphVertex> vertices; /** * Construct a new empty graph. */ public DirectedGraph() { // TO DO } /** * Add a vertex to the graph. */ public void addVertex( GraphVertex v ) { // TO DO // walk the list to perform insertion sort } /** * Get a vertex from the graph with the given ID. * Returns null if no such vertex exists. */ public GraphVertex getVertex( int ID ) { // TO DO return null; } /** * Remove a vertex from the graph with the given ID. */ public void removeVertex( int ID ) { // TO DO // remove it from the vertices list // for all remaining vertices, remove it from any neighbor list } /** * Get the number of vertices in this graph. */ public int numVertices() { // TO DO return -1; } /** * Add an edge to the graph with endpoints given by * vertices with ID1 and ID2. (Do not add if it already * exists). * * This is a directed graph, so add as a directed edge from ID1 -> ID2. */ public void addEdge( int ID1, int ID2) { GraphVertex source = getVertex( ID1 ); GraphVertex target = getVertex( ID2 ); // as long as it was a valid edge if ( source != null && target != null ) { // TO DO } } /** * Remove an edge from the graph with endpoints given by * vertices with ID1 and ID2. * * This is a directed graph, so remove the directed edge from ID1 -> ID2. */ public void removeEdge( int ID1, int ID2 ) { // TO DO } /** * Check if an edge exists with endpoints given by * vertices with ID1 and ID2. * * This is a directed graph, so checks for the directed edge from ID1 -> ID2. */ public boolean isEdge( int ID1, int ID2 ) { // TO DO return false; } /** * Get the edges in the graph. Each edge is stored * as a 1-dimensional array of length 2 with the * endpoints. * * This is a directed graph, so returns directed edges from source -> target. * The source vertex is stored at index 0, target at index 1. */ public Iterator<GraphVertex[]> getEdges() { // TO DO return null; } /** * Get the number of edges in this graph. */ public int numEdges() { // TO DO return -1; } /** * Helper method for resetting marks added during traversals. **/ private void resetMarks() { // TO DO // for each vertex, set the attribute "visited" to be false } /** * Return a list of vertices visited by a depth-first traversal * from the vertex with the given ID. * * If the ID is invalid, returns null. */ public List<GraphVertex> depthFirst( int ID ) { // find the vertex with the ID GraphVertex v = getVertex(ID); // if it's not a valid ID, return null if ( v == null ) return null; // reset any marks on the vertices resetMarks(); // make an empty list for the traversal List<GraphVertex> traversal = new ArrayList<GraphVertex>(); // mark the vertex v.setAttribute( "visited", true ); // add this vertex traversal.add(v); // start the recursion depthFirstR( v, traversal ); // return the traversal return traversal; } /** * Helper method for recursion, add vertices to given list. */ private void depthFirstR( GraphVertex v, List<GraphVertex> traversal ) { // TO DO } /** * Return a list of vertices visited by a breadth-first traversal * from the vertex with the given ID. * * If the ID is invalid, returns null. */ public List<GraphVertex> breadthFirst( int ID ) { // TO DO return null; } /** * Return the vertices and edges, as in: * "((0,1,2,3),(0->1,1->2,1->3,2->3,3->0))" */ public String toString() { return "(" + vertexIDsString() + "," + edgesString() + ")"; } /** * Returns a String of vertex IDs in increasing order, as in "(0,1,2,3)". */ public String vertexIDsString() { // TO DO return ""; } /** * Returns a String of edges, as in "(0->1,1->2,1->3,2->3,3->0)". */ public String edgesString() { // String for edges String edgeString = "("; // for each edge Iterator<GraphVertex[]> edges = getEdges(); // current edge GraphVertex[] edge; while ( edges.hasNext() ) { edge = edges.next(); edgeString += Integer.toString( edge[0].getID() ) + "->" + Integer.toString( edge[1].getID()) + ","; } // if there was at least one edge if ( edgeString.length() > 1 ) // remove extra comma edgeString = edgeString.substring(0,edgeString.length() - 1); // add the last ) edgeString += ")"; return edgeString; }}