SpannerBasicGreedy.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/NodeSet.h>
#include <ogdf/graphalg/SpannerModule.h>
 
namespace ogdf {
 
template<typename TWeight>
class SpannerBasicGreedy : public SpannerModule<TWeight> {
    EdgeArray<TWeight> m_spannerWeights;
    EpsilonTest m_eps;
 
public:
    virtual bool preconditionsOk(const GraphAttributes& GA, double stretch,
            std::string& error) override {
        if (GA.directed()) {
            error = "The graph must be undirected";
            return false;
        }
        if (stretch < 1.0) {
            error = "The stretch must be >= 1.0";
            return false;
        }
        return true;
    }
 
private:
    virtual void init(const GraphAttributes& GA, double stretch, GraphCopySimple& spanner,
            EdgeArray<bool>& inSpanner) override {
        SpannerModule<TWeight>::init(GA, stretch, spanner, inSpanner);
        m_spannerWeights.init(spanner);
    }
 
    virtual typename SpannerModule<TWeight>::ReturnType execute() override {
        Array<edge> edges(m_GA->constGraph().numberOfEdges());
        int i = 0;
        for (edge e : m_GA->constGraph().edges) {
            edges[i++] = e;
        }
        edges.quicksort(EdgeWeightComparator(*m_GA));
 
        assertTimeLeft();
 
        for (edge e : edges) {
            node u = m_spanner->copy(e->source());
            node v = m_spanner->copy(e->target());
            double maxDistance = m_stretch * weight(e);
            double currentSpannerDistance = distanceInSpanner(u, v, maxDistance);
            if (m_eps.greater(currentSpannerDistance, maxDistance)) {
                edge newEdge = m_spanner->newEdge(e);
                m_spannerWeights[newEdge] = weight(e);
                (*m_inSpanner)[e] = true;
            }
            assertTimeLeft();
        }
 
        return SpannerModule<TWeight>::ReturnType::Feasible;
    }
 
    OGDF_EXPORT double distanceInSpanner(node s, node t, double maxLookupDist);
 
    inline TWeight weight(edge e) { return getWeight(*m_GA, e); }
 
    struct EdgeWeightComparator {
        EdgeWeightComparator(const GraphAttributes& GA) : m_GA(GA) {};
        EdgeWeightComparator() = delete;
        EdgeWeightComparator(const EdgeWeightComparator&) = delete;
        EdgeWeightComparator& operator=(const EdgeWeightComparator&) = delete;
 
        bool less(edge a, edge b) const {
            return m_eps.less(getWeight(m_GA, a), getWeight(m_GA, b));
        }
 
    private:
        const GraphAttributes& m_GA;
        const EpsilonTest m_eps;
    };
 
    using SpannerModule<TWeight>::getWeight;
    using SpannerModule<TWeight>::assertTimeLeft;
    using SpannerModule<TWeight>::m_GA;
    using SpannerModule<TWeight>::m_stretch;
    using SpannerModule<TWeight>::m_spanner;
    using SpannerModule<TWeight>::m_inSpanner;
};
 
}