SpannerBermanDisconnected.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphAttributes.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/simple_graph_alg.h>
#include <ogdf/graphalg/SpannerBerman.h>
#include <ogdf/graphalg/SpannerModule.h>
 
#include <algorithm>
#include <cstdint>
#include <string>
 
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;
        }
 
        Graph::CCsInfo ccsInfo(G);
        SpannerBerman<TWeight> spannerBerman;
 
        for (int c = 0; c < ccsInfo.numberOfCCs(); c++) {
            assertTimeLeft();
 
            GraphCopySimple GC;
            GC.setOriginalGraph(G);
            NodeArray<node> nodeMap(G, nullptr);
            EdgeArray<edge> edgeMap(G, nullptr);
            GC.insert(ccsInfo, c, nodeMap, edgeMap);
 
            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;
};
 
}