import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import javafx.util.Pair;

/**
 * Static methods for performing graph searches.
 *   @author Dave Reed
 *   @version 11/25/18
 */
public class GraphSearch {
    
    public static <E> List<E> DFSrec(Graph<E> g, E start, E goal) {
        List<E> path = new ArrayList<E>();
        path.add(start);
        if (GraphSearch.DFSrec(g, path, goal)) {
            return path;
        }
        return null;
    }
    
    private static <E> boolean DFSrec(Graph<E> g, List<E> pathSoFar, E goal) {
        E lastVertex = pathSoFar.get(pathSoFar.size()-1);
        if (lastVertex.equals(goal)) {
            return true;
        }
        else {
            for (E adj : g.getAllAdjacent(lastVertex)) {
                if (!pathSoFar.contains(adj)) {
                    pathSoFar.add(adj);
                    if (GraphSearch.DFSrec(g, pathSoFar, goal)) {
                        return true;
                    }
                    pathSoFar.remove(pathSoFar.size()-1);
                }
            }
            return false;
        }
    }
    
    ////////////////////////////////////////////////////////////////////
    
    public static <E> List<E> DFS(Graph<E> g, E start, E goal) {
        List<E> startPath = new ArrayList<E>();
        startPath.add(start);
        
        Stack<List<E>> paths = new Stack<List<E>>();
        paths.push(startPath);
        
        while (!paths.isEmpty()) {
            List<E> pathToExtend = paths.pop();
            E current = pathToExtend.get(pathToExtend.size()-1);
            if (current.equals(goal)) {
                return pathToExtend;
            }
            else {
                for (E adj : g.getAllAdjacent(current)) {
                    if (!pathToExtend.contains(adj)) {
                        List<E> copy = new ArrayList<E>(pathToExtend);
                        copy.add(adj);
                        paths.push(copy);
                    }

                }
            }
        }
        return null;
    }

    ////////////////////////////////////////////////////////////////////

    public static <E> List<E> BFS(Graph<E> g, E start, E goal) {
        List<E> startPath = new ArrayList<E>();
        startPath.add(start);
        
        Queue<List<E>> paths = new LinkedList<List<E>>();
        paths.add(startPath);
        
        while (!paths.isEmpty()) {
            List<E> pathToExtend = paths.remove();
            E current = pathToExtend.get(pathToExtend.size()-1);
            if (current.equals(goal)) {
                return pathToExtend;
            }
            else {
                for (E adj : g.getAllAdjacent(current)) {
                    if (!pathToExtend.contains(adj)) {
                        List<E> copy = new ArrayList<E>(pathToExtend);
                        copy.add(adj);
                        paths.add(copy);
                    }
                }
            }
        }
        return null;
    }
    
    ////////////////////////////////////////////////////////
    
    public static void main(String[] args) throws java.io.FileNotFoundException {
        List<Pair<Integer, Integer>> edges = new ArrayList<Pair<Integer, Integer>>();
        edges.add(new Pair<Integer, Integer>(1, 2));
        edges.add(new Pair<Integer, Integer>(2, 3));
        edges.add(new Pair<Integer, Integer>(2, 4));
        edges.add(new Pair<Integer, Integer>(2, 5));
        edges.add(new Pair<Integer, Integer>(4, 5));
        edges.add(new Pair<Integer, Integer>(4, 6));
        edges.add(new Pair<Integer, Integer>(6, 3));        
             
        Graph<Integer> g = new DiGraphList<Integer>(edges);

        System.out.println("DFSrec " + GraphSearch.DFSrec(g, 1, 3));
        System.out.println("DFSrec " + GraphSearch.DFSrec(g, 1, 5));
        System.out.println();
        System.out.println("DFS " + GraphSearch.DFS(g, 1, 3));
        System.out.println("DFS " + GraphSearch.DFS(g, 1, 5));
        System.out.println();
        System.out.println("BFS " + GraphSearch.BFS(g, 1, 3));
        System.out.println("BFS " + GraphSearch.BFS(g, 1, 5)); 
    }
}