SeparatorDualFC.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/basic.h>
#include <ogdf/graphalg/SeparatorLiptonTarjanFC.h>
 
#include <memory>
#include <string>
 
namespace ogdf::planar_separators {
class ArrayBFSTree;
} // namespace ogdf::planar_separators
 
namespace ogdf {
template<class E>
class List;
 
 
class OGDF_EXPORT SeparatorDualFC : public SeparatorLiptonTarjanFC {
public:
    SeparatorDualFC(bool useTriBFS = false) : useTriangulatingBFS {useTriBFS} { }
 
    virtual double getMaxSeparatorSize(int n) const override { return -1; }
 
protected:
    bool useTriangulatingBFS;
    std::shared_ptr<ArrayBFSTree> tree;
 
    void makeTree();
 
    virtual bool doSeparate(const Graph& G, List<node>& separator, List<node>& first,
            List<node>& second) override;
 
    virtual bool findCycle(List<node>& separator, List<node>& first, List<node>& second) override;
 
    virtual std::string getSpecificName() const override {
        std::string name = "DualFC";
        if (useTriangulatingBFS) {
            name += "-triBFS";
        }
        return name;
    }
};
 
}