TestGraph.java

/*
    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<Vertex> vertexList = new ArrayList<Vertex>();
    private ArrayList<ArrayList<Double>> adjacencyMatrix = new ArrayList<ArrayList<Double>>();
    private ArrayList<ArrayList<Edge>> adjacencyList = new ArrayList<ArrayList<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 ArrayList<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 ArrayList<Edge>());
            adjacencyMatrix.add(new ArrayList<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
        ArrayList<Integer> v = new ArrayList<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 ArrayList<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 ArrayList<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");
    }
}