SpannerKortsarzPeleg.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/GraphCopy.h>
#include <ogdf/basic/GraphList.h>
#include <ogdf/basic/GraphSets.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/simple_graph_alg.h>
#include <ogdf/graphalg/MaximumDensitySubgraph.h>
#include <ogdf/graphalg/SpannerModule.h>
 
#include <algorithm>
#include <cstdint>
#include <string>
 
namespace ogdf {
 
template<typename TWeight>
class SpannerKortsarzPeleg : public SpannerModule<TWeight> {
    GraphCopySimple m_G;
    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 != 2.0) {
            error = "The stretch must be 2.0";
            return false;
        }
        if (!isSimple(GA.constGraph())) {
            error = "The graph is not simple";
            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_G.clear();
        m_G.init(GA.constGraph());
    }
 
    virtual typename SpannerModule<TWeight>::ReturnType execute() override {
        while (true) {
            node maxNode = nullptr;
            double maxDensity = 0.0;
            NodeSet<true> maxDenseSubset(m_GA->constGraph());
            List<edge> maxE_U; // holds the edges of the maximum dense subgraph
 
            for (node v : m_G.nodes) {
                // Create neighbor graph
                GraphCopySimple neighborGraph;
                // Note: v is not part of the neighbor graph.
                neighborGraph.setOriginalGraph(m_G);
                for (adjEntry adj : v->adjEntries) {
                    neighborGraph.newNode(adj->twinNode());
                }
                for (edge e : m_G.edges) {
                    if (neighborGraph.copy(e->target()) != nullptr
                            && neighborGraph.copy(e->source()) != nullptr) {
                        neighborGraph.newEdge(e);
                    }
                }
 
                // Calculate dense subgraph and find all edges E_U of this subgraph
                NodeSet<true> denseSubset(m_G);
                int64_t timelimit = -1;
                if (isTimelimitEnabled()) {
                    timelimit = max(static_cast<int64_t>(0), getTimeLeft());
                }
                bool success = maximumDensitySubgraph(
                        neighborGraph, denseSubset,
                        [&](node n) {
                            OGDF_ASSERT(neighborGraph.original(n) != nullptr);
                            return neighborGraph.original(n);
                        },
                        timelimit);
                if (!success) {
                    throw typename SpannerModule<TWeight>::TimeoutException();
                }
 
                List<edge> E_U;
                for (edge e : m_G.edges) {
                    if (denseSubset.isMember(e->source()) && denseSubset.isMember(e->target())) {
                        E_U.pushBack(e);
                    }
                }
 
                // Did we found a new maximum dense subgraph?
                double density = denseSubset.size() == 0
                        ? 0.0
                        : static_cast<double>(E_U.size()) / denseSubset.size();
                if (m_eps.greater(density, maxDensity)) {
                    maxDensity = density;
                    maxNode = v;
                    maxDenseSubset = denseSubset;
                    maxE_U = E_U;
                }
            }
 
            if (m_eps.less(maxDensity, 1.0)) {
                break;
            }
 
            OGDF_ASSERT(maxNode != nullptr);
 
            // add edges to spanner
            for (node u : maxDenseSubset.nodes()) {
                edge e = m_G.searchEdge(maxNode, u); // e is part of m_G
                addToSpanner(e);
 
                // remove from m_G
                m_G.delEdge(e);
            }
 
            // Remove R(H^u, maxDenseSubset) from m_G
            // Improvement: H^c (see paper) is actually not needed. Since
            // R(H^u, maxDenseSubset) is the intersection of E_U and the current spanner
            // edges, but E_U only consists of current spanner edges (Note that the loop
            // above only contains edges not in E_U since maxNode is not part of the
            // neighbor graph), the intersection is not needed. One can directly delete
            // all edges in E_U.
            for (edge e : maxE_U) {
                m_G.delEdge(e);
            }
        }
 
        // Add uncovered edges to spanner
        for (edge e : m_G.edges) {
            addToSpanner(e);
        }
 
        return SpannerModule<TWeight>::ReturnType::Feasible;
    }
 
    inline void addToSpanner(edge e) {
        m_spanner->newEdge(m_G.original(e));
        (*m_inSpanner)[m_G.original(e)] = true;
    }
 
    using SpannerModule<TWeight>::assertTimeLeft;
    using SpannerModule<TWeight>::isTimelimitEnabled;
    using SpannerModule<TWeight>::getTimeLeft;
    using SpannerModule<TWeight>::m_GA;
    using SpannerModule<TWeight>::m_spanner;
    using SpannerModule<TWeight>::m_inSpanner;
};
 
}