PlanarAugmentation.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/SList.h>
#include <ogdf/basic/basic.h>
#include <ogdf/augmentation/AugmentationModule.h>
#include <ogdf/augmentation/planar/PALabel.h>
 
namespace ogdf {
class DynamicBCTree;
 
class OGDF_EXPORT PlanarAugmentation : public AugmentationModule {
public:
    PlanarAugmentation() { }
 
    ~PlanarAugmentation() { }
 
protected:
    virtual void doCall(Graph& G, List<edge>& list) override;
 
 
private:
    int m_nPlanarityTests = 0;
 
    Graph* m_pGraph = nullptr;
 
    DynamicBCTree* m_pBCTree = nullptr;
 
    List<edge>* m_pResult = nullptr;
 
    List<pa_label> m_labels;
 
    List<node> m_pendants;
 
    List<node> m_pendantsToDel;
 
    NodeArray<pa_label> m_belongsTo;
 
    NodeArray<ListIterator<pa_label>> m_isLabel;
 
    NodeArray<SList<adjEntry>> m_adjNonChildren;
 
private:
    void augment();
 
    void makeConnectedByPendants();
 
    void reduceChain(node pendant, pa_label labelOld = nullptr);
 
    PALabel::StopCause followPath(node v, node& last);
 
    bool planarityCheck(node v1, node v2);
 
    node adjToCutvertex(node v, node cutvertex = nullptr);
 
    node findLastBefore(node pendant, node ancestor);
 
    void deletePendant(node pendant, bool removeFromLabel = true);
 
    void addPendant(node pendant, pa_label& label);
 
    edge connectPendants(node pendant1, node pendant2);
 
    void removeAllPendants(pa_label& label);
 
    void joinPendants(pa_label& label);
 
    void connectInsideLabel(pa_label& label);
 
    ListIterator<pa_label> insertLabel(pa_label label);
 
    void deleteLabel(pa_label& label, bool removePendants = true);
 
    void connectLabels(pa_label first, pa_label second);
 
    pa_label newLabel(node cutvertex, node pendant, PALabel::StopCause whyStop);
 
    bool findMatching(pa_label& first, pa_label& second);
 
    bool connectCondition(pa_label a, pa_label b);
 
    void updateAdjNonChildren(node newBlock, SList<node>& path);
 
    void modifyBCRoot(node oldRoot, node newRoot);
 
    void updateNewEdges(const SList<edge>& newEdges);
 
    void terminate();
};
 
}