Code /* TestGraph.java CIS 260 4/22/2009 David Klick Demonstration of graph techniques and algorithms. */ import java.util.*; import java.io.*; class Graph { private boolean DIRECTED = false; private boolean WEIGHTED = false; private ArrayList vertexList = new ArrayList(); private ArrayList> adjacencyMatrix = new ArrayList>(); private ArrayList> adjacencyList = new ArrayList>(); class Vertex { private String name; public boolean visited; // used in isPath public boolean inTree; // used in MST alg public double minWeight; // for shortest path alg public boolean weightFound; // for shortest path alg public ArrayList minPath; // for shortest path alg public Vertex(String s) { name = s; } public String getName() { return name; } public String toString() { return name; } } class Edge implements Comparable { public int src, dest; public double weight; Edge(int s, int d, double w) { src = s; dest = d; weight = w; } public int compareTo(Edge e) { if (weight < e.weight) return -1; else if (weight > e.weight) return 1; else return 0; } public String toString() { String s = ""; if (src != -1) s += vertexList.get(src) + "->"; s += vertexList.get(dest) + " (" + weight + ")"; return s; } } public Graph() { this(false, false); } public Graph(boolean directed) { this(directed, false); } public Graph(boolean directed, boolean weighted) { DIRECTED = directed; WEIGHTED = weighted; } public int addVertex(String s) { int pos = find(s); if (pos == -1) { vertexList.add(new Vertex(s)); // create adjacency list and matrix for new vertex adjacencyList.add(new ArrayList()); adjacencyMatrix.add(new ArrayList()); // make sure there are no edges to new vertex from anywhere else for (int i=0; i" + vertexList.get(posDest) + " (" + adjacencyMatrix.get(posSrc).get(posDest) + ")"); return false; } if (!DIRECTED && adjacencyMatrix.get(posDest).get(posSrc) != 0) { System.err.println("Error: Edge already exists: " + vertexList.get(posDest) + "->" + vertexList.get(posSrc) + " (" + adjacencyMatrix.get(posDest).get(posSrc) + ")"); return false; } // set weights in adjacency matrix adjacencyMatrix.get(posSrc).set(posDest, weight); if (!DIRECTED) adjacencyMatrix.get(posDest).set(posSrc, weight); // update adjacency list adjacencyList.get(posSrc).add(new Edge(posSrc, posDest, weight)); if (!DIRECTED) adjacencyList.get(posDest).add(new Edge(posDest, posSrc, weight)); return true; } public String toString() { String s = "----- Graph listing -----\n\nList of vertices:\n"; for (int i=0; i0?", ":"") + e); } s += "\n"; } s += "\nAdjacency Matrix\n "; for (int j=0; j v = new ArrayList(); vertexList.get(posSrc).visited = true; v.add(posSrc); while (!v.isEmpty()) { int v1 = depthFirst ? v.remove(v.size()-1) : v.remove(0); int v2; while ( (v2=getAdjacentUnvisited(v1)) != -1 ) { if (v2 == posDest) return true; vertexList.get(v2).visited = true; v.add(v2); } } return false; } // This minimal spanning tree algorithm accounts for weighted edges, // but not directed edges public String minimumSpanningTree() { // check for empty graph if (vertexList.size() == 0) return "No MST - empty graph"; if (DIRECTED) return "This app does not calculate MST for directed graphs"; // create new graph to contain MST Graph mst = new Graph(false, true); // populate with all vertices for (int i=0; i pq = new PriorityQueue(); Edge e; vertexList.get(current).inTree = true; ntree++; while (ntree < nverts) { for (int j=0; j iter = pq.iterator(); while (iter.hasNext()) { Edge etmp = iter.next(); if (etmp.dest == e.dest) iter.remove(); } current = e.dest; vertexList.get(current).inTree = true; ntree++; } return "\nWeighted MST:\n" + mst + "\n"; } public String shortestPath(String src, String dest) { // make sure source and destination vertices exist int posSrc = find(src); if (posSrc == -1) return "Error: Source vertex not found: " + src; int posDest = find(dest); if (posDest == -1) return "Error: Destination vertex not found: " + dest; int i, j, v=0; for (i=0; i(); double wgt = adjacencyMatrix.get(posSrc).get(i); if (wgt == 0) wgt = Double.MAX_VALUE; else { if (i != posSrc) vertexList.get(i).minPath.add(posSrc); vertexList.get(i).minPath.add(i); } vertexList.get(i).minWeight = wgt; vertexList.get(i).weightFound = false; } vertexList.get(posSrc).minWeight = 0; vertexList.get(posSrc).weightFound = true; for (i=0; i(); for (int x=0; x