Dijkstra.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/EpsilonTest.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/PriorityQueue.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/heap/PairingHeap.h>
 
#include <functional>
#include <limits>
 
namespace ogdf {
 
template<typename T, template<typename P, class C> class H = PairingHeap>
class Dijkstra {
protected:
    EpsilonTest m_eps; 
 
public:
 
    void callUnbound(const Graph& G, const EdgeArray<T>& weight, const List<node>& sources,
            NodeArray<edge>& predecessor, NodeArray<T>& distance, bool directed = false,
            bool arcsReversed = false) {
        PrioritizedMapQueue<node, T, std::less<T>, H> queue(G);
        distance.init(G, std::numeric_limits<T>::max());
        predecessor.init(G, nullptr);
 
#ifdef OGDF_DEBUG
        // No source should be given multiple times.
        NodeArray<bool> isSource {G, false};
        for (node s : sources) {
            OGDF_ASSERT(!isSource[s]);
            isSource[s] = true;
        }
#endif
 
        // initialization
        for (node v : G.nodes) {
            queue.push(v, distance[v]);
        }
        for (node s : sources) {
            queue.decrease(s, (distance[s] = 0));
        }
 
#ifdef OGDF_DEBUG
        for (edge de : G.edges) {
            OGDF_ASSERT(weight[de] >= 0);
        }
#endif
 
        while (!queue.empty()) {
            node v = queue.topElement();
            queue.pop();
            if (!predecessor[v]
                    && m_eps.greater(distance[v], static_cast<T>(0))) { // v is unreachable, ignore
                continue;
            }
            for (adjEntry adj : v->adjEntries) {
                edge e = adj->theEdge();
                node w = adj->twinNode();
                if (directed
                        && ((!arcsReversed && e->target() == v)
                                || (arcsReversed && e->target() != v))) {
                    continue;
                }
 
                if (m_eps.greater(distance[w], distance[v] + weight[e])) {
                    OGDF_ASSERT(std::numeric_limits<T>::max() - weight[e] >= distance[v]);
                    queue.decrease(w, (distance[w] = distance[v] + weight[e]));
                    predecessor[w] = e;
                }
            }
        }
    }
 
 
    void callBound(const Graph& G, const EdgeArray<T>& weight, const List<node>& sources,
            NodeArray<edge>& predecessor, NodeArray<T>& distance, bool directed, bool arcsReversed,
            node target, T maxLength = std::numeric_limits<T>::max()) {
        PrioritizedMapQueue<node, T, std::less<T>, H> queue(G);
        distance.init(G, std::numeric_limits<T>::max());
        predecessor.init(G, nullptr);
 
        // initialization
        for (node s : sources) {
            queue.push(s, (distance[s] = 0));
        }
 
#ifdef OGDF_DEBUG
        for (edge de : G.edges) {
            OGDF_ASSERT(weight[de] >= 0);
        }
#endif
 
        while (!queue.empty()) {
            node v = queue.topElement();
            if (v == target) { // terminate early if this is our sole target
                break;
            }
 
            queue.pop();
            if (!predecessor[v]
                    && m_eps.greater(distance[v], static_cast<T>(0))) { // v is unreachable, ignore
                continue;
            }
            for (adjEntry adj : v->adjEntries) {
                edge e = adj->theEdge();
                node w = adj->twinNode();
                if (directed
                        && ((!arcsReversed && e->target() == v)
                                || (arcsReversed && e->target() != v))) {
                    continue;
                }
 
                const T newDistance = distance[v] + weight[e];
                if (m_eps.greater(newDistance, maxLength)) {
                    // using this edge would result in a path length greater than our upper bound
                    continue;
                }
                if (m_eps.greater(distance[w], newDistance)) {
                    OGDF_ASSERT(std::numeric_limits<T>::max() - weight[e] >= distance[v]);
                    distance[w] = newDistance;
                    if (queue.contains(w)) {
                        queue.decrease(w, distance[w]);
                    } else {
                        queue.push(w, distance[w]);
                    }
                    predecessor[w] = e;
                }
            }
        }
    }
 
 
    void callUnbound(const Graph& G, const EdgeArray<T>& weight, node s, NodeArray<edge>& predecessor,
            NodeArray<T>& distance, bool directed = false, bool arcsReversed = false) {
        List<node> sources;
        sources.pushBack(s);
        callUnbound(G, weight, sources, predecessor, distance, directed, arcsReversed);
    }
 
 
    void callBound(const Graph& G, const EdgeArray<T>& weight, node s, NodeArray<edge>& predecessor,
            NodeArray<T>& distance, bool directed, bool arcsReversed, node target,
            T maxLength = std::numeric_limits<T>::max()) {
        List<node> sources;
        sources.pushBack(s);
        callBound(G, weight, sources, predecessor, distance, directed, arcsReversed, target,
                maxLength);
    }
 
 
    void call(const Graph& G, const EdgeArray<T>& weight, const List<node>& sources,
            NodeArray<edge>& predecessor, NodeArray<T>& distance, bool directed = false,
            bool arcsReversed = false, node target = nullptr,
            T maxLength = std::numeric_limits<T>::max()) {
        if (target == nullptr && maxLength == std::numeric_limits<T>::max()) {
            callUnbound(G, weight, sources, predecessor, distance, directed, arcsReversed);
        } else {
            callBound(G, weight, sources, predecessor, distance, directed, arcsReversed, target,
                    maxLength);
        }
    }
 
 
    void call(const Graph& G, const EdgeArray<T>& weight, const node s, NodeArray<edge>& predecessor,
            NodeArray<T>& distance, bool directed = false, bool arcsReversed = false,
            node target = nullptr, T maxLength = std::numeric_limits<T>::max()) {
        if (target == nullptr && maxLength == std::numeric_limits<T>::max()) {
            callUnbound(G, weight, s, predecessor, distance, directed, arcsReversed);
        } else {
            callBound(G, weight, s, predecessor, distance, directed, arcsReversed, target, maxLength);
        }
    }
};
 
}