SpannerModule.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/EpsilonTest.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphAttributes.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/Module.h>
#include <ogdf/basic/Stopwatch.h>
#include <ogdf/basic/basic.h>
#include <ogdf/graphalg/ShortestPathAlgorithms.h>
 
#include <cstdint>
#include <string>
 
namespace ogdf {
 
template<typename TWeight>
class SpannerModule : public Module {
public:
    SpannerModule() : m_GA(nullptr) { }
 
    // destruction
    virtual ~SpannerModule() { }
 
    virtual ReturnType call(const GraphAttributes& GA, double stretch, GraphCopySimple& spanner,
            EdgeArray<bool>& inSpanner) {
        init(GA, stretch, spanner, inSpanner);
#ifdef OGDF_DEBUG
        std::string error;
        OGDF_ASSERT(preconditionsOk(GA, stretch, error));
#endif
 
        if (isTimelimitEnabled()) {
            m_watch.start(true);
        }
        ReturnType result;
        try {
            result = execute();
        } catch (const TimeoutException&) {
            result = ReturnType::TimeoutInfeasible;
        }
        if (isTimelimitEnabled()) {
            m_watch.stop();
        }
        return result;
    }
 
    virtual bool preconditionsOk(const GraphAttributes& GA, double stretch, std::string& error) = 0;
 
    void setTimelimit(int64_t milliseconds) { m_timelimit = milliseconds; }
 
    int64_t getTimeNeeded() { return m_watch.milliSeconds(); }
 
protected:
    const GraphAttributes* m_GA;
    double m_stretch;
    GraphCopySimple* m_spanner;
    EdgeArray<bool>* m_inSpanner;
 
    virtual void init(const GraphAttributes& GA, double stretch, GraphCopySimple& spanner,
            EdgeArray<bool>& inSpanner) {
        m_GA = &GA;
        m_stretch = stretch;
        m_spanner = &spanner;
        m_inSpanner = &inSpanner;
 
        const Graph& G = GA.constGraph();
        m_spanner->clear();
        m_spanner->setOriginalGraph(G);
        for (node n : G.nodes) {
            m_spanner->newNode(n);
        }
        m_inSpanner->init(G, false);
    }
 
    virtual ReturnType execute() = 0;
 
    bool isTimelimitEnabled() { return m_timelimit != -1; }
 
    int64_t getTimeLeft() { return m_timelimit - getTimeNeeded(); }
 
    void assertTimeLeft() {
        if (isTimelimitEnabled() && getTimeLeft() <= 0) {
            throw TimeoutException();
        }
    }
 
private:
    int64_t m_timelimit = -1; 
    StopwatchCPU m_watch; 
 
protected:
    struct TimeoutException {
    }; 
 
public:
    static bool isMultiplicativeSpanner(const GraphAttributes& GA, const GraphCopySimple& spanner,
            double stretch);
 
    static void apspSpanner(const GraphAttributes& GA, const GraphCopySimple& spanner,
            NodeArray<NodeArray<TWeight>>& shortestPathMatrix);
 
protected:
    static TWeight getWeight(const GraphAttributes& GA, edge e);
};
 
template<typename TWeight>
void SpannerModule<TWeight>::apspSpanner(const GraphAttributes& GA, const GraphCopySimple& spanner,
        NodeArray<NodeArray<TWeight>>& shortestPathMatrix) {
    EdgeArray<TWeight> weights(spanner);
    for (edge e : spanner.edges) {
        weights[e] = getWeight(GA, spanner.original(e));
    }
    dijkstra_SPAP(spanner, shortestPathMatrix, weights);
}
 
template<typename TWeight>
bool SpannerModule<TWeight>::isMultiplicativeSpanner(const GraphAttributes& GA,
        const GraphCopySimple& spanner, double stretch) {
    const Graph& G = GA.constGraph();
    OGDF_ASSERT(&(spanner.original()) == &G);
 
    if (G.numberOfNodes() != spanner.numberOfNodes()) {
        return false;
    }
 
    NodeArray<NodeArray<TWeight>> originalDistances(G);
    EdgeArray<TWeight> weights(G);
    for (edge e : G.edges) {
        weights[e] = getWeight(GA, e);
    }
    dijkstra_SPAP(G, originalDistances, weights);
 
    NodeArray<NodeArray<TWeight>> newDistances(spanner);
    apspSpanner(GA, spanner, newDistances);
 
    EpsilonTest m_eps;
    for (edge e : G.edges) {
        node u = e->source();
        node v = e->target();
        TWeight originalDistance = originalDistances[u][v];
        TWeight newDistance = newDistances[spanner.copy(u)][spanner.copy(v)];
        if (m_eps.greater(static_cast<double>(newDistance), stretch * originalDistance)) {
            return false;
        }
    }
 
    return true;
}
 
template<>
inline int SpannerModule<int>::getWeight(const GraphAttributes& GA, edge e) {
    if (GA.has(GraphAttributes::edgeIntWeight)) {
        return GA.intWeight(e);
    } else {
        return 1;
    }
}
 
template<>
inline double SpannerModule<double>::getWeight(const GraphAttributes& GA, edge e) {
    if (GA.has(GraphAttributes::edgeDoubleWeight)) {
        return GA.doubleWeight(e);
    } else {
        return 1.0;
    }
}
 
}