AStarSearch.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/EpsilonTest.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/PriorityQueue.h>
 
namespace ogdf {
 
 
template<typename T>
class AStarSearch {
private:
    using NodeQueue = PrioritizedMapQueue<node, T>;
 
    bool m_directed;
    double m_maxGap;
    EpsilonTest m_et;
 
    NodeArray<bool> m_folded;
    const EdgeArray<T>* m_cost = nullptr;
    std::function<T(node)> m_heuristic;
    NodeArray<edge>* m_predecessor = nullptr;
    NodeArray<T> m_distance;
    NodeQueue* m_queue = nullptr;
 
public:
    explicit AStarSearch(const bool directed = false, const double maxGap = 1,
            const EpsilonTest& et = EpsilonTest())
        : m_directed(directed), m_maxGap(maxGap), m_et(et) {
        OGDF_ASSERT(m_et.geq(maxGap, 1.0));
    }
 
    T call(
            const Graph& graph, const EdgeArray<T>& cost, const node source, const node target,
            NodeArray<edge>& predecessor, std::function<T(node)> heuristic = [](node) {
#ifdef _MSC_VER
                return 0;
#else
            return T(0);
#endif
            }) {
        // initialize auxiliary structures
        m_cost = &cost;
        m_distance.init(graph);
        m_predecessor = &predecessor;
        m_predecessor->init(graph);
        m_heuristic = heuristic;
 
        m_folded.init(graph, false);
        NodeQueue queue(graph);
        m_queue = &queue;
 
        m_distance[source] = 0;
        (*m_predecessor)[target] = nullptr;
        m_queue->push(source, 0);
 
        // investigate each node
        while (!m_queue->empty()) {
            node v = queue.topElement();
            queue.pop();
            m_folded[v] = true;
 
            if (v == target) {
                queue.clear();
            } else {
                investigateNode(v);
            }
        }
 
        OGDF_ASSERT((*m_predecessor)[target] == nullptr || validatePath(source, target));
 
        return m_distance[target];
    }
 
private:
#ifdef OGDF_DEBUG
    bool validatePath(const node source, const node target) const {
        NodeArray<bool> visited(*m_predecessor->graphOf(), false);
 
        OGDF_ASSERT(m_et.equal(m_distance[source], T(0)));
 
        for (node v = target; v != source;) {
            OGDF_ASSERT(!visited[v]);
 
            visited[v] = true;
            edge e = (*m_predecessor)[v];
 
            OGDF_ASSERT(e != nullptr);
 
            node w = e->opposite(v);
 
            OGDF_ASSERT(m_et.equal(m_distance[w] + (*m_cost)[e], m_distance[v]));
 
            v = w;
        }
 
        return true;
    }
#endif
 
    void investigateNode(const node v) {
        for (adjEntry adj = v->firstAdj(); adj != nullptr; adj = adj->succ()) {
            edge e = adj->theEdge();
            if (!m_directed || e->target() != v) {
                node w = e->opposite(v);
                T distanceW = m_distance[v] + (*m_cost)[e];
                if (!m_folded(w) && (!m_queue->contains(w) || m_et.less(distanceW, m_distance[w]))) {
                    m_distance[w] = distanceW;
                    (*m_predecessor)[w] = e;
                    T priority = (T)(m_distance[w] + m_maxGap * m_heuristic(w));
 
                    if (!m_queue->contains(w)) {
                        m_queue->push(w, priority);
                    } else {
                        m_queue->decrease(w, priority);
                    }
                }
            }
        }
    }
};
 
}