SeparatorLiptonTarjan.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/basic.h>
#include <ogdf/graphalg/PlanarSeparatorModule.h>
 
#include <cmath>
#include <memory>
#include <string>
 
namespace ogdf {
template<class E>
class List;
 
 
class OGDF_EXPORT SeparatorLiptonTarjan : public PlanarSeparatorModule {
    friend class Cycle;
 
public:
    SeparatorLiptonTarjan(bool useTriangulatingBFS = false, unsigned int treeHeightIt = 0)
        : useTriBFS {useTriangulatingBFS}, treeHeightIterations(treeHeightIt + 1) { }
 
    virtual double getMaxSeparatorSize(int n) const override { return sqrt(8) * sqrt(n); }
 
 
protected:
    bool useTriBFS;
    unsigned int treeHeightIterations;
 
    virtual bool doSeparate(const Graph& G, List<node>& separator, List<node>& first,
            List<node>& second) override;
 
    std::shared_ptr<BFSTreeClassical> tree;
 
    virtual std::string getSpecificName() const override {
        std::string name = "LT";
        if (useTriBFS) {
            name += "-triBFS";
        }
        if (treeHeightIterations > 1) {
            name += "-THM-" + std::to_string(treeHeightIterations - 1);
        }
 
        return name;
    }
 
    virtual void makeTree();
 
    void fillLists(List<node>& separator, List<node>& first, List<node>& second) const;
 
    edge chooseEdge() const;
};
 
 
}