/*
 *  ======================================================================
 *  Compilation:  javac BFSearcher.java
 *  Dependencies: Queue.java Graph.java
 *  
 *  Runs breadth first search (BFS) algorithm from source s on a graph G.
 *  After preprocessing the graph, can process shortest path queries
 *  from any vertex v to s.
 *
 *  ======================================================================
 */

public class BFSearcher {
    private SymbolTable visited = new SymbolTable();

    // Run BFS in graph G from given source vertex s

    public BFSearcher(Graph G, String s) {

        // put source on the queue

        Queue q = new Queue();
        q.enqueue(s);
        visited.put(s, "");
        
        while (!q.isEmpty()) {
            String v = (String) q.dequeue();
            String[] neighbors = G.neighbors(v);
            for (int i = 0; i < neighbors.length; i++) {
                String w = neighbors[i];
                if (visited.get(w) == null) {
                    q.enqueue(w);
                    visited.put(w, v);
                }
            }
        }
    }

    // Is v reachable from the source s

    public boolean isReachable(String v) { return visited.get(v) != null; }

    // Compute the length of the shortest path from v to s

    public int pathLength(String v) {
        int len = -1;
        while (visited.get(v) != null) {
            v = (String) visited.get(v);
            len++;
        }
        return len;
    }

    // Print the shortest path from v to s to standard output

    public void showPath(String v) {
        while (visited.get(v) != null) {
            System.out.println(v);
            v = (String) visited.get(v);
        }
    }

    // Return the shortest path from v to s as an array of strings

    public String[] path(String v) { 
        int N = pathLength(v);
        String[] p = new String[N+1];
        for (int i = 0; i <= N; i++) {
            p[i] = v;
            v = (String) visited.get(v);
        }
        return p;
    }
}