Open
Graph Drawing
Framework

 v.2012.05
 

EmbedderMinDepth.h
Go to the documentation of this file.
00001 /*
00002  * $Revision: 2299 $
00003  * 
00004  * last checkin:
00005  *   $Author: gutwenger $ 
00006  *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
00007  ***************************************************************/
00008  
00044 #ifdef _MSC_VER
00045 #pragma once
00046 #endif
00047 
00048 #ifndef OGDF_EMBEDDER_MIN_DEPTH_H
00049 #define OGDF_EMBEDDER_MIN_DEPTH_H
00050 
00051 #include <ogdf/module/EmbedderModule.h>
00052 #include <ogdf/decomposition/BCTree.h>
00053 #include <ogdf/decomposition/StaticSPQRTree.h>
00054 
00055 namespace ogdf {
00056 
00058 class OGDF_EXPORT EmbedderMinDepth : public EmbedderModule
00059 {
00060 public:
00061     //constructor
00062     EmbedderMinDepth() { }
00063 
00070     void call(PlanRep& PG, adjEntry& adjExternal);
00071 
00072 private:
00079     void computeBlockGraphs(const node& bT, const node& cH);
00080 
00091     int bottomUpTraversal(const node& bT, const node& cH);
00092 
00104     void topDownTraversal(const node& bT);
00105 
00112   void embedBlock(const node& bT);
00113 
00124   void embedBlock(const node& bT, const node& cT, ListIterator<adjEntry>& after);
00125 
00126 private:
00128     BCTree* pBCTree;
00129 
00131     adjEntry* pAdjExternal;
00132 
00134     NodeArray<Graph> blockG;
00135 
00137     NodeArray< NodeArray<node> > nH_to_nBlockEmbedding;
00138 
00140     NodeArray< EdgeArray<edge> > eH_to_eBlockEmbedding;
00141 
00143     NodeArray< NodeArray<node> > nBlockEmbedding_to_nH;
00144 
00146     NodeArray< EdgeArray<edge> > eBlockEmbedding_to_eH;
00147     
00149     NodeArray< NodeArray<int> > nodeLength;
00150 
00152     NodeArray<int> minDepth;
00153 
00155     EdgeArray<int> m_cB;
00156 
00159     NodeArray< List<node> > M_B;
00160 
00164     NodeArray< List<node> > M2;
00165 
00167     NodeArray< List<adjEntry> > newOrder;
00168 
00171     NodeArray<bool> treeNodeTreated;
00172 
00174     NodeArray<StaticSPQRTree*> spqrTrees;
00175 };
00176 
00177 } // end namespace ogdf
00178 
00179 #endif