import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class UnweightedGraph {
    private final int DEFAULT_SIZE = 10;
    private ArrayList<Vertex> vertices;
    private int numVertices;
    private boolean undirected;
    
    /**
     * Constructor
     */
    public UnweightedGraph() {
        vertices = new ArrayList<Vertex>();
        for( int i = 0; i < DEFAULT_SIZE ; i++ ) vertices.add(null);
        numVertices = 0;
        undirected = false;
    } // end constructor
    
    /**
     * Constructor with parameter
     * @param if undirected is true then the graph is undirected
     */
    public UnweightedGraph(boolean undirected) {
        vertices = new ArrayList<Vertex>();
        for( int i = 0; i < DEFAULT_SIZE ; i++ ) vertices.add(null);
        numVertices = 0;
        this.undirected = undirected;
    } // end constructor
    
    /**
     * Constructor with parameters
     * @param size is the number of vertices
     * @param if undirected is true then the graph is undirected
     */
    public UnweightedGraph(boolean undirected, int size) {
        vertices = new ArrayList<Vertex>();
        for( int i = 0; i < size; i++ ) {
            vertices.add(new Vertex(i));
        } // end for
        numVertices = size;
        this.undirected = undirected;
    } // end constructor
    
    /**
     * This adds an edge to the graph
     * @param the edge is from vertex v1 to vertex v2
     */
    public void addEdge(int v1, int v2) {
        if( v1 >= vertices.size() ) resize(v1);
        if( vertices.get(v1) == null ) {
            vertices.set(v1,new Vertex(v1));
            numVertices++;
        } // end if
        if( v2 >= vertices.size() ) resize(v2);
        if( vertices.get(v2) == null ) {
            vertices.set(v2,new Vertex(v2));
            numVertices++;
        } // end if
        vertices.get(v1).adjList.add( new Edge(v2) );
        if( undirected ) {
            vertices.get(v2).adjList.add( new Edge(v1) );
        } // end if
    }// end addEdge
    
    /**
     * Checks for vertex2 adjacent to vertex 1
     * @param - the vertices
     * @return true if vertex2 adjacent to vertex1
     */
    public boolean isAdjacent(int vertex1, int vertex2) {
        return vertices.get(vertex1).adjList.contains(new Edge(vertex2));
    }
    
    /**
     * Does a depth first search of the graph
     * @return a String of the vertices on a depth first serach
     */
    public String depthFirstSearch(int start) {
        resetGraph();
        String out = " ";
        Stack<Vertex> s = new Stack<Vertex>();
        s.push(vertices.get(start));
        vertices.get(start).marked = true;
        while( !s.isEmpty() ) {
            Vertex newVertex = s.pop();
            out += newVertex.name + " ";
            for( Edge edge : newVertex.adjList ) {
                Vertex nextVertex = vertices.get(edge.vertex);
                if( !nextVertex.marked ) {
                    s.push(nextVertex);
                    nextVertex.marked = true;
                } // end if
            } // end for
        } // end while
        return out;
    } // end depthFirstSearch
    
    
    /**
     * Does a breadth first search of the graph
     * @return a String of the vertices on a breadth first serach
     */
    public String breadthFirstSearch(int start) {
        resetGraph();
        String out = " ";
        Queue<Vertex> q = new LinkedQueue<Vertex>();
        q.enqueue(vertices.get(start));
        vertices.get(start).marked = true;
        while( !q.isEmpty() ) {
            Vertex newVertex = q.dequeue();
            out +=  newVertex.name  + " ";
            for( Edge edge : newVertex.adjList ) {
                Vertex nextVertex = vertices.get(edge.vertex);
                if( !nextVertex.marked ) {
                    q.enqueue(nextVertex);
                    nextVertex.marked = true;
                } // end if
            } // end for
        } // end while
        return out;
    } // end breadthFirstSearch
    
    /**
     * Calculates all shortest paths from a start vertex
     * @param the start vertex
     */
    public void allShortestPaths(int fromVertex) {
        resetGraph();
        Queue<Vertex> q = new LinkedQueue<Vertex>();
        q.enqueue(vertices.get(fromVertex));
        vertices.get(fromVertex).marked = true;
        while( !q.isEmpty() ) {
            Vertex newVertex = q.dequeue();
            for( Edge edge : newVertex.adjList ) {
                Vertex nextVertex = vertices.get(edge.vertex);
                if( !nextVertex.marked ) {
                    q.enqueue(nextVertex);
                    nextVertex.marked = true;
                    nextVertex.previous = newVertex.name;
                } // end if
            } // end while Itr.hasNext())
        } // end while !Q.isEmpty())
    } // end allShortestPaths
    
    /**
     * Finds the shortest path to a particular vertex
     * @return a String of the vertices on the shortest path
     */
    public String shortestPath(int toVertex) {
        if( !vertices.get(toVertex).marked ) return " " + toVertex + " is unreachable";
        if( vertices.get(toVertex).previous != -1 ) {
            return shortestPath(vertices.get(toVertex).previous) + " " + toVertex;
        } else {
            return " " + toVertex;
        } // end if
    } // end shortestPath
    
    /**
     * Finds the shortest path to a particular vertex
     * @return an ArrayList<Integer> of the vertices on the shortest path
     */
    public ArrayList<Integer> shortestPathArray(int toVertex) {
        if( !vertices.get(toVertex).marked ) return null;
        if(vertices.get(toVertex).previous == -1 ) {
            ArrayList<Integer> path = new ArrayList<Integer>();
            path.add(toVertex);
            return path;
        } else {
            ArrayList<Integer> path = shortestPathArray(vertices.get(toVertex).previous);
            path.add(toVertex);
            return path;
        }// end if
    } // end shortestPathArray
    
    /**
     * The number of vertices in the graph
     * @return the number of vertices
     */
    public int numberOfVertices() {
        return numVertices;
    } // end numberOfVertices
    
    /**
     * @return the adjacentcy lists as a String
     */
    public String toString() {
        String out = "";
        for( int i = 0; i < numVertices; i++ ) {
            out = out + "Vertex " + i + " adjacent vertices:  ";
            if( vertices.get(i) == null ) {
                out = "Vertices must be numbered consecutively";
                return out;
            }// end for
            for( Edge edge : vertices.get(i).adjList ) {
                out = out + edge + " ";
            } // end for
            out = out + '\n';
        } // end for
        return out;
    } // end toString
    
    private void resetGraph() {
        for( int v = 0; v < numVertices; v++ ) {
            vertices.get(v).marked = false;
            vertices.get(v).previous = -1;
        } // end for
    } // end resetGraph
    
    private class Edge {
        int vertex;
        Edge(int vertex) {
            this.vertex = vertex;
        }
        public boolean equals(Object x) {
            if( x == null ) return false;
            if( !this.getClass().equals(x.getClass()) ) return false;
            return ((Edge)x).vertex == vertex;
        } // end equals
        public String toString() {
            return "  " + vertex;
        }
    } // end Edge
    
    private class Vertex {
        int name;
        List<Edge> adjList;
        boolean marked;
        int previous;
        Vertex(int name) {
            this.name = name;
            adjList = new LinkedList<Edge>();
            marked = false;
            previous = -1;
        }
    } // end Vertex
    
    private void resize(int size) {
        ArrayList<Vertex> temp = vertices;
        vertices = new ArrayList<Vertex>(size+1);
        for( int i = 0; i < temp.size(); i++ ) vertices.add(temp.get(i));
        for( int i = temp.size(); i < size + 1; i++ ) vertices.add(null);
    } // end resize
    
} // end UnweightedGraph