CIS 260 - Graphs II

Objectives

implement graph algorithms in Java
create and use graphs to solve problems
Graph implementation

Code to process graphs will be developed in class and posted to the page after class. It is expected that this will take both Tuesday and Thursday to complete.
Numerous changes were requested as we started to implement the code in class. The code below includes those requested changes.
/*
   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 Vector<Vertex> vertexList = new Vector<Vertex>();
   private Vector<Vector<Double>> adjacencyMatrix = new Vector<Vector<Double>>();
   private Vector<Vector<Edge>> adjacencyList = new Vector<Vector<Edge>>();

   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 Vector<Integer> 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<Edge> {
      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 Vector<Edge>());
         adjacencyMatrix.add(new Vector<Double>());

         // make sure there are no edges to new vertex from anywhere else
         for (int i=0; i<vertexList.size()-1; i++) {
            adjacencyMatrix.get(i).add(0.0);
         }

         // set all edges to zero for newly added vertex 
         for (int i=0; i<vertexList.size(); i++) {
            adjacencyMatrix.get(vertexList.size()-1).add(0.0);
         }

         return vertexList.size()-1;
      } else {
         System.err.println("Error: Duplicate vertex found on add: " + s);
         return -1;
      }
   }

   private int find(String s) {
      for (int i=0; i<vertexList.size(); i++) {
         if (vertexList.get(i).getName().equals(s)) return i;
      }
      return -1;
   }

   public boolean addEdge(String src, String dest) {
      return addEdge(src, dest, 1);
   }

   public boolean addEdge(String src, String dest, double weight) {
      int posSrc = find(src);
      if (posSrc == -1) posSrc = addVertex(src);
      int posDest = find(dest);
      if (posDest == -1) posDest = addVertex(dest);
      return addEdge(posSrc, posDest, weight);
   }

   private boolean addEdge(int posSrc, int posDest) {
      return addEdge(posSrc, posDest, 1);
   }

   private boolean addEdge(int posSrc, int posDest, double weight) {
      if (!WEIGHTED || weight==0) weight = 1;

      // check for existing edges (parallel edges not allowed in this implementation)
      if (adjacencyMatrix.get(posSrc).get(posDest) != 0) {
         System.err.println("Error: Edge already exists: " + vertexList.get(posSrc)
            + "->" + 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; i<vertexList.size(); i++) {
         s += vertexList.get(i) + " (" + i + ")\n";
      }

      s += "\nAdjacency list:\n";
      for (int i=0; i<vertexList.size(); i++) {
         s += vertexList.get(i) + ": ";
         for (int j=0; j<adjacencyList.get(i).size(); j++) {
            Edge e = adjacencyList.get(i).get(j);
            s += ((j>0?", ":"") + e);
         }
         s += "\n";
      }

      s += "\nAdjacency Matrix\n     ";
      for (int j=0; j<adjacencyMatrix.get(0).size(); j++) {
         s += String.format("%3s ", vertexList.get(j).getName());
      }
      s += "\n";
      for (int i=0; i<adjacencyMatrix.size(); i++) {
         s += String.format("%3s: ", vertexList.get(i).getName());
         for (int j=0; j<adjacencyMatrix.get(i).size(); j++) {
            s += String.format("%3d ", adjacencyMatrix.get(i).get(j).intValue());
         }
         s += "\n";
      }
      return s + "\n----- End of graph listing ---\n";
   }

   // finds an adjacent vertex to v which has not been visited
   public int getAdjacentUnvisited(int v) {
      for (int i=0; i<adjacencyList.get(v).size(); i++) {
         int n = adjacencyList.get(v).get(i).dest;
         if (!vertexList.get(n).visited) return n;
      }
      return -1;
   }

   public boolean isPath(String src, String dest) {
      // default isPath method uses depthFirst search
      return isPath(src, dest, true);
   }

   // use this method to specify depth-first or breadth-first
   public boolean isPath(String src, String dest, boolean depthFirst) {
      // make sure source vertex exists
      int posSrc = find(src);
      if (posSrc == -1) {
         System.out.println("Error: Vertex not found: " + src);
         return false;
      }

      // make sure destination vertex exists
      int posDest = find(dest);
      if (posDest == -1) {
         System.out.println("Error: Vertex not found: " + dest);
         return false;
      }
      
      // check for obvious case of same node
      if (posSrc == posDest) return true;

      // set all vertices to unvisited
      for (int i=0; i<vertexList.size(); i++) {
         vertexList.get(i).visited = false;
      }
      
      // handles both depth-first and breadth-first search
      Vector<Integer> v = new Vector<Integer>();
      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<vertexList.size(); i++) {
         mst.addVertex(vertexList.get(i).getName());
      }

      // set all vertices to not being in MST
      for (int i=0; i<vertexList.size(); i++) {
         vertexList.get(i).inTree = false;
      }

      int current = 0;  // current vertex
      int ntree   = 0;  // number of vertices connected in MST
      int nverts  = vertexList.size();  // number of vertices
      PriorityQueue<Edge> pq = new PriorityQueue<Edge>();
      Edge e;

      vertexList.get(current).inTree = true;
      ntree++;

      while (ntree < nverts) {
         for (int j=0; j<adjacencyList.get(current).size(); j++) {
            e = adjacencyList.get(current).get(j);
            if (!vertexList.get(e.dest).inTree) pq.add(e);
         }
         if (pq.isEmpty()) return "No MST - graph is not connected";
         
         // add lowest cost edge to MST
         e = pq.poll();
         mst.addEdge(e.src, e.dest, e.weight);
         
         // remove edges from priority queue with same destination
         Iterator<Edge> 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<vertexList.size(); i++) {
         vertexList.get(i).minPath = new Vector<Integer>();
         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<vertexList.size()-1; i++) {
         double minWeight = Double.MAX_VALUE;
         for (j=0; j<vertexList.size(); j++) {
            if (!vertexList.get(j).weightFound) {
               if (vertexList.get(j).minWeight < minWeight) {
                  v = j;
                  minWeight = vertexList.get(v).minWeight;
               }
            }
         }
         vertexList.get(v).weightFound = true;

         for (j=0; j<vertexList.size(); j++) {
            if (!vertexList.get(j).weightFound) {
               double wgt = adjacencyMatrix.get(v).get(j);
               if (wgt != 0 && (minWeight + wgt
                  < vertexList.get(j).minWeight)) {
                  vertexList.get(j).minWeight = minWeight + wgt;
                  vertexList.get(j).minPath = new Vector<Integer>();
                  for (int x=0; x<vertexList.get(v).minPath.size(); x++) {
                     vertexList.get(j).minPath.add(vertexList.get(v).minPath.get(x));
                  }
                  vertexList.get(j).minPath.add(j);
               }
            }
         }
      }

      String s = "Shortest path from " + src + " to " + dest + ": ";
      if (vertexList.get(posDest).minPath.size() == 0) return s + "Not found";
      for (int x=0; x<vertexList.get(posDest).minPath.size(); x++) {
         s += vertexList.get(posDest).minPath.get(x) + " ";
      }
      return s + "\n";
   }
}

public class TestGraph {
   public static void main(String[] args) {
      Graph g = new Graph(false, true);
      g.addEdge("A", "B", 3.0);
      g.addEdge("A", "C", 1.0);
      g.addEdge("B", "C", 1.0);
      g.addEdge("B", "D", 1.0);
      g.addEdge("C", "D", 3.0);
      System.out.println(g + "\n");
      System.out.println(g.shortestPath("A", "D") + "\n");
      System.out.println("Path from A to D: " + g.isPath("A", "D") + "\n");
      System.out.println(g.minimumSpanningTree() + "\n");
      System.out.println("After adding disconnected vertex M:\n");
      g.addVertex("M");
      System.out.println(g.shortestPath("A", "M") + "\n");
      System.out.println("Path from A to M: " + g.isPath("A", "M") + "\n");
      System.out.println(g.minimumSpanningTree() + "\n");
   }
}