dijkstra.h

#ifndef GRAPHLIB_ALGORITHMS_DIJKSTRA_H
#define GRAPHLIB_ALGORITHMS_DIJKSTRA_H
 
#include <cassert>
#include <list>
#include <optional>
#include <queue>
#include <set>
#include <unordered_map>
#include <vector>
 
#include "GraphLib/internal/concepts.h"
#include "GraphLib/internal/util.h"
 
namespace GraphLib {
 
namespace Internal {

template <valid_weighted_graph_type G>
class DijkstraIterator {
public:
    /* Iterator concept requirements */
 
    using difference_type = std::ptrdiff_t; 
    using value_type = G::id_type;          

    DijkstraIterator(const G& graph, const value_type start) : graph(graph), start(start)
    {
        assert(graph.node_count() > 0);
        assert(graph.node_exists(start));
 
        frontier.push(priority_pair_type(edge_weight_type {}, start));
        node_lookup[start] = {start, edge_weight_type {}};
    }

    const DijkstraIterator begin() const
    {
        return DijkstraIterator(graph, start);
    }

    const DijkstraIterator end() const
    {
        DijkstraIterator end = DijkstraIterator<G>(graph, start);
        end.done = true;
        return end;
    }

    std::pair<value_type, value_type> operator*() const
    {
        const value_type best = frontier.top().value;
        return {best, node_lookup.at(best).first};
    }

    DijkstraIterator& operator++()
    {
        if (!done)
            perform_update();
        return *this;
    }
 
    bool operator==(const DijkstraIterator& other) const
    {
        if (!(other.graph == graph && other.start == start && other.done == done))
            return false;
        else if (done)
            return true;
        else
            return other.iterations == iterations;
    }
 
    bool operator!=(const DijkstraIterator& other) const
    {
        return !(*this == other);
    }
 
    /* State inspection methods */

    value_type get_current_pred(const value_type node) const
    {
        return node_lookup.at(node).first;
    }

    value_type get_current_cost(const value_type node) const
    {
        return node_lookup.at(node).second;
    }

    bool has_seen(const value_type node) const
    {
        return node_lookup.contains(node);
    }
 
private:
    /* Implementation details */
 
    using edge_weight_type = typename G::edge_type::weight_type;
    using priority_pair_type = Internal::PriorityPair<edge_weight_type, value_type>;
    using priority_queue_type =
        std::priority_queue<priority_pair_type, std::vector<priority_pair_type>, std::greater<priority_pair_type>>;
 
    const G& graph;
    const value_type start;
    bool done {false};
    unsigned long iterations {0};
 
    // maps all encountered nodes to their predecessor and best known costs
    std::unordered_map<value_type, std::pair<value_type, edge_weight_type>> node_lookup {};
 
    // holds the nodes already part of the spanning tree we're constructing
    std::set<value_type> closed_nodes {};
 
    // holds nodes reachable from the edge of the explored ("closed") graph
    // sorted by their cost. duplicates and elements whose nodes have since
    // been added to the closed list are possible because updating the heap
    // is expensive, and therefore need to be removed when encountered.
    priority_queue_type frontier {};

    void perform_update()
    {
        assert(!done);
 
        // pick the best node from the queue and remove it, then get its neighbors.
        // using structured bindings here, they work in the order of the public fields
        const auto [best_cost, best_node] = frontier.top();
        frontier.pop();
        const auto best_neighbors = graph.get_neighbors(best_node);
 
        // scan the picked node's neighbors and update their costs if better
        for (auto const node : best_neighbors) {
            if (closed_nodes.contains(node))
                continue;
 
            if (graph.get_edge(best_node, node).weight < 0)
                throw std::out_of_range("Graph with negative edge weight not permitted");
 
            const auto new_cost = best_cost + graph.get_edge_weight(best_node, node);
            if (!(node_lookup.contains(node) && new_cost >= node_lookup[node].second)) {
                node_lookup[node] = {best_node, new_cost};
                frontier.push(priority_pair_type(new_cost, node));
            }
        }
 
        closed_nodes.insert(best_node);
 
        // remove any revealed entries of closed nodes
        while (!frontier.empty() && closed_nodes.contains(frontier.top().value)) {
            frontier.pop();
        }
 
        if (frontier.empty())
            done = true;
 
        iterations++;
    }
};
 
} // namespace Internal


template <Internal::valid_weighted_graph_type G>
G dijkstra(const G& graph, const typename G::id_type start)
{
    if (!graph.node_exists(start))
        throw std::invalid_argument("Start node not in the passed graph");
 
    auto spanning_tree = G {};
    const auto explorer = Internal::DijkstraIterator<G>(graph, start);
 
    for (const auto [best, best_pred] : explorer) {
        spanning_tree.add_node_with_id(best, graph.get_node_data(best));
        if (best != start) {
            const auto edge = graph.get_edge(best_pred, best);
            spanning_tree.add_edge(best_pred, best, edge.weight);
        }
    }
 
    return spanning_tree;
}

template <Internal::valid_weighted_graph_type G>
std::optional<std::list<typename G::id_type>> uniform_cost_search(const G& graph, const typename G::id_type start,
                                                                  const typename G::id_type target)
{
    if (!(graph.node_exists(start) && graph.node_exists(start)))
        throw std::invalid_argument("Start and/or target node not in the passed graph");
 
    auto explorer = Internal::DijkstraIterator<G>(graph, start);
 
    for (; explorer != explorer.end(); ++explorer)
        if ((*explorer).first == target)
            break;
 
    if (!explorer.has_seen(target))
        return std::nullopt;
 
    auto path = std::list<typename G::id_type> {};
    path.push_front(target);
 
    typename G::id_type current = target;
    while (current != start) {
        current = explorer.get_current_pred(current);
        path.push_front(current);
    }
 
    return path;
}

} // namespace GraphLib
 
#endif