Program Listing for File AStarGeneral.hpp¶

/*
 * AStarGeneral.hpp
 *
 *  Created on: 09.08.2019
 *      Author: Eugenio Angriman <angrimae@hu-berlin.de>
 */

#ifndef NETWORKIT_DISTANCE_A_STAR_GENERAL_HPP_
#define NETWORKIT_DISTANCE_A_STAR_GENERAL_HPP_

#include <networkit/auxiliary/VectorComparator.hpp>
#include <networkit/distance/STSP.hpp>

#include <tlx/container/d_ary_addressable_int_heap.hpp>

namespace NetworKit {

template <typename Heuristic>
class AStarGeneral final : public STSP {
public:
    AStarGeneral(const Graph &G, Heuristic heu, node source, node target, bool storePred = true)
        : STSP(G, source, target, storePred), heu(heu), heap{prio} {}

    /*
     * Executes the AStar algorithm.
     */
    void run() override {
        if (source == target) {
            distance = 0.;
            hasRun = true;
            return;
        }

        init();
        constexpr auto infdist = std::numeric_limits<edgeweight>::max();
        const count n = G->upperNodeIdBound();
        distance = infdist;

        std::fill(distFromSource.begin(), distFromSource.end(), infdist);
        distFromSource.resize(n, infdist);
        distFromSource[source] = 0.;

        std::fill(prio.begin(), prio.end(), infdist);
        prio.resize(n, infdist);
        prio[source] = 0.;

        heap.clear();
        heap.reserve(n);
        heap.push(source);

        node top = none;
        do {
            top = heap.extract_top();
            if (top == target) {
                distance = distFromSource[target];
                break;
            }

            G->forNeighborsOf(top, [&](node u, edgeweight w) {
                const double newDist = distFromSource[top] + w;
                if (newDist < distFromSource[u]) {
                    distFromSource[u] = newDist;
                    prio[u] = newDist + heu(u);
                    heap.update(u);
                    if (storePred) {
                        pred[u] = top;
                    }
                }
            });
        } while (!heap.empty());

        if (top != target) {
            WARN("Source cannot reach target!");
        } else if (storePred) {
            buildPath();
        }

        hasRun = true;
    }

private:
    // Priorities used for the heap
    std::vector<double> distFromSource, prio;
    // Lower bound of the distance to the target node
    Heuristic heu;

    tlx::d_ary_addressable_int_heap<node, 2, Aux::LessInVector<double>> heap;
};
} // namespace NetworKit

#endif // NETWORKIT_DISTANCE_A_STAR_GENERAL_HPP_