OnePlanarization.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/GraphCopy.h>
#include <ogdf/basic/GraphSets.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/extended_graph_alg.h>
 
namespace ogdf::oneplan_backtracking {
class EdgePairPartition;
 
 
class OGDF_EXPORT OnePlanarization : public GraphCopy {
private:
    const EdgePairPartition* m_epp = nullptr;
    NodeSet m_saturatedVertices; // vertices that are incident to an uncrossable edge
    NodeSet m_crossingVertices;
    EdgeSet m_kiteEdges; // uncrossable
    EdgeSet m_crossingEdges; // edges incident to crossing vertices (uncrossable)
    EdgeSet m_freeEdges; // edges that still have at least one other edge they are allowed to cross
    EdgeSet m_remainingEdges; // uncrossable edges that are not kite edges or crossing edges
 
public:
    OnePlanarization() = default;
 
    explicit OnePlanarization(const EdgePairPartition* ep) { init(ep); }
 
    void init(const EdgePairPartition* ep);
 
    const EdgePairPartition* getEdgePairPartition() const { return m_epp; }
 
    bool isPlanar() const { return ogdf::isPlanar(*this); }
 
    const NodeSet& crossingVertices() const { return m_crossingVertices; }
 
 
    const EdgeSet& kiteEdges() const { return m_kiteEdges; }
 
 
    const EdgeSet& crossingEdges() const { return m_crossingEdges; }
 
    const EdgeSet& freeEdges() const { return m_freeEdges; }
 
    const EdgeSet& remainingEdges() const { return m_remainingEdges; }
 
    void getSaturatedSubgraph(GraphCopy& cp) const {
        cp.init(*reinterpret_cast<const Graph*>(this));
        for (edge e : m_freeEdges) {
            cp.delEdge(cp.copy(e));
        }
    }
 
private:
    using GraphCopy::init;
};
}