SpannerIteratedWrapper.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/graphalg/SpannerModule.h>
 
#include <algorithm>
#include <cstdint>
#include <limits>
#include <memory>
#include <string>
 
namespace ogdf {
class GraphAttributes;
 
template<typename TWeight>
class SpannerIteratedWrapper : public SpannerModule<TWeight> {
public:
    SpannerIteratedWrapper(SpannerModule<TWeight>* module, int maxIterations)
        : m_module(module), m_maxIterations(maxIterations) { }
 
    virtual bool preconditionsOk(const GraphAttributes& GA, double stretch,
            std::string& error) override {
        return m_module->preconditionsOk(GA, stretch, error);
    }
 
    int getExecutedIterations() { return m_iterations; }
 
private:
    std::unique_ptr<SpannerModule<TWeight>> m_module;
    const int m_maxIterations;
    int m_iterations;
 
    virtual typename SpannerModule<TWeight>::ReturnType execute() override {
        const Graph& G = m_GA->constGraph();
        if (isTimelimitEnabled()) {
            int64_t timeLeft = max(getTimeLeft(), static_cast<int64_t>(0));
            m_module->setTimelimit(timeLeft);
        }
 
        int bestSize = std::numeric_limits<int>::max();
 
        for (m_iterations = 1; m_iterations <= m_maxIterations; m_iterations++) {
            // No assertTimeLeft here: If there is an timeout, check, if we had a previous solution
            if (isTimelimitEnabled() && getTimeLeft() <= 0) {
                if (bestSize == std::numeric_limits<int>::max()) {
                    return SpannerModule<TWeight>::ReturnType::TimeoutInfeasible;
                } else {
                    return SpannerModule<TWeight>::ReturnType::Feasible;
                }
            }
 
            GraphCopySimple spanner(G);
            EdgeArray<bool> inSpanner(G);
 
            typename SpannerModule<TWeight>::ReturnType r =
                    m_module->call(*m_GA, m_stretch, spanner, inSpanner);
            if (r == SpannerModule<TWeight>::ReturnType::NoFeasibleSolution) {
                continue;
            }
            if (r == SpannerModule<TWeight>::ReturnType::TimeoutInfeasible) {
                // do we found at least one solution?
                if (bestSize == std::numeric_limits<int>::max()) {
                    return SpannerModule<TWeight>::ReturnType::TimeoutInfeasible;
                } else {
                    return SpannerModule<TWeight>::ReturnType::Feasible;
                }
            }
            if (r != SpannerModule<TWeight>::ReturnType::Feasible) {
                return r; // return errors directly
            }
 
            if (spanner.numberOfEdges() < bestSize) {
                // found a new best solution
                bestSize = spanner.numberOfEdges();
 
                // Copy solution to the members
                m_spanner->clear();
                m_spanner->setOriginalGraph(G);
                for (node n : G.nodes) {
                    m_spanner->newNode(n);
                }
                m_inSpanner->init(G, false);
 
                for (edge e : spanner.edges) {
                    edge eOrig = spanner.original(e);
                    (*m_inSpanner)[eOrig] = true;
                    m_spanner->newEdge(eOrig);
                }
            }
        }
        m_iterations--; // remove the overflow iteration, which is not executed
 
        if (bestSize == std::numeric_limits<int>::max()) {
            return SpannerModule<TWeight>::ReturnType::NoFeasibleSolution;
        } else {
            return SpannerModule<TWeight>::ReturnType::Feasible;
        }
    }
 
    using SpannerModule<TWeight>::getTimeLeft;
    using SpannerModule<TWeight>::isTimelimitEnabled;
    using SpannerModule<TWeight>::m_GA;
    using SpannerModule<TWeight>::m_stretch;
    using SpannerModule<TWeight>::m_spanner;
    using SpannerModule<TWeight>::m_inSpanner;
};
 
}