PartialSolutionFilter.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>
#include <ogdf/k-planarity/1-planarity_backtracking/OnePlanarization.h>
 
namespace ogdf::oneplan_backtracking {
 
 
class OGDF_EXPORT PartialSolutionFilter {
public:
    virtual bool canCut(OnePlanarization& pl) = 0;
 
    virtual ~PartialSolutionFilter() = default;
};
 
class OGDF_EXPORT FreeEdgesDensityFilter : public PartialSolutionFilter {
public:
    bool canCut(OnePlanarization& pl) override {
        ogdf::NodeSet seenVertices(pl);
        for (ogdf::edge e : pl.freeEdges()) {
            seenVertices.insert(e->target());
            seenVertices.insert(e->source());
        }
 
        return pl.freeEdges().size() > 4 * seenVertices.size() - 8;
    }
};
 
class OGDF_EXPORT PlanarizationDensityFilter : public PartialSolutionFilter {
public:
    bool canCut(OnePlanarization& pl) override {
        return pl.numberOfEdges() > 4 * pl.numberOfNodes() - 8;
    }
};
 
class OGDF_EXPORT SaturatedSubgraphPlanarityFilter : public PartialSolutionFilter {
    bool canCut(OnePlanarization& pl) override {
        ogdf::GraphCopy saturatedSubgraph;
        pl.getSaturatedSubgraph(saturatedSubgraph);
        return !isPlanar(saturatedSubgraph);
    }
};
 
 
class OGDF_EXPORT SeparatingCycleFilter : public PartialSolutionFilter {
public:
    bool canCut(OnePlanarization& pl) override;
 
private:
    bool test(OnePlanarization& pl, ogdf::node crossingVertex, ogdf::NodePair cyclePair,
            ogdf::NodePair otherPair);
 
    static int minFreeEdgeCycle(const OnePlanarization& pl, node crossingVertex,
            NodePair& cyclePair, NodePair& otherPair, EdgeSet& cycleEdges, NodeSet& cycleNodes);
 
    static void contractUncrossableEdges(const OnePlanarization& pl, GraphCopy& cp,
            const EdgeSet& cycleEdges, const NodeSet& cycleNodes, node& v1, node& v2);
};
}