import java.io.File;
import java.util.Set;
import java.util.HashSet;
import java.util.Queue;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;

/**
 * Static methods for performing graph searches.
 *   @author Dave Reed
 *   @version 11/25/16
 */
public class GraphSearch {
    public static <E> void DFS1(Graph<E> g, E v) {
        GraphSearch.DFS1(g, v, new HashSet<E>());
    }
    
    private static <E> void DFS1(Graph<E> g, E v, Set<E> visited) {
        if (!visited.contains(v)) {
            System.out.println(v);
            visited.add(v);
            for (E adj : g.getAdj(v)) {
                GraphSearch.DFS1(g, adj, visited);
            }
        }
    }
    
    ////////////////////////////////////////////////////////////////////
    
    public static <E> void DFS2(Graph<E> g, E v) {
        Stack<E> unvisited = new Stack<E>();
        unvisited.push(v);
        Set visited = new HashSet<E>();
        while (!unvisited.isEmpty()) {
            E nextV = unvisited.pop();
            if (!visited.contains(nextV)) {
                System.out.println(nextV);
                visited.add(nextV);
                for (E adj : g.getAdj(nextV)) {
                    unvisited.push(adj);
                }
            }
        }
    }

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

    public static <E> void BFS(Graph<E> g, E v) {
        Queue<E> unvisited = new LinkedList<E>();
        unvisited.add(v);
        Set visited = new HashSet<E>();
        while (!unvisited.isEmpty()) {
            E nextV = unvisited.remove();
            if (!visited.contains(nextV)) {
                System.out.println(nextV);
                visited.add(nextV);
                for (E adj : g.getAdj(nextV)) {
                    unvisited.add(adj);
                }
            }
        }
    }

    ////////////////////////////////////////////////////////////////////
    
    public static <E> void topo(Graph<E> g, E v) {
        GraphSearch.topo(g, v, new HashSet<E>());
    }
    private static <E> void topo(Graph<E> g, E v, Set<E> visited) {
        if (!visited.contains(v)) {
            visited.add(v);
            for (E adj : g.getAdj(v)) {
                GraphSearch.topo(g, adj, visited);
            }
            System.out.println(v);
        }
    }

    
    ////////////////////////////////////////////////////////
    
    public static void main(String[] args) throws java.io.FileNotFoundException {
        System.out.print("Enter the graph file: ");
        
        Scanner input = new Scanner(System.in);
        String filename = input.next();
        
        Graph<String> g = new DiGraphList<String>();
        
        Scanner infile = new Scanner(new File(filename));
        while (infile.hasNext()) {
            String s1 = infile.next();
            String s2 = infile.next();
            g.addEdge(s1, s2);
        }
        
        System.out.print("Enter the start state: ");
        String start = input.next();
        
        GraphSearch.DFS1(g, start);
        
        System.out.println();
        
        GraphSearch.DFS2(g, start);
        
        System.out.println();
        
        GraphSearch.BFS(g, start);        

        System.out.println();
        
        GraphSearch.topo(g, start);  
    }
}