bfs.h

Go to the documentation of this file.

#ifndef GRAPHLIB_ALGORITHMS_BFS_H
#define GRAPHLIB_ALGORITHMS_BFS_H
 
#include <queue>
#include <set>
#include <vector>
 
#include "GraphLib/internal/concepts.h"

 
namespace GraphLib {


template <Internal::valid_graph_type G>
std::vector<typename G::id_type> breadth_first_search(const G& graph, typename G::id_type root,
                                                      typename G::id_type target)
{
    using id_type = G::id_type;
 
    if (!graph.node_exists(root)) {
        throw std::runtime_error("Root ID does not exist in Graph, cannot conduct BFS");
    } else if (!graph.node_exists(target)) {
        throw std::runtime_error("Target ID does not exist in Graph, cannot conduct BFS");
    }
 
    // speichere node und path zur node in queue
    std::queue<std::pair<id_type, std::vector<id_type>>> queue {{{root, {root}}}};
 
    std::set<id_type> seen {root};
    std::vector<id_type> path {};
 
    while (!queue.empty()) {
        auto [current_node, path_so_far] = queue.front();
        queue.pop();
 
        if (current_node == target)
            return path_so_far;
 
        for (id_type neighbor : graph.get_neighbors(current_node)) {
            if (!seen.contains(neighbor)) {
                auto new_path = path_so_far;
                new_path.push_back(neighbor);
                queue.push({neighbor, new_path});
            }
            seen.insert(neighbor);
        }
    }
    return std::vector<id_type> {};
}

template <Internal::valid_graph_type G>
G breadth_first_search(const G& graph, typename G::id_type root)
{
    using id_type = G::id_type;
 
    if (!graph.node_exists(root)) {
        throw std::runtime_error("Root ID does not exist in Graph, cannot construct Spanning Tree");
    }
 
    G mst {};
    std::set<id_type> seen {root};
    std::queue<id_type> queue({root});
 
    for (const auto& id : graph.get_nodes()) {
        mst.add_node_with_id(id, graph.get_node_data(id));
    }
 
    while (!queue.empty()) {
        id_type current = queue.front();
        queue.pop();
 
        for (id_type neighbor : graph.get_neighbors(current)) {
            if (!seen.contains(neighbor)) {
                if constexpr (Internal::valid_weighted_graph_type<G>) {
                    mst.add_edge(current, neighbor, graph.get_edge_weight(current, neighbor));
                } else {
                    mst.add_edge(current, neighbor);
                }
                seen.insert(neighbor);
                queue.push(neighbor);
            }
        }
    }
 
    return mst;
}

} // namespace GraphLib
 
#endif