OnePlanarityBacktracking.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Module.h>
#include <ogdf/basic/Timeouter.h>
#include <ogdf/basic/basic.h>
#include <ogdf/k-planarity/1-planarity_backtracking/EdgePairPartition.h>
#include <ogdf/k-planarity/1-planarity_backtracking/OnePlanarization.h> // IWYU pragma: keep
 
#include <list>
#include <memory>
#include <stack>
#include <vector>
 
namespace ogdf {
class Graph;
} // namespace ogdf
 
namespace ogdf::oneplan_backtracking {
class PartialSolutionFilter;
 
 
class OGDF_EXPORT OnePlanarityBacktracking : public Timeouter {
private:
    class DFSThread {
    public:
        EdgePairPartition m_epp;
 
        OnePlanarityBacktracking* m_solver;
 
        std::stack<bool> m_branchStack;
 
        DFSThread(EdgePairPartition& x, OnePlanarityBacktracking* s) : m_epp(x), m_solver(s) {
            m_branchStack.push(true);
        }
 
        DFSThread(const Graph& G, OneplanMode mode, OnePlanarityBacktracking* s)
            : m_epp(G, mode), m_solver(s) {
            m_branchStack.push(true);
        }
 
        bool nextStep();
 
        bool finished() const { return m_branchStack.empty(); }
 
 
        bool branch();
 
        void cleanUp(DFSThread& thread);
    };
 
    enum class NodeStatus {
        CNT, 
        CUT, 
        SOL 
    };
 
    std::list<DFSThread> m_threads;
 
    int m_maxThreads;
    int m_maxExtractedKuratowskis;
    int m_processedNodes = 0;
 
public:
 
    explicit OnePlanarityBacktracking(int maxThreads = 1000, int maxKuratowskis = 1000);
 
    virtual ~OnePlanarityBacktracking();
 
    OnePlanarityBacktracking(const OnePlanarityBacktracking&) = delete;
 
    OnePlanarityBacktracking& operator=(const OnePlanarityBacktracking&) = delete;
 
 
    Module::ReturnType testOnePlanarity(const Graph& G, OnePlanarization* out = nullptr) {
        return test(OneplanMode::Normal, G, out);
    }
 
 
    Module::ReturnType testICPlanarity(const Graph& G, OnePlanarization* out = nullptr) {
        return test(OneplanMode::IC, G, out);
    }
 
 
    Module::ReturnType testNICPlanarity(const Graph& G, OnePlanarization* out = nullptr) {
        return test(OneplanMode::NIC, G, out);
    }
 
    int processedNodes() const { return m_processedNodes; }
 
protected:
    std::vector<std::unique_ptr<PartialSolutionFilter>> m_filters;
 
private:
    Module::ReturnType test(OneplanMode mode, const Graph& G, OnePlanarization* out = nullptr);
 
    NodeStatus verifyNode(EdgePairPartition* epp);
 
    void push(DFSThread* t, EdgePairPartition* epp);
};
}