PlanarSubgraphPQTree.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/basic.h>
#include <ogdf/planarity/booth_lueker/PlanarLeafKey.h>
#include <ogdf/planarity/planar_subgraph_fast/MaxSequencePQTree.h>
#include <ogdf/planarity/planar_subgraph_fast/whaInfo.h>
 
namespace ogdf {
template<class E>
class SList;
template<class E>
class SListPure;
template<class T, class X, class Y>
class PQLeafKey;
 
class OGDF_EXPORT PlanarSubgraphPQTree : public MaxSequencePQTree<edge, bool> {
public:
    using PlanarLeafKey = booth_lueker::PlanarLeafKey<whaInfo*>;
 
    PlanarSubgraphPQTree() : MaxSequencePQTree<edge, bool>() { }
 
    virtual ~PlanarSubgraphPQTree() { }
 
    virtual int Initialize(SListPure<PlanarLeafKey*>& leafKeys);
 
    int Initialize(SListPure<PQLeafKey<edge, whaInfo*, bool>*>& leafKeys) override {
        return MaxSequencePQTree<edge, bool>::Initialize(leafKeys);
    }
 
    void ReplaceRoot(SListPure<PlanarLeafKey*>& leafKeys);
 
    virtual bool Reduction(SListPure<PlanarLeafKey*>& leafKeys,
            SList<PQLeafKey<edge, whaInfo*, bool>*>& eliminatedKeys);
 
    bool Reduction(SListPure<PQLeafKey<edge, whaInfo*, bool>*>& leafKeys) override {
        return MaxSequencePQTree<edge, bool>::Reduction(leafKeys);
    }
 
private:
    void ReplaceFullRoot(SListPure<PlanarLeafKey*>& leafKeys);
 
    void ReplacePartialRoot(SListPure<PlanarLeafKey*>& leafKeys);
 
    void removeEliminatedLeaves(SList<PQLeafKey<edge, whaInfo*, bool>*>& eliminatedKeys);
};
 
}