// Adapted from Carrano&Savitch, Data Structures and Abstractions With Java // Providing ways to manually create a graph AND use adjacency list import java.util.*; public class Digraph { private Map verticies; // key-val pairs of (VertexName,Vertex) // each Vertex points to its adjacency list private int edgeCount; // number of edges public Digraph( ) { verticies = new LinkedHashMap(); // helps to maintain order in which nodes are created } // Add vertex to map; key is its name; val is the vertex: public void addVertex(Object name) { verticies.put(name, new Vertex(name)); } // Adds edge assuming source and dest verticies exist: public void addEdge(Object source, Object dest, int weight) { Vertex s = (Vertex)verticies.get(source); // get source index Vertex d = (Vertex)verticies.get(dest); // get dest index s.addEdge(new Edge(s,d,weight)); // add edge to source's adjacency list edgeCount++; } public void addEdge(Object source, Object dest) { addEdge(source,dest,0); } // Empty graph? public boolean isEmpty() { return verticies.isEmpty(); } // Return number of vertices: public int getVertexCount() { return verticies.size(); } // Return number of edges: public int getEdgeCount() { return edgeCount; } // Stringify by returning edges with their adjacency lists: public String toString() { String s = ""; Iterator it=verticies.keySet().iterator(); while(it.hasNext()) { Object key = it.next(); // current vertex label Vertex val = (Vertex) verticies.get(key); // current Vertex s += "[" + val + "]" + "-->"; s += val.getEdges(); s += "\n"; } return s; } // ***** NEW ***** // Want vertex iterator to do things to each Vertex in hashtable: public Iterator getVertexIterator() { return verticies.values().iterator(); } public void resetVerticies() { for (Iterator vi = getVertexIterator() ; vi.hasNext() ; ) { Vertex v = (Vertex) vi.next(); v.unvisit(); v.setCost(0); v.setPrev(null); } } public void resetVerticies(int cost) { for (Iterator vi = getVertexIterator() ; vi.hasNext() ; ) { Vertex v = (Vertex) vi.next(); v.unvisit(); v.setCost(cost); v.setPrev(null); } } public SeqStructure getBFS(Object origin) { resetVerticies(); SeqStructure toDo = new QueueAsList(); SeqStructure path = new QueueAsList(); Vertex originVertex = (Vertex)verticies.get(origin); originVertex.visit(); toDo.put(originVertex); path.put(originVertex); while(!toDo.isEmpty()) { Vertex currentVertex = (Vertex)toDo.get(); for (Iterator edges = currentVertex.getEdgeIterator(); edges.hasNext(); ) { Edge currentEdge = (Edge) edges.next(); Vertex nextVertex = currentEdge.getDest(); if(!nextVertex.isVisited()) { nextVertex.visit(); toDo.put(nextVertex); path.put(nextVertex); } } } return path; } public SeqStructure getDFS(Object origin) { resetVerticies(); SeqStructure toDo = new StackAsList(); SeqStructure path = new QueueAsList(); Vertex originVertex = (Vertex)verticies.get(origin); originVertex.visit(); toDo.put(originVertex); path.put(originVertex); while(!toDo.isEmpty()) { // take top of stack, but might have to put it back if it terminates: Vertex currentVertex = (Vertex)toDo.get(); // try to find unvisited neighbor: Iterator edges = currentVertex.getEdgeIterator(); boolean found = false; Vertex nextVertex = null; while (!found && edges.hasNext()) { Edge currentEdge = (Edge) edges.next(); Vertex trialVertex = currentEdge.getDest(); if(!trialVertex.isVisited()) { found = true; nextVertex = trialVertex; } } // unvisited vertex found! visit vertex and record doing so: // otherwise, we leave currentVertex removed from stack because it had no unvisited neighbors if (nextVertex != null) { toDo.put(currentVertex); // put currentVertex back because path didn't terminate here nextVertex.visit(); toDo.put(nextVertex); // next node to process path.put(nextVertex); // save path } } return path; } public boolean search(Object o) { if (verticies.get(o)==null) return false; return true; } public SeqStructure unweightedShortestPath(Object origin,Object end) { resetVerticies(); boolean done = false; SeqStructure toDo = new QueueAsList(); SeqStructure path = new StackAsList(); Vertex originVertex = (Vertex)verticies.get(origin); Vertex endVertex = (Vertex)verticies.get(end); originVertex.visit(); toDo.put(originVertex); while(!done && !toDo.isEmpty()) { Vertex currentVertex = (Vertex)toDo.get(); for (Iterator edges = currentVertex.getEdgeIterator(); !done && edges.hasNext(); ) { Edge currentEdge = (Edge) edges.next(); Vertex nextVertex = currentEdge.getDest(); if(!nextVertex.isVisited()) { nextVertex.visit(); nextVertex.setCost(1+currentVertex.getCost()); nextVertex.setPrev(currentVertex); toDo.put(nextVertex); } if (nextVertex.equals(endVertex)) done = true; } // end for } // end while path.put(endVertex); while(endVertex.hasPrev()) { endVertex = endVertex.getPrev(); path.put(endVertex); } return path; } // weighted shortest path (kinda the long way): public SeqStructure dijkstra1(Object origin,Object end) { resetVerticies(); boolean done = false; SeqStructure toDo = new Heap(edgeCount); // must use Minheap (my "Heap" is actually a Maxheap with MinPQElements) SeqStructure path = new QueueAsList(); // using a Queue to make cost of end easier to extract -- normally use a Stack Vertex originVertex = (Vertex)verticies.get(origin); Vertex endVertex = (Vertex)verticies.get(end); originVertex.setPrev(null); toDo.put(new MinPQElement(originVertex,0)); while(!done && !toDo.isEmpty()) { MinPQElement entry = (MinPQElement) toDo.get(); Vertex currentVertex = (Vertex) entry.getItem(); if (!currentVertex.isVisited()) { currentVertex.visit(); currentVertex.setCost(entry.getPriority()); currentVertex.setPrev(((Vertex) entry.getItem()).getPrev()); if (currentVertex.equals(endVertex)) done = true; else { for (Iterator edges = currentVertex.getEdgeIterator(); edges.hasNext(); ) { Edge currentEdge = (Edge) edges.next(); Vertex nextVertex = currentEdge.getDest(); if(!nextVertex.isVisited()) { int nextCost = currentEdge.getWeight() + currentVertex.getCost(); nextVertex.setCost(nextCost); nextVertex.setPrev(currentVertex); toDo.put(new MinPQElement(nextVertex,nextCost)); } } // end for } // end else } // end if } // end while path.put(endVertex); while(endVertex.hasPrev()) { endVertex = endVertex.getPrev(); path.put(endVertex); } return path; } // weighted shortest path (a bit less code): public SeqStructure dijkstra2(Object origin, Object end) { // could use end to save some effort resetVerticies(Integer.MAX_VALUE); // set all initial costs to infinity SeqStructure toDo = new Heap(edgeCount); // must use Minheap (my "Heap" is actually a Maxheap with MinPQElements) SeqStructure path = new QueueAsList(); // using a Queue to make cost of end easier to extract -- normally use a Stack Vertex originVertex = (Vertex)verticies.get(origin); Vertex endVertex = (Vertex)verticies.get(end); originVertex.setPrev(null); originVertex.setCost(0); toDo.put(new MinPQElement(originVertex,0)); while(!toDo.isEmpty()) { MinPQElement entry = (MinPQElement) toDo.get(); Vertex currentVertex = (Vertex) entry.getItem(); currentVertex.visit(); for (Iterator edges = currentVertex.getEdgeIterator(); edges.hasNext(); ) { Edge currentEdge = (Edge) edges.next(); Vertex nextVertex = currentEdge.getDest(); if(!nextVertex.isVisited()) { int nextCost = Math.min(currentVertex.getCost(),currentEdge.getWeight() + currentVertex.getCost()); nextVertex.setCost(nextCost); nextVertex.setPrev(currentVertex); toDo.put(new MinPQElement(nextVertex,nextCost)); } } } path.put(endVertex); while(endVertex.hasPrev()) { endVertex = endVertex.getPrev(); path.put(endVertex); } return path; } // weighted shortest path (a bit less code): public SeqStructure dijkstra3(Object origin, Object end) { // could use end to save some effort resetVerticies(Integer.MAX_VALUE); // set all initial costs to infinity SeqStructure toDo = new Heap(edgeCount); // must use Minheap (my "Heap" is actually a Maxheap with MinPQElements) SeqStructure path = new QueueAsList(); // using a Queue to make cost of end easier to extract -- normally use a Stack Vertex originVertex = (Vertex)verticies.get(origin); Vertex endVertex = (Vertex)verticies.get(end); originVertex.setPrev(null); originVertex.setCost(0); toDo.put(new MinPQElement(originVertex,0)); while(!toDo.isEmpty()) { System.out.println("Testing: " + toDo); // note: NOT sorted! why? array represents a tree MinPQElement entry = (MinPQElement) toDo.get(); Vertex currentVertex = (Vertex) entry.getItem(); currentVertex.visit(); for (Iterator edges = currentVertex.getEdgeIterator(); edges.hasNext(); ) { Edge currentEdge = (Edge) edges.next(); Vertex nextVertex = currentEdge.getDest(); int nextCost = currentEdge.getWeight() + currentVertex.getCost(); if (nextVertex.getCost() > nextCost ) { nextVertex.setCost(nextCost); nextVertex.setPrev(currentVertex); toDo.put(new MinPQElement(nextVertex,nextCost)); } } } path.put(endVertex); while(endVertex.hasPrev()) { endVertex = endVertex.getPrev(); path.put(endVertex); } return path; } }