dfs.h

Go to the documentation of this file.

#ifndef GRAPHLIB_ALGORITHMS_DFS_H
#define GRAPHLIB_ALGORITHMS_DFS_H
 
#include <functional>
#include <set>
#include <vector>
 
#include "GraphLib/internal/concepts.h"

 
namespace GraphLib {


template <Internal::valid_graph_type G>
std::vector<typename G::id_type> depth_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 DFS");
    } else if (!graph.node_exists(target)) {
        throw std::runtime_error("Target ID does not exist in Graph, cannot conduct DFS");
    }
    std::set<id_type> seen {};
    std::vector<id_type> path {};
 
    // Helper-funktion für rekursives DFS
    std::function<bool(id_type, std::vector<id_type>&)> dfs_recursive =
        [&](id_type current, std::vector<id_type>& current_path) -> bool {
        if (current == target) {
            return true;
        }
 
        seen.insert(current);
 
        for (id_type neighbor : graph.get_neighbors(current)) {
            if (!seen.contains(neighbor)) {
                current_path.push_back(neighbor);
                if (dfs_recursive(neighbor, current_path)) {
                    return true;
                }
                current_path.pop_back();
            }
        }
        return false;
    };
 
    path.push_back(root);
    if (dfs_recursive(root, path)) {
        return path;
    }
 
    return std::vector<id_type> {};
}

template <Internal::valid_graph_type G>
G depth_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 {};
 
    for (const auto& id : graph.get_nodes()) {
        mst.add_node_with_id(id, graph.get_node_data(id));
    }
 
    std::function<void(id_type)> dfs_recursive = [&](id_type current) {
        seen.insert(current);
 
        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);
                }
                dfs_recursive(neighbor);
            }
        }
    };
 
    dfs_recursive(root);
    return mst;
}

} // namespace GraphLib
 
#endif