SpannerBermanDisconnected.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/simple_graph_alg.h>
#include <ogdf/graphalg/SpannerBerman.h>
#include <ogdf/graphalg/SpannerModule.h>
 
namespace ogdf {
 
template<typename TWeight>
class SpannerBermanDisconnected : public SpannerModule<TWeight> {
public:
    virtual bool preconditionsOk(const GraphAttributes& GA, double stretch,
            std::string& error) override {
        if (!isSimple(GA.constGraph())) {
            error = "The graph is not simple";
            return false;
        }
        if (stretch < 1.0) {
            error = "The stretch must be >= 1.0";
            return false;
        }
        return true;
    }
 
private:
    virtual typename SpannerModule<TWeight>::ReturnType execute() override {
        const Graph& G = m_GA->constGraph();
 
        if (G.numberOfNodes() == 0) {
            return SpannerModule<TWeight>::ReturnType::Feasible;
        }
 
        NodeArray<int> components(G);
        int amountComponenets = connectedComponents(G, components);
 
        SpannerBerman<TWeight> spannerBerman;
 
        for (int c = 0; c < amountComponenets; c++) {
            assertTimeLeft();
 
            List<node> nodes;
            for (node n : G.nodes) {
                if (components[n] == c) {
                    nodes.pushBack(n);
                }
            }
 
            GraphCopySimple GC;
            GC.createEmpty(G);
            inducedSubGraph(G, nodes.begin(), GC);
 
            GraphCopySimple spanner(GC);
            EdgeArray<bool> inSpanner;
            GraphAttributes GCA(GC, 0);
            GCA.directed() = m_GA->directed();
            if (m_GA->has(GraphAttributes::edgeIntWeight)) {
                GCA.addAttributes(GraphAttributes::edgeIntWeight);
                for (edge e : GC.edges) {
                    GCA.intWeight(e) = m_GA->intWeight(GC.original(e));
                }
            }
            if (m_GA->has(GraphAttributes::edgeDoubleWeight)) {
                GCA.addAttributes(GraphAttributes::edgeDoubleWeight);
                for (edge e : GC.edges) {
                    GCA.doubleWeight(e) = m_GA->doubleWeight(GC.original(e));
                }
            }
 
            if (isTimelimitEnabled()) {
                int64_t timeLeft = max(getTimeLeft(), static_cast<int64_t>(0));
                spannerBerman.setTimelimit(timeLeft);
            }
            typename SpannerModule<TWeight>::ReturnType r =
                    spannerBerman.call(GCA, m_stretch, spanner, inSpanner);
            if (r != SpannerModule<TWeight>::ReturnType::Feasible) {
                return r;
            }
 
            // copy used edges to m_spanner and m_inSpanner
            for (edge e : spanner.edges) {
                edge eOrig = GC.original(spanner.original(e));
                (*m_inSpanner)[eOrig] = true;
                m_spanner->newEdge(eOrig);
            }
        }
 
        return SpannerModule<TWeight>::ReturnType::Feasible;
    }
 
    using SpannerModule<TWeight>::getWeight;
    using SpannerModule<TWeight>::assertTimeLeft;
    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;
};
 
}