PlanarSubgraphBoyerMyrvold.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/basic.h>
#include <ogdf/planarity/BoothLueker.h>
#include <ogdf/planarity/PlanarSubgraphModule.h>
 
#include <cstdlib>
#include <random>
 
namespace ogdf {
template<class E>
class List;
 
 
class OGDF_EXPORT PlanarSubgraphBoyerMyrvold : public PlanarSubgraphModule<int> {
private:
    int m_runs;
    double m_randomness;
    BoothLueker m_planModule;
    std::minstd_rand m_rand;
 
public:
    explicit PlanarSubgraphBoyerMyrvold(int runs = 1, double randomness = 0)
        : m_runs(runs), m_randomness(randomness), m_rand(rand()) {};
 
    ~PlanarSubgraphBoyerMyrvold() {};
 
    virtual PlanarSubgraphBoyerMyrvold* clone() const override {
        return new PlanarSubgraphBoyerMyrvold(m_runs);
    };
 
    void seed(std::minstd_rand rand) { m_rand = rand; }
 
protected:
    virtual ReturnType doCall(const Graph& graph, const List<edge>& preferedEdges,
            List<edge>& delEdges, const EdgeArray<int>* pCost, bool preferedImplyPlanar) override;
 
    bool isRemoved(const GraphCopy& copy, const edge e) {
        return copy.copy(e) == nullptr || copy.copy(e)->source() != copy.copy(e->source())
                || copy.copy(e)->target() != copy.copy(e->target());
    }
};
 
}