EmbedderMinDepthPiTa.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/ArrayBuffer.h>
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/List.h>
#include <ogdf/basic/Observer.h>
#include <ogdf/basic/basic.h>
#include <ogdf/basic/extended_graph_alg.h>
#include <ogdf/planarity/embedder/EmbedderBCTreeBase.h>
 
namespace ogdf {
class BCTree;
 
 
class OGDF_EXPORT EmbedderMinDepthPiTa : public embedder::EmbedderBCTreeBase<false> {
public:
    //constructor
    EmbedderMinDepthPiTa() : m_useExtendedDepthDefinition(true), pm_blockCutfaceTree(nullptr) { }
 
    /* needs to be deleted explicitly for MSVC<=16 and classes containing a NodeArrayP */
    OGDF_NO_COPY(EmbedderMinDepthPiTa)
 
    
    virtual void doCall(Graph& G, adjEntry& adjExternal) override;
 
    bool useExtendedDepthDefinition() const { return m_useExtendedDepthDefinition; }
 
    void useExtendedDepthDefinition(bool b) { m_useExtendedDepthDefinition = b; }
 
protected:
    adjEntry trivialInit(Graph& G) override {
        planarEmbed(G);
        CombinatorialEmbedding CE(G);
        adjEntry result = CE.chooseFace()->firstAdj();
        deleteDummyNodes(G, result);
 
        return result;
    }
 
private:
    bool m_useExtendedDepthDefinition;
 
    void embedBlocks(const node& bT, const node& cH);
 
    void embedCutVertex(const node& vT, bool root = false);
 
    void embedBlockVertex(const node& bT, const node& parent_cT);
 
    int computeBlockCutfaceTreeEdgeLengths(const node& n);
 
    void computeTdiam(const node& n);
 
    void invertPath(Graph& G, const node& n, const edge& e);
 
    node computeBlockMapping(const node& bDG, const node& parent, List<node>& blocksNodes,
            List<node>& childBlocks);
 
    int eccentricityBottomUp(const node& nT);
 
    void eccentricityTopDown(const node& nT);
 
    int depthBlock(const node& bT);
 
    int depthCutvertex(const node& cT);
 
    void deleteDummyNodes(Graph& G, adjEntry& adjExternal);
 
private:
    Graph bcTreePG;
 
    NodeArray<node> nBCTree_to_npBCTree;
 
    NodeArray<node> npBCTree_to_nBCTree;
 
    NodeArrayP<Graph> blockG;
 
    NodeArray<NodeArray<node>> nH_to_nBlockEmbedding;
 
    NodeArray<EdgeArray<edge>> eH_to_eBlockEmbedding;
 
    NodeArray<NodeArray<node>> nBlockEmbedding_to_nH;
 
    NodeArray<EdgeArray<edge>> eBlockEmbedding_to_eH;
 
    NodeArray<NodeArray<int>> nodeLength;
 
    EdgeArray<int> m_cB;
 
    NodeArray<List<node>> M_B;
 
    EdgeArray<int> edgeLength_blockCutfaceTree;
 
    Graph Tdiam;
 
    bool Tdiam_initialized;
 
    NodeArray<node> nBlockCutfaceTree_to_nTdiam;
 
    NodeArray<node> nTdiam_to_nBlockCutfaceTree;
 
    node knotTdiam;
 
    adjEntry tmpAdjExtFace;
 
    List<List<adjEntry>> faces;
 
    ArrayBuffer<node> fPG_to_nDG;
 
    NodeArray<int> nDG_to_fPG;
 
    Graph blockCutfaceTree;
 
    BCTree* pm_blockCutfaceTree;
 
    NodeArray<node> nBlockCutfaceTree_to_nm_blockCutfaceTree;
 
    NodeArray<node> nm_blockCutfaceTree_to_nBlockCutfaceTree;
 
    NodeArray<node> bPG_to_bDG;
 
    NodeArray<node> bDG_to_bPG;
 
    NodeArray<int> eccentricity_alt;
 
    NodeArray<int> eccentricity;
 
    List<node> oneEdgeBlockNodes;
 
    List<node> dummyNodes;
 
    NodeArray<List<adjEntry>> newOrder;
 
    NodeArrayP<Graph> G_nT;
 
    NodeArray<NodeArray<node>> nG_nT_to_nPG;
 
    NodeArray<NodeArray<node>> nPG_to_nG_nT;
 
    NodeArray<EdgeArray<edge>> eG_nT_to_ePG;
 
    NodeArray<EdgeArray<edge>> ePG_to_eG_nT;
 
    NodeArray<adjEntry> Gamma_adjExt_nT;
};
 
}