SeparatorDual.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/basic.h>
#include <ogdf/graphalg/SeparatorLiptonTarjan.h>
 
#include <cmath>
#include <string>
 
namespace ogdf {
template<class E>
class List;
 
 
class OGDF_EXPORT SeparatorDual : public SeparatorLiptonTarjan {
public:
    SeparatorDual(bool useTriangulatingBFS = false, unsigned int treeHeightIt = 0)
        : useTriBFS {useTriangulatingBFS}, treeHeightIterations(treeHeightIt + 1) { }
 
    virtual std::string getSpecificName() const override {
        std::string name = "Dual";
        if (useTriBFS) {
            name += "-triBFS";
        }
        if (treeHeightIterations > 1) {
            name += "-THM-" + std::to_string(treeHeightIterations - 1);
        }
 
        return name;
    }
 
    virtual double getMaxSeparatorSize(int n) const override { return 4 * sqrt(n); }
 
protected:
    virtual void makeTree() override;
 
    virtual bool doSeparate(const Graph& G, List<node>& separator, List<node>& first,
            List<node>& second) override;
 
    bool useTriBFS; // whether to use triangulating BFS for the second phase or not
    unsigned int treeHeightIterations; // how many iterations of tree height maximisation to run
};
 
}