MaximalPlanarSubgraphSimple.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/basic/List.h>
#include <ogdf/basic/Math.h>
#include <ogdf/basic/Module.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/comparer.h>
#include <ogdf/basic/extended_graph_alg.h>
#include <ogdf/planarity/PlanarSubgraphEmpty.h>
#include <ogdf/planarity/PlanarSubgraphModule.h>
 
#include <random>
#include <type_traits>
 
namespace ogdf {
 
 
template<typename TCost, class Enable = void>
class MaximalPlanarSubgraphSimple { };
 
 
 
template<typename TCost>
class MaximalPlanarSubgraphSimple<TCost, typename std::enable_if<std::is_integral<TCost>::value>::type>
    : public PlanarSubgraphModule<TCost> {
public:
    MaximalPlanarSubgraphSimple()
        : m_heuristic(*(new PlanarSubgraphEmpty<TCost>)), m_deleteHeuristic(true) { }
 
    explicit MaximalPlanarSubgraphSimple(PlanarSubgraphModule<TCost>& heuristic)
        : m_heuristic(heuristic), m_deleteHeuristic(false) { }
 
    virtual ~MaximalPlanarSubgraphSimple() {
        if (m_deleteHeuristic) {
            delete &m_heuristic;
        }
    }
 
    virtual MaximalPlanarSubgraphSimple* clone() const override {
        auto result = new MaximalPlanarSubgraphSimple(*(m_heuristic.clone()));
        result->m_deleteHeuristic =
                true; // normally a given heuristic is not deleted by the destructor
        return result;
    }
 
protected:
    virtual Module::ReturnType doCall(const Graph& graph, const List<edge>& preferredEdges,
            List<edge>& delEdges, const EdgeArray<TCost>* pCost, bool preferredImplyPlanar) override {
        Module::ReturnType result;
        delEdges.clear();
        List<edge> heuDelEdges;
        if (pCost == nullptr) {
            result = m_heuristic.call(graph, preferredEdges, heuDelEdges, preferredImplyPlanar);
        } else {
            result = m_heuristic.call(graph, *pCost, preferredEdges, heuDelEdges,
                    preferredImplyPlanar);
            heuDelEdges.quicksort(GenericComparer<edge, TCost>(*pCost));
        }
        if (Module::isSolution(result)) {
            GraphCopy copy(graph);
            for (edge e : heuDelEdges) {
                copy.delEdge(copy.copy(e));
            }
            for (edge e : heuDelEdges) {
                edge f = copy.newEdge(e);
 
                if (!isPlanar(copy)) {
                    delEdges.pushBack(e);
                    copy.delEdge(f);
                }
            }
        }
        return result;
    }
 
 
private:
    PlanarSubgraphModule<TCost>& m_heuristic; 
    bool m_deleteHeuristic; 
};
 
template<typename TCost>
class MaximalPlanarSubgraphSimple<TCost, typename std::enable_if<std::is_floating_point<TCost>::value>::type>
    : public PlanarSubgraphModule<TCost> {
public:
    MaximalPlanarSubgraphSimple()
        : m_heuristic(*(new PlanarSubgraphEmpty<TCost>))
        , m_deleteHeuristic(true)
        , m_randomness(0.0)
        , m_randomGenerator()
        , m_runs(1) { }
 
    explicit MaximalPlanarSubgraphSimple(PlanarSubgraphModule<TCost>& heuristic,
            double randomness = 0.0, unsigned int runs = 1)
        : m_heuristic(heuristic)
        , m_deleteHeuristic(false)
        , m_randomness(randomness)
        , m_randomGenerator()
        , m_runs(runs) {
        OGDF_ASSERT(runs > 0);
    }
 
    virtual ~MaximalPlanarSubgraphSimple() {
        if (m_deleteHeuristic) {
            delete &m_heuristic;
        }
    }
 
    virtual MaximalPlanarSubgraphSimple* clone() const override {
        auto result = new MaximalPlanarSubgraphSimple(*(m_heuristic.clone()), m_randomness, m_runs);
        result->m_deleteHeuristic =
                true; // normally a given heuristic is not deleted by the destructor
        return result;
    }
 
    void setSeed(unsigned seed) { m_randomGenerator.seed(seed); }
 
 
protected:
    virtual Module::ReturnType doCall(const Graph& graph, const List<edge>& preferredEdges,
            List<edge>& delEdges, const EdgeArray<TCost>* pCost, bool preferredImplyPlanar) override {
        Module::ReturnType result = Module::ReturnType::Error;
        delEdges.clear();
 
        // scale the costs and do multiple runs (if needed)
        List<edge> delEdgesCurrentBest;
 
        // normalize costs to [0,1] and apply randomness
        EdgeArray<TCost> normalizedCost(graph);
 
        for (auto i = 0u; i < m_runs; i++) {
            List<edge> heuDelEdges;
 
            if (pCost == nullptr) {
                result = m_heuristic.call(graph, preferredEdges, heuDelEdges, preferredImplyPlanar);
            } else {
                std::uniform_real_distribution<TCost> distribution(0.0, 1.0);
                edge firstEdge = graph.firstEdge();
                TCost maxCost = firstEdge == nullptr ? 0 : (*pCost)[firstEdge];
                TCost minCost = firstEdge == nullptr ? 0 : (*pCost)[firstEdge];
                for (edge e : graph.edges) {
                    Math::updateMax(maxCost, (*pCost)[e]);
                    Math::updateMin(minCost, (*pCost)[e]);
                }
                for (edge e : graph.edges) {
                    // do not merge with first FOR !
                    // normalized = pCost transformed to [0,1]
                    TCost normalized = 1;
                    if (maxCost > minCost) {
                        normalized = ((*pCost)[e] - minCost) / (maxCost - minCost);
                    }
                    // now use randomness
                    normalizedCost[e] = (1.0 - m_randomness) * normalized
                            + m_randomness * distribution(m_randomGenerator);
                }
                result = m_heuristic.call(graph, normalizedCost, preferredEdges, heuDelEdges,
                        preferredImplyPlanar);
            }
 
            if (Module::isSolution(result)) {
                GraphCopy copy(graph);
 
                if (pCost != nullptr) {
                    GenericComparer<edge, TCost> cmp(normalizedCost);
                    heuDelEdges.quicksort(cmp);
                }
 
                for (edge e : heuDelEdges) {
                    copy.delEdge(copy.copy(e));
                }
 
                delEdgesCurrentBest.clear();
                for (edge e : heuDelEdges) {
                    edge f = copy.newEdge(e);
 
                    if (!isPlanar(copy)) {
                        delEdgesCurrentBest.pushBack(e);
                        copy.delEdge(f);
                    }
                }
 
                if (pCost == nullptr) {
                    if (i == 0 || delEdgesCurrentBest.size() < delEdges.size()) {
                        // better solution: copy to delEdges
                        delEdges.clear();
                        for (auto e : delEdgesCurrentBest) {
                            delEdges.pushBack(e);
                        };
                    }
                } else {
                    if (i == 0
                            || weightOfList(delEdgesCurrentBest, normalizedCost)
                                    < weightOfList(delEdges, normalizedCost)) {
                        // better solution: copy to delEdges
                        delEdges.clear();
                        for (auto e : delEdgesCurrentBest) {
                            delEdges.pushBack(e);
                        };
                    }
                }
            }
        }
 
        return result;
    }
 
private:
    PlanarSubgraphModule<TCost>& m_heuristic; 
    bool m_deleteHeuristic; 
    double m_randomness; 
    std::default_random_engine m_randomGenerator; 
    unsigned int m_runs; 
 
    TCost weightOfList(const List<edge>& list, const EdgeArray<TCost>& weights) {
        TCost result = 0.0;
        for (auto e : list) {
            result += weights[e];
        }
        return result;
    }
};
 
}