SpannerElkinNeiman.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/GraphList.h>
#include <ogdf/basic/Math.h>
#include <ogdf/basic/Queue.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/simple_graph_alg.h>
#include <ogdf/graphalg/SpannerIteratedWrapper.h>
#include <ogdf/graphalg/SpannerModule.h>
 
#include <cmath>
#include <limits>
#include <string>
 
namespace ogdf {
class GraphCopySimple;
 
template<typename TWeight>
class SpannerElkinNeiman : public SpannerModule<TWeight> {
    const Graph* m_G;
 
    EpsilonTest m_eps;
 
    double m_c; 
    double m_beta; 
    int m_k; 
    int m_intStretch; 
 
    const double DEFAULT_EPSILON = 0.8;
 
public:
    SpannerElkinNeiman() : SpannerModule<TWeight>() { setEpsilon(DEFAULT_EPSILON); }
 
    SpannerElkinNeiman(double epsilon) : SpannerModule<TWeight>() { setEpsilon(epsilon); }
 
    void setEpsilon(double epsilon) {
        OGDF_ASSERT(epsilon > 0);
        m_c = 3.0 / epsilon; // see corollary 8.
    }
 
    virtual bool preconditionsOk(const GraphAttributes& GA, double stretch,
            std::string& error) override {
        if (GA.directed()) {
            error = "The graph must be undirected";
            return false;
        }
        double integralPart;
        if (std::modf(stretch, &integralPart) != 0.0) {
            error = "The stretch is required to be an integer, not " + to_string(stretch);
            return false;
        }
        int intStretch = static_cast<int>(stretch);
        if (intStretch < 1) {
            error = "The stretch must be >= 1.0";
            return false;
        }
        if (intStretch % 2 == 0) {
            error = "The stretch must be odd";
            return false;
        }
        if (GA.has(GraphAttributes::edgeDoubleWeight) || GA.has(GraphAttributes::edgeIntWeight)) {
            error = "The graph must be unweighted";
            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_intStretch = static_cast<int>(stretch);
        m_k = (m_intStretch + 1) / 2;
        m_G = &GA.constGraph();
        m_beta = log(m_c * m_G->numberOfNodes()) / m_k; // log is logarithm naturale
    }
 
    struct BfsNode {
        node n; 
        int depth; 
        edge p; 
 
        BfsNode(node _n, double _depth, edge _p) : n(_n), depth(_depth), p(_p) { }
    };
 
    virtual typename SpannerModule<TWeight>::ReturnType execute() override {
        NodeArray<double> r(*m_G);
        // First, assign each node the random variable. This is done here, so the first
        // feasibility check can be done fast (This is the one that mostly fails).
        for (node u : m_G->nodes) {
            r[u] = randomDoubleExponential(m_beta);
            // Feasibility check 1: See proof of Theorem 1 and "Standard Centralized Model" in 2.1.1
            if (m_eps.geq(r[u], static_cast<double>(m_k))) {
                return SpannerModule<TWeight>::ReturnType::NoFeasibleSolution;
            }
        }
 
        // Paper: u broadcasts a message x within distance k
        // Here: Fix a receiving node x and find all nodes u within distance k, that send messages to x
        for (node x : m_G->nodes) {
            // values[u]: x recieves the value from u (m_u(x))
            NodeArray<double> values(*m_G, std::numeric_limits<double>::lowest());
 
            // firstEdge[u]: The first edge from the path x->u (p_u(x))
            // This is the last edge from the path u->x as described in the paper
            NodeArray<edge> firstEdge(*m_G, nullptr);
 
            QueuePure<BfsNode> queue;
            NodeArray<bool> marked(*m_G, false); // Just visit a node once.
 
            queue.emplace(x, 0, nullptr); // p==nullptr: we do not have a first edge
            marked[x] = true; // Do not revisit x
            while (!queue.empty()) {
                BfsNode bfsNode = queue.pop();
                int distance = bfsNode.depth + 1;
 
                for (adjEntry adj : bfsNode.n->adjEntries) {
                    node u = adj->twinNode();
                    if (marked[u]) {
                        continue;
                    }
 
                    edge p = bfsNode.p;
                    if (p == nullptr) {
                        p = adj->theEdge(); // Set the first edge: Only happens in the first expansion step of the bfs
                    }
 
                    values[u] = r[u] - distance;
                    firstEdge[u] = p;
 
                    if (distance < m_k) { // distance is <= m_k when a dfs node is popped from the stack.
                        queue.emplace(u, distance, p);
                        marked[u] = true;
                    }
                }
            }
 
            assertTimeLeft();
 
            // find edges that must be added to the spanner:
            // m(x) = max{m_u(x) | u in V}
            double maxValue = std::numeric_limits<double>::lowest();
            for (node u : m_G->nodes) {
                Math::updateMax(maxValue, values[u]);
            }
            maxValue -= 1.0; // m(x)-1
 
            assertTimeLeft();
 
            // Add the edges (sets C(x) in the paper) to the spanner.
            for (node u : m_G->nodes) {
                if (values[u] != std::numeric_limits<double>::lowest()
                        && m_eps.geq(values[u], maxValue)) {
                    edge e = firstEdge[u];
                    if (!(*m_inSpanner)[e]) {
                        m_spanner->newEdge(e);
                        (*m_inSpanner)[e] = true;
                    }
                }
            }
 
            assertTimeLeft();
        }
 
        // Feasibility check 2: See proof of Theorem 1 and "Standard Centralized Model" in 2.1.1
        // Note: The paper states, that the spanner must have >= n-1 edges. This does not work, for
        // all graphs, e.g. a forest as an input. The paper never states, that the graph must be connected
        // nor that it can be disconnected. Using n-<amount components> does work and solves the issue above.
        int components = connectedComponents(*m_G);
        if (m_spanner->numberOfEdges() < m_G->numberOfNodes() - components) {
            return SpannerModule<TWeight>::ReturnType::NoFeasibleSolution;
        }
 
        return SpannerModule<TWeight>::ReturnType::Feasible;
    }
 
    using SpannerModule<TWeight>::assertTimeLeft;
    using SpannerModule<TWeight>::m_GA;
    using SpannerModule<TWeight>::m_stretch;
    using SpannerModule<TWeight>::m_spanner;
    using SpannerModule<TWeight>::m_inSpanner;
};
 
template<typename TWeight>
class SpannerElkinNeimanIterated : public SpannerIteratedWrapper<TWeight> {
public:
    SpannerElkinNeimanIterated()
        : SpannerIteratedWrapper<TWeight>(new SpannerElkinNeiman<TWeight>(), 200) {};
};
 
}