EmbedderMinDepthPiTa.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_EMBEDDER_MIN_DEPTH_PITA_H
#define OGDF_EMBEDDER_MIN_DEPTH_PITA_H

#define USE_EXTENDED_DEPTH_DEFINITION

#include <ogdf/module/EmbedderModule.h>
#include <ogdf/decomposition/BCTree.h>

namespace ogdf {

class OGDF_EXPORT EmbedderMinDepthPiTa : public EmbedderModule
{
public:
    //constructor
    EmbedderMinDepthPiTa() { }

    void call(PlanRep& PG, adjEntry& adjExternal);

private:
    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/*, const node& parent_cT*/);

    int depthCutvetex(const node&  cT);

    void deleteDummyNodes(PlanRep& PG, adjEntry& adjExternal);

private:
    BCTree* pBCTree;

    Graph bcTreePG;

    NodeArray<node> nBCTree_to_npBCTree;

    NodeArray<node> npBCTree_to_nBCTree;

    adjEntry* pAdjExternal;

    NodeArray<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;

    List<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;

#ifdef USE_EXTENDED_DEPTH_DEFINITION

    List<node> dummyNodes;
#endif

    NodeArray< List<adjEntry> > newOrder;

    NodeArray<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;
};

} // end namespace ogdf

#endif