// bfs.cpp (Breadth First Search)

#include "graph.h"
#include "queue.h"

Graph bfs(const Graph & graph, Graph::NodeId start_node)
{
    std::vector<bool> visited(graph.num_nodes(), false);
    std::vector<int> dist(graph.num_nodes(), -1);
    Graph bfs_tree(graph.num_nodes(), graph.dirtype);
    Queue<Graph::NodeId> queue;

    std::cout << "The following vertices are reachable from vertex "
              << start_node << ":\n";
    queue.push_back(start_node);
    visited[start_node] = true;
    dist[start_node] = 0;

    while (not queue.is_empty()) {
        auto cur_nodeid = queue.pop_front();
        std::cout << "Vertex " << cur_nodeid << " has distance "
                  << dist[cur_nodeid] << ".\n";
        for (auto neighbor: graph.get_node(cur_nodeid).adjacent_nodes()) {
            if (not visited[neighbor.id()]) {
                visited[neighbor.id()] = true;
                dist[neighbor.id()] = dist[cur_nodeid] + 1;
                bfs_tree.add_edge(cur_nodeid, neighbor.id());
                queue.push_back(neighbor.id());
            }
        }
    }

    return bfs_tree;
}


int main(int argc, char* argv[])
{
    if (argc > 1) {
        Graph g(argv[1], Graph::directed);              // read digraph from file
        Graph bfs_tree = bfs(g, 0);
        std::cout << "The following is a BFS-tree rooted at 0:\n";
        bfs_tree.print();
    }
}