FindKuratowskis.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/planarity/boyer_myrvold/BoyerMyrvoldPlanar.h>
 
namespace ogdf {
 
 
struct ExternE {
    node theNode;
    SListPure<int> startnodes;
    SListPure<node> endnodes;
    SListPure<SListPure<edge>> externalPaths;
};
 
 
struct WInfo {
    node w;
 
    enum class MinorType {
        A = 0x0001, // minor A
        B = 0x0002, // minor B
        C = 0x0004, // minor C
        D = 0x0008, // minor D
        E = 0x0010 // minor E
    };
    int minorType;
 
    ArrayBuffer<adjEntry>* highestXYPath;
    ArrayBuffer<adjEntry>* zPath;
 
    bool pxAboveStopX;
    bool pyAboveStopY;
 
    SListPure<SListPure<edge>> pertinentPaths;
 
    SListIterator<ExternE> externEStart;
    SListIterator<ExternE> externEEnd;
    node firstExternEAfterW;
};
 
inline int operator&(int lhs, WInfo::MinorType rhs) { return lhs & static_cast<int>(rhs); }
 
inline int operator|=(int& lhs, WInfo::MinorType rhs) {
    lhs |= static_cast<int>(rhs);
    return lhs;
}
 
class OGDF_EXPORT KuratowskiStructure {
    friend class FindKuratowskis;
    friend class ExtractKuratowskis;
 
public:
    KuratowskiStructure() { }
 
    ~KuratowskiStructure() { }
 
    KuratowskiStructure(const KuratowskiStructure& orig) { copy(orig); }
 
    KuratowskiStructure& operator=(const KuratowskiStructure& orig) {
        copy(orig);
        return *this;
    }
 
    void clear();
 
    node V;
    int V_DFI;
 
    node R;
 
    node RReal;
    node stopX;
    node stopY;
 
protected:
 
    SListPure<WInfo> wNodes;
 
 
    ArrayBuffer<adjEntry> highestFacePath;
 
    SListPure<ArrayBuffer<adjEntry>> highestXYPaths;
 
    SListPure<adjEntry> externalFacePath;
 
    SListPure<edge> externalSubgraph;
 
    SListPure<edge> pertinentSubgraph;
 
 
    SListPure<ArrayBuffer<adjEntry>> zPaths;
 
    SListPure<ExternE> externE;
 
    SListPure<int> stopXStartnodes;
    SListPure<int> stopYStartnodes;
    SListPure<node> stopXEndnodes;
    SListPure<node> stopYEndnodes;
 
    void copy(const KuratowskiStructure& orig);
    void copyPointer(const KuratowskiStructure& orig, SListPure<WInfo>& list);
};
 
 
class FindKuratowskis {
public:
    explicit FindKuratowskis(BoyerMyrvoldPlanar* bm);
 
    ~FindKuratowskis() { }
 
    void addKuratowskiStructure(const node currentNode, const node root, const node stopx,
            const node stopy);
 
    inline SListPure<KuratowskiStructure>& getAllKuratowskis() { return allKuratowskis; }
 
    inline const SListPure<KuratowskiStructure>& getAllKuratowskis() const {
        return allKuratowskis;
    }
 
    FindKuratowskis& operator=(const FindKuratowskis&) = delete;
 
protected:
    BoyerMyrvoldPlanar* pBM;
 
    Graph& m_g;
 
    const int& m_embeddingGrade;
 
    const bool m_bundles;
 
    NodeArray<WInfo*> m_getWInfo;
 
    SListPure<KuratowskiStructure> allKuratowskis;
 
    KuratowskiStructure k;
 
 
    int m_nodeMarker;
    NodeArray<int> m_wasHere;
 
 
    const NodeArray<node>& m_realVertex;
 
    const NodeArray<int>& m_dfi;
 
    const Array<node>& m_nodeFromDFI;
 
 
    const NodeArray<adjEntry> (&m_link)[2];
 
    const NodeArray<adjEntry>& m_adjParent;
 
 
    const NodeArray<int>& m_leastAncestor;
 
    EdgeArray<BoyerMyrvoldEdgeType>& m_edgeType;
 
    NodeArray<int>& m_lowPoint;
 
    const NodeArray<int>& m_highestSubtreeDFI;
 
 
    const NodeArray<ListPure<node>>& m_separatedDFSChildList;
 
    const EdgeArray<node>& m_pointsToRoot;
 
    NodeArray<int>& m_numUnembeddedBackedgesInBicomp;
 
 
    NodeArray<SListPure<adjEntry>>& m_backedgeFlags;
 
    NodeArray<SListPure<node>>& m_pertinentRoots;
 
    node findRoot(node stopX) const;
 
    void extractHighestFacePath(ArrayBuffer<adjEntry>& highestFacePath, int marker);
 
    void extractExternalFacePath(SListPure<adjEntry>& externalFacePath,
            const ArrayBuffer<adjEntry>& highestFacePath, int marker, int highMarker);
 
    void splitInMinorTypes(const SListPure<adjEntry>& externalFacePath, int marker);
 
    void extractExternalSubgraph(const node stop, int root, SListPure<int>& externalStartnodes,
            SListPure<node>& externalEndnodes);
    void extractExternalSubgraphBundles(const node stop, int root,
            SListPure<edge>& externalSubgraph, int nodeMarker);
 
#if 1
    void extractPertinentSubgraph(SListPure<WInfo>& W_All);
#else
    void extractPertinentSubgraph(SListPure<WInfo>& W_All, const node V);
#endif
 
    void extractPertinentSubgraphBundles(const SListPure<WInfo>& W_All, const node V,
            SListPure<edge>& pertinentSubgraph, int nodeMarker);
};
 
}