Write or draw an adjacency (edge) list (NOT adjacency matrix) for the following graph.

Using the Graph.java methods, and assuming the variable called graph has been assigned an instance of a Graph, write statements to add EDGES/vertices which represent the following graph (use 0 for the weight when adding). See GraphTester.java in the Graph Code Files folder in Catalyst for examples.

Graph.java:

import java.util.*; import java.util.Map.Entry; interface Visitor { public void visit(T obj); }

// --- assumes definition of simple class Pair

// --- Vertex class ------------------------------------------------------ class Vertex { public static final double INFINITY = Double.MAX_VALUE; public HashMap, Double> > adjList = new HashMap, Double> >(); public E data; public double dist; // used for particular graph problems, NOT the graph itself public Vertex nextInPath; // used for particular graph problems, NOT the graph itself

public Vertex( E x ) { data = x; dist = INFINITY; nextInPath = null; } public Vertex() { this(null); }

public void addToAdjList(Vertex neighbor, double cost) { if( adjList.get(neighbor.data) == null) adjList.put(neighbor.data, new Pair, Double> (neighbor, cost) ); // Note: if you want to change the cost, you'll need to remove it and then add it back } public void addToAdjList(Vertex neighbor, int cost) { addToAdjList( neighbor, (double)cost ); } public boolean equals(Object rhs) { Vertex other = (Vertex)rhs;

return (data.equals(other.data));

} public int hashCode() { return (data.hashCode()); }

public void showAdjList() { Iterator, Double>>> iter ; Entry, Double>> entry; Pair, Double> pair;

System.out.print( "Adj List for " + data + ": "); iter = adjList.entrySet().iterator(); while( iter.hasNext() ) { entry = iter.next(); pair = entry.getValue(); System.out.print( pair.first.data + "(" + String.format("%3.1f", pair.second) + ") " ); } System.out.println(); }

}

public class Graph { // the graph data is all here -------------------------- protected HashMap > vertexSet;

// public graph methods -------------------------------- public Graph () { vertexSet = new HashMap >(); } public Graph( Edge[] edges ) { this(); int k, numEdges; numEdges = edges.length;

for (k = 0; k src, dst;

// put both source and dest into vertex list(s) if not already there src = addToVertexSet(source); dst = addToVertexSet(dest);

// add dest to source's adjacency list src.addToAdjList(dst, cost); //dst.addToAdjList(src, cost); // ADD THIS IF UNDIRECTED GRAPH } public void addEdge(E source, E dest, int cost) { addEdge(source, dest, (double)cost); } // adds vertex with x in it, and always returns ref to it public Vertex addToVertexSet(E x) { Vertex retVal=null; Vertex foundVertex;

// find if Vertex already in the list: foundVertex = vertexSet.get(x); if ( foundVertex != null ) // found it, so return it { return foundVertex; }

// the vertex not there, so create one retVal = new Vertex(x); vertexSet.put(x, retVal);

return retVal; // should never happen } public boolean remove(E start, E end) { Vertex startVertex = vertexSet.get(start); boolean removedOK = false; if( startVertex != null ) { Pair, Double> endPair = startVertex.adjList.remove(end); removedOK = endPair!=null; } /*// Add if UNDIRECTED GRAPH: Vertex endVertex = vertexSet.get(end); if( endVertex != null ) { Pair, Double> startPair = endVertex.adjList.remove(start); removedOK = startPair!=null ; } */

return removedOK; } public void showAdjTable() { Iterator>> iter;

System.out.println( "------------------------ "); iter = vertexSet.entrySet().iterator(); while( iter.hasNext() ) { (iter.next().getValue()).showAdjList(); } System.out.println(); }

public void clear() { vertexSet.clear(); } /** Breadth-first traversal from the parameter startElement*/ public void breadthFirstTraversal(E startElement, Visitor visitor) { Vertex currVertex; }

/** Postorder traversal from the parameter startElement */ public void depthFirstTraversal(E startElement, Visitor visitor) { }

}

GraphTester.java:

import java.util.*; import java.text.*;

//------------------------------------------------------ public class GraphTester { // ------- main -------------- public static void main(String[] args) { // build graph Graph myGraph1 = new Graph(); myGraph1.addEdge("A", "B", 0); myGraph1.addEdge("A", "C", 0); myGraph1.addEdge("A", "D", 0); myGraph1.addEdge("B", "E", 0); myGraph1.addEdge("B", "F", 0); myGraph1.addEdge("C", "G", 0); myGraph1.addEdge("D", "H", 0); myGraph1.addEdge("D", "I", 0); myGraph1.addEdge("F", "J", 0); myGraph1.addEdge("G", "K", 0); myGraph1.addEdge("G", "L", 0); myGraph1.addEdge("H", "M", 0); myGraph1.addEdge("H", "N", 0); myGraph1.addEdge("I", "N", 0);

myGraph1.showAdjTable();

}

}

5 2 7 6 3