SeparatorLiptonTarjanFC.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/graphalg/PlanarSeparatorModule.h>
 
#include <set>
 
namespace ogdf {
 
namespace planar_separators {
 
class OGDF_EXPORT BFSTreeFC : public ArrayBFSTree {
public:
    BFSTreeFC(GraphCopy& G, node rootNode) : ArrayBFSTree(G, rootNode) { construct(); }
 
    void construct();
};
 
class OGDF_EXPORT TriangulatingBFSTree : public ArrayBFSTree {
public:
    TriangulatingBFSTree(GraphCopy& G, node rootNode) : ArrayBFSTree(G, rootNode) { construct(); }
 
    void construct();
 
    void visit(node v, node parent, adjEntry adj, SListPure<node>& bfs);
};
 
}
 
 
class OGDF_EXPORT SeparatorLiptonTarjanFC : public PlanarSeparatorModule {
public:
    SeparatorLiptonTarjanFC(bool useTriBFS = false) : useTriangulatingBFS {useTriBFS} { }
 
    virtual double getMaxSeparatorSize(int n) const override { return -1; }
 
protected:
    virtual bool doSeparate(const Graph& G, List<node>& separator, List<node>& first,
            List<node>& second) override;
 
    bool useTriangulatingBFS;
    std::shared_ptr<ArrayBFSTree> tree;
 
    virtual std::string getSpecificName() const override {
        std::string name = "LTFC";
        if (useTriangulatingBFS) {
            name += "-triBFS";
        }
        return name;
    }
 
    virtual bool findCycle(List<node>& separator, List<node>& first, List<node>& second);
 
    edge chooseEdge() const;
};
 
}