/* 
 * Graph.java
 * 
 * Computer Science E-22, Harvard University
 */

import java.io.*;
import java.util.*;

/**
 * An implementation of a Graph ADT.
 */
public class Graph {
    /*
     * Vertex - a private inner class for representing a vertex.
     */
    private class Vertex {
        private String id;
        private Edge edges;           // adjacency list, sorted by edge cost
        private Vertex next;          // next Vertex in linked list
        private boolean encountered;
        private boolean done;
        private Vertex parent;        // preceding vertex in path from root
        private double cost;          // cost of shortest known path
        
        private Vertex(String id) {
            this.id = id;
            cost = Double.POSITIVE_INFINITY;
        }
        
        /*
         * reinit - reset the starting values of the fields used by
         * the various algorithms, removing any values set by previous
         * uses of the algorithms.
         */
        private void reinit() {
            done = false;
            encountered = false;
            parent = null;
            cost = Double.POSITIVE_INFINITY;
        }
        
        /*
         * addToAdjacencyList - add the specified edge to the
         * adjacency list for this vertex.
         */
        private void addToAdjacencyList(Edge e) {
            /* Add to the front of the list. */
            e.next = edges;
            edges = e;
        }
        
        /*
         * pathString - returns a string that specifies the path from
         * the root of the current spanning tree (if there is one) to
         * this vertex.  If this method is called after performing
         * Dijkstra's algorithm, the returned string will specify the
         * shortest path.
         */
        private String pathString() {
            String str;
            
            if (parent == null) {
                str = id;         /* base case: this vertex is the root */
            } else {
                str = parent.pathString() + " -> " + id;
            }
            
            return str;
        }
        
        /*
         * toString - returns a string representation of the vertex 
         * of the following form:
         *    vertex v:
         *            edge to vi (cost = c1i)
         *            edge to vj (cost = c1j)
         *            ...
         */
        public String toString() {
            String str = "vertex " + id + ":\n";
            
            /* 
             * Iterate over the edges, adding a line to the string for
             * each of them.
             */
            Edge e = edges;
            while (e != null) {
                // Note: we have to use just the id field of the 
                // end vertex, or else we'll get infinite recursion!
                str += "\tedge to " + e.end.id;
                str += " (cost = " + e.cost + ")\n"; 
                
                e = e.next;
            }
            
            return str;
        }
    }
    
    /*
     * Edge - a private inner class for representing an edge.
     */
    private class Edge {
        private Vertex start;
        private Vertex end;
        private double cost;
        private Edge next;            // next Edge in adjacency list
        
        private Edge(Vertex start, Vertex end, double cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
    }
    
    /******* Graph instance variables and method start here. *********/
    
    /* A linked list of the vertices in the graph. */
    private Vertex vertices;
    
    /*
     * reinitVertices - private helper method that resets the starting
     * state of all of the vertices in the graph, removing any values
     * set by previous uses of the algorithms.
     */
    private void reinitVertices() {
        Vertex v = vertices;
        while (v != null) {
            v.reinit();
            v = v.next;
        }
    }
    
    /*
     * getVertex - private helper method that returns a reference to
     * the vertex with the specified id.  If the vertex isn't
     * in the graph, it returns null.
     */
    private Vertex getVertex(String id) {
        Vertex v = vertices;
        
        while (v != null && !v.id.equals(id)) {
            v = v.next;
        }
        
        return v;
    }
    
    /*
     * addVertex - private helper method that adds a vertex with
     * the specified id and returns a reference to it.
     */
    private Vertex addVertex(String id) {
        Vertex v = new Vertex(id);
        
        /* Add to the front of the list. */
        v.next = vertices;
        vertices = v;
        
        return v;
    }
    
    /**
     * addEdge - add an edge with the specified cost, and with start
     * and end vertices that have the specified IDs.  The edge will
     * be stored in the adjacency list of the start vertex.  If a
     * specified vertex isn't already part of the graph, it will be
     * added, too.
     */
    public void addEdge(String startVertexID, String endVertexID, double cost) {
        Vertex start = getVertex(startVertexID);
        if (start == null) {
            start = addVertex(startVertexID);
        }
        
        Vertex end = getVertex(endVertexID);
        if (end == null) {
            end = addVertex(endVertexID);
        }
        
        Edge e = new Edge(start, end, cost);
        start.addToAdjacencyList(e);
    }
    
