class Graph {
    constructor() {
        this.vertices = [];
        this.adjacentList = new Map();
    }

    addVertex(v) {
        this.vertices.push(v);
        this.adjacentList.set(v, []);
    }

    getAdjacencyListVertex(v) {
        return this.adjacentList.get(v);
    }

    addEdge(u, v) {
        let uVertex = this.getAdjacencyListVertex(u);
        let vVertex = this.getAdjacencyListVertex(v);

        uVertex.push(v);
        vVertex.push(u);
    }

    DFSUtil(v, visited, route) {
        visited[v] = true;
        route.push(v);

        this.getAdjacencyListVertex(v).forEach(neighbor => {
            if (!visited[neighbor]) {
                this.DFSUtil(neighbor, visited, route);
            }
        })
    }

    DFS(v) {
        let visited = {};
        let route = [];

        this.DFSUtil(v, visited, route)
        return route;
    }

    BFS(source, dest, pred=[]) {
        const visited = { [source]: true };
        let queue = [[source, 0]];

        while(queue.length) {
            const [ s, dist ] = queue.shift();
            for (const neighbor of this.getAdjacencyListVertex(s)) {
                if(!visited[neighbor]) {
                    pred[neighbor] = [s, dist];
                    if (neighbor === dest) {
                        return [dest, dist + 1];
                    }
                    queue.push([ neighbor, dist + 1]);
                    visited[neighbor] = true;
                }
            }
        }

        return false;
    }

    findShortestRoute(u, v) {
        const pred = [];
        const path = [];
        if (!this.BFS(u, v, pred)) {
            return `There is no path from ${u} to ${v}.`;
        }
        let crawl = v;
        path.unshift(crawl);
        while(pred.hasOwnProperty(crawl)) {
            path.unshift(pred[crawl][0]);
            crawl = pred[crawl][0];
        }

        return {
            'len': path.length - 1,
            path
        };
    }
}

let g = new Graph();

g.addVertex('a');
g.addVertex('b');
g.addVertex('c');
g.addVertex('d');
g.addVertex('e');

g.addEdge('a', 'c');
g.addEdge('a', 'd');
g.addEdge('d', 'b');
g.addEdge('c', 'e');

console.log(g.getAdjacencyListVertex('a'));
console.log(g);
console.log(g.BFS('a', 'b'));
console.log(g.BFS('a', 'f'));
console.log(g.findShortestRoute('a', 'b'));
console.log(g.findShortestRoute('a', 'b'));
console.log(g.findShortestRoute('a', 'f'));
console.log(g.findShortestRoute('b', 'e'));

console.log(g.DFS('a'));