    /**
     * toString - returns a concatenation of the string
     * representations of all of the vertices in the graph.
     */
    public String toString() {
        String str = "";
        
        Vertex v = vertices;
        while (v != null) {
            str += v;
            v = v.next;
        }
        
        return str;
    }
    
    /**
     * initFromFile - initialize a graph using the information in the
     * specified file.  The file should be a text file consisting of
     * lines that specify the edges of the graph in the following form:
     *     <start vertex data> <end vertex data> <cost>
     */
    public void initFromFile(String fileName) {
        String lineString = "";
        
        try {
            /* This Scanner will scan the file, one line at a time. */
            Scanner file = new Scanner(new File(fileName));
            
            /* Parse the file, one line at a time. */
            while (file.hasNextLine()) {
                lineString = file.nextLine();
                Scanner line = new Scanner(lineString);
                
                String startID = line.next();
                String endID = line.next();
                double cost = line.nextDouble();
                addEdge(startID, endID, cost);
            }
        } catch (IOException e) {
            System.out.println("Error accessing " + fileName);
            System.exit(1);
        } catch (NoSuchElementException e) {
            System.out.println("invalid input line: " + lineString);
            System.exit(1);
        }
    }
    
    /**
     * depthFirstTrav - perform a depth-first traversal starting from
     * the vertex with the specified ID.  After making sure that the
     * start vertex exists, it makes an initial call to the recursive
     * method dfTrav, which does the actual traversal.
     */
    public void depthFirstTrav(String originID) {
        reinitVertices();
        
        /* Get the specified start vertex. */
        Vertex start = getVertex(originID);
        if (start == null) {
            throw new IllegalArgumentException("no such vertex: " + originID);
        }
        
        /* Start the recursion rolling... */
        dfTrav(start, null);
    }
    
    /*
     * dfTrav - a recursive method used to perform a depth-first
     * traversal, starting from the specified vertex v.  The parent
     * parameter specifies v's parent in the depth-first spanning
     * tree.  In the initial invocation, the value of parent should be
     * null, because the starting vertex is the root of the spanning
     * tree.
     */
    private static void dfTrav(Vertex v, Vertex parent) {
        /* Visit v. */
        System.out.println(v.id);
        v.done = true;
        v.parent = parent;
        
        Edge e = v.edges;
        while (e != null) {
            Vertex w = e.end;
            if (!w.done) {
                dfTrav(w, v);
            }
            e = e.next;
        }
    }
    
    /**
     * breadthFirstTrav - perform a breadth-first traversal starting from
     * the vertex with the specified ID.
     */
    public void breadthFirstTrav(String originID) {
        reinitVertices();
        
        /* Get the specified start vertex. */
        Vertex origin = getVertex(originID);
        if (origin == null) {
            throw new IllegalArgumentException("no such vertex: " + originID);
        }
        
        bfTrav(origin);
    }
    
    private static void bfTrav(Vertex origin) {
        /* Mark the origin as encountered, and add it to the queue. */
        origin.encountered = true;
        origin.parent = null;
        Queue<Vertex> q = new LLQueue<Vertex>();
        q.insert(origin);
        
        while (!q.isEmpty()) {
            /* Remove a vertex v and visit it. */
            Vertex v = q.remove();
            System.out.println(v.id);
            
            /* Add v's unencountered neighbors to the queue. */
            Edge e = v.edges;
            while (e != null) {
                Vertex w = e.end;
                if (!w.encountered) {
                    w.encountered = true;
                    w.parent = v;
                    q.insert(w);
                }
                e = e.next;
            }
        }
    }
    
    /**
     * dijkstra - apply Dijkstra's algorithm starting from the
     * specified origin vertex to find the shortest path from the
     * origin to all other vertices that can be reached from the
     * origin.
     *
     * The method prints the vertices in the order in which they are
     * finalized.  For each vertex v, it lists the total cost of the
     * shortest path from the origin to v, as well as v's parent
     * vertex.  Tracing back along the parents gives the shortest
     * path.
     */
    public void dijkstra(String originID) {
        /* This will give all vertices an infinite cost. */
        reinitVertices();
        
        /* Get the origin and set its cost to 0. */
        Vertex origin = getVertex(originID);
        if (origin == null) {
            throw new IllegalArgumentException("no such vertex: " + originID);
        }
        origin.cost = 0;
        
        while (true) {
            /* Find the unfinalized vertex with the minimal cost. */
            Vertex w = null;
            Vertex v = vertices;
            while (v != null) {
                if (!v.done && (w == null || v.cost < w.cost)) {
                    w = v;
                }
                v = v.next;
            }
            
            /* 
             * If there are no unfinalized vertices, or if all of the
             * unfinalized vertices are unreachable from the origin
             * (which is the case if the w.cost is infinite), then
             * we're done.
             */
            if (w == null || w.cost == Double.POSITIVE_INFINITY) {
                return;
            }
            
            /* Finalize w. */
            System.out.println("\tfinalizing " + w.id + " (cost = " + w.cost +
              (w.parent == null ? ")" : ", parent = " + w.parent.id + ")"));
            System.out.println("\t\tpath = " + w.pathString());
            w.done = true;
            
            /* Try to improve the estimates of w's unfinalized neighbors. */
            Edge e = w.edges;
            while (e != null) {
                Vertex x = e.end;
                if (!x.done) {
                    double cost_via_w = w.cost + e.cost;
                    if (cost_via_w < x.cost) {
                        x.cost = cost_via_w;
                        x.parent = w;
                    }
                }
                e = e.next;
            }
        }
    }
    
    /**
     * prim - apply Prim's algorithm starting from the specified
     * vertex to find a minimum spanning tree for the graph.  
     * The method assumes that the graph is connected.
     *
     * The "done" instance variable is used to divide the vertices
     * into two sets.  Initially, the origin is in one set (the one
     * containing vertices for which done == true), and all other
     * vertices are in a second set (the one containing vertices for
     * which done == false).  We repeatedly add the lowest-cost edge
     * joining a vertex in the first set to a vertex in the second
     * set, and then we move the vertex in the second set to the first
     * set by setting its done field to true.
     */
    public void prim(String originID) {
        reinitVertices();
        
        /* Get the origin and mark it as done. */
        Vertex origin = getVertex(originID);
        if (origin == null) {
            throw new IllegalArgumentException("no such vertex: " + originID);
        }
        origin.done = true;
        
        while (true) {
            /* 
             * Find the minimal-cost edge linking a done vertex with
             * one that isn't done. 
             */
            Edge edgeToAdd = null;
            Vertex v = vertices;
            while (v != null) {
                if (v.done) {
                    Edge e = v.edges;
                    while (e != null) {
                        if (!e.end.done && 
                            (edgeToAdd == null || e.cost < edgeToAdd.cost)) {
                            edgeToAdd = e;
                        }
                        e = e.next;
                    }
                }
                v = v.next;
            }
            
            /* 
             * If no such edge exists, we're done.
             */
            if (edgeToAdd == null) {
                return;
            }
            
            /* Add the edge and mark its end vertex done. */
            System.out.println("\tadding edge (" + edgeToAdd.start.id + ", " +
              edgeToAdd.end.id + ")");
            edgeToAdd.end.parent = edgeToAdd.start;
            edgeToAdd.end.done = true;
        }
    }
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        Graph g = new Graph();
        
        System.out.print("Graph info file: ");
        String fileName = in.nextLine();
        g.initFromFile(fileName);
        
        System.out.print("starting point: ");
        String start = in.nextLine();
        
        System.out.println("depth-first traversal from " + start + ":");
        g.depthFirstTrav(start);
        
        System.out.println("breadth-first traversal from " + start + ":");
        g.breadthFirstTrav(start);
        
        System.out.println("Dijkstra's algorithm from " + start + ":");
        g.dijkstra(start);
        
        System.out.println("Prim's algorithm from " + start + ":");
        g.prim(start);
    }
}