ext/OGDF/ogdf/planarity/EmbedderMinDepthPiTa.h

   1 /*
   2  * $Revision: 2615 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-16 14:23:36 +0200 (Mo, 16. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief The algorithm computes a planar embedding with minimum
  11  * depth if the embedding for all blocks of the graph is given.
  12  *
  13  * \author Thorsten Kerkhof
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public License
  25  * Version 2 or 3 as published by the Free Software Foundation;
  26  * see the file LICENSE.txt included in the packaging of this file
  27  * for details.
  28  *
  29  * \par
  30  * This program is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33  * GNU General Public License for more details.
  34  *
  35  * \par
  36  * You should have received a copy of the GNU General Public
  37  * License along with this program; if not, write to the Free
  38  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  39  * Boston, MA 02110-1301, USA.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48 #ifndef OGDF_EMBEDDER_MIN_DEPTH_PITA_H
  49 #define OGDF_EMBEDDER_MIN_DEPTH_PITA_H
  50
  51
  52 #include <ogdf/module/EmbedderModule.h>
  53 #include <ogdf/decomposition/BCTree.h>
  54
  55
  56 namespace ogdf {
  57
  58 //! Planar graph embedding with minimum block-nesting depth for given embedded blocks.
  59 /**
  60  * For details see the paper "Minimum Depth Graph Drawing" by M. Pizzonia and R. Tamassia.
  61  */
  62 class OGDF_EXPORT EmbedderMinDepthPiTa : public EmbedderModule
  63 {
  64 public:
  65         //constructor
  66         EmbedderMinDepthPiTa() : m_useExtendedDepthDefinition(true) { }
  67
  68         /**
  69          * \brief Computes an embedding of \a G.
  70          *
  71          * \param G is the original graph.
  72          * \param adjExternal is assigned an adjacency entry on the external face.
  73          */
  74         void call(Graph& G, adjEntry& adjExternal);
  75
  76         bool useExtendedDepthDefinition() const { return m_useExtendedDepthDefinition; }
  77         void useExtendedDepthDefinition(bool b) { m_useExtendedDepthDefinition = b; }
  78
  79 private:
  80         bool m_useExtendedDepthDefinition;
  81
  82         /**
  83          * \brief Computes recursively an embedding for every block by using the
  84          * planarEmbed function.
  85          *
  86          * \param bT is a block node in the BC-tree.
  87          * \param cH is a node of bT in the auxiliary graph.
  88          */
  89         void embedBlocks(const node& bT, const node& cH);
  90
  91         /**
  92          * \brief Computes entry in newOrder for a cutvertex.
  93          *
  94          * \param vT is a cut vertex node in the BC-tree.
  95          * \param root is true if vT is the root node of the block-cutface tree.
  96          */
  97         void embedCutVertex(const node& vT, bool root = false);
  98
  99         /**
 100          * \brief Computes entries in newOrder for nodes in a block.
 101          *
 102          * \param bT is a node in the BC-tree.
 103          * \param parent_cT is a node in the BC-tree.
 104          */
 105         void embedBlockVertex(const node& bT, const node& parent_cT);
 106
 107         /**
 108          * \brief Computes recursively edge lengths for the block-cutface tree. The length
 109          *   of an edge from n to a leaf is 1, from n' to n 2 etc.
 110          *
 111          * \param n is a node in the block-cutface tree.
 112          */
 113         int computeBlockCutfaceTreeEdgeLengths(const node& n);
 114
 115         /**
 116          * \brief Computes recursively the diametral tree.
 117          *
 118          * \param n is a node in the block-cutface tree.
 119          */
 120         void computeTdiam(const node& n);
 121
 122         /**
 123          * \brief Directs all edges to \a n and recursively all edges of its children -
 124          * except the edge to \a n - to the child.
 125          *
 126          * \param G is the tree with the inverted edges.
 127          * \param n is a node in the original tree.
 128          * \param e is an edge in the original tree.
 129          */
 130         void invertPath(Graph& G, const node& n, const edge& e);
 131
 132         /**
 133          * \brief Computes for a block bDG of the dual graph the associated block
 134          *   in the original graph.
 135          *
 136          * \param bDG is a node in the block-cutface tree.
 137          * \param parent is the parent of bDG in the block-cutface tree.
 138          * \param blocksNodes is assigned a list containing all nodes of the original
 139          *   graph of the associated block of bDG.
 140          * \param childBlocks
 141          */
 142         node computeBlockMapping(
 143                 const node& bDG,
 144                 const node& parent,
 145                 List<node>& blocksNodes,
 146                 List<node>& childBlocks);
 147
 148         /**
 149          * \brief Computes the eccentricity of a node nT in the block-cutface tree
 150          *   to all nodes further down in the tree and recursively the eccentricity
 151          *   to all nodes yet further down its children.
 152          *
 153          * \param nT is a node in the block-cutface tree.
 154          */
 155         int eccentricityBottomUp(const node& nT);
 156
 157         /**
 158          * \brief Computes the eccentricity of a node nT in the block-cutface tree
 159          *   and recursively the eccentricity of its children.
 160          *
 161          * \param nT is a node in the block-cutface tree.
 162          */
 163         void eccentricityTopDown(const node& nT);
 164
 165         /**
 166          * \brief Computes the depth of an embedding Gamma(B).
 167          *
 168          * \param bT is a block-node of the BC-tree.
 169          */
 170         int depthBlock(const node&  bT);
 171
 172         /**
 173          * \brief Computes the depth of an embedding Gamma(c).
 174          *
 175          * \param cT is a cutvertex-node of the BC-tree.
 176          */
 177         int depthCutvertex(const node&  cT);
 178
 179         /**
 180          * \brief Deletes inserted dummy nodes. If adjExternal is an adjacency entry
 181          *   of a dummy edge it is reset.
 182          *
 183          * \param G is the graph.
 184          * \param adjExternal is an adjacency entry on the external face.
 185          */
 186         void deleteDummyNodes(Graph& G, adjEntry& adjExternal);
 187
 188 private:
 189         /** the BC-tree of G */
 190         BCTree* pBCTree;
 191
 192         /** the tree of pBCTree rooted at a cutface. */
 193         Graph bcTreePG;
 194
 195         /** a mapping of nodes in bcTreePG to nodes in pBCTree->bcTree() */
 196         NodeArray<node> nBCTree_to_npBCTree;
 197
 198         /** a mapping of nodes in pBCTree->bcTree() to nodes in bcTreePG */
 199         NodeArray<node> npBCTree_to_nBCTree;
 200
 201         /** an adjacency entry on the external face */
 202         adjEntry* pAdjExternal;
 203
 204         /** all blocks */
 205         NodeArray<Graph> blockG;
 206
 207         /** a mapping of nodes in the auxiliaryGraph of the BC-tree to blockG */
 208         NodeArray< NodeArray<node> > nH_to_nBlockEmbedding;
 209
 210         /** a mapping of edges in the auxiliaryGraph of the BC-tree to blockG */
 211         NodeArray< EdgeArray<edge> > eH_to_eBlockEmbedding;
 212
 213         /** a mapping of nodes in blockG to the auxiliaryGraph of the BC-tree */
 214         NodeArray< NodeArray<node> > nBlockEmbedding_to_nH;
 215
 216         /** a mapping of edges in blockG to the auxiliaryGraph of the BC-tree */
 217         NodeArray< EdgeArray<edge> > eBlockEmbedding_to_eH;
 218
 219         /** saving for each node in the block graphs its length */
 220         NodeArray< NodeArray<int> > nodeLength;
 221
 222         /** an array saving the length for each edge in the BC-tree */
 223         EdgeArray<int> m_cB;
 224
 225         /**
 226          * \f$M_B = {cH \in B | m_B(cH) = m_B}\f$ with \f$m_B = \max_{c \in B} m_B(c)\f$
 227          *  and \f$m_B(c) = \max {0} \cup {m_{c, B'} | c \in B', B' \neq B}\f$.
 228          */
 229         NodeArray< List<node> > M_B;
 230
 231         /** Saving edge lengths for the block-cutface tree. */
 232         EdgeArray<int> edgeLength_blockCutfaceTree;
 233
 234         /** The diametrical tree of the block-cutface tree. */
 235         Graph Tdiam;
 236
 237         /** Needed in computeTdiam function to know if first vertex was already inserted */
 238         bool Tdiam_initialized;
 239
 240         /** Mapping nodes from block-cutvertex tree to the diametrical tree */
 241         NodeArray<node> nBlockCutfaceTree_to_nTdiam;
 242
 243         /** Mapping nodes from the diametrical tree to block-cutvertex tree*/
 244         NodeArray<node> nTdiam_to_nBlockCutfaceTree;
 245
 246         /** The knot of the diametrical tree */
 247         node knotTdiam;
 248
 249         /** adjacency entry of the external face of the embedding of G */
 250         adjEntry tmpAdjExtFace;
 251
 252         /**
 253          * a list of all faces in G, a face in this list is containing a list of all
 254          * adjacency entries
 255          */
 256         List< List<adjEntry> > faces;
 257
 258         /** mapping faces in G to nodes in DG */
 259         List<node> fPG_to_nDG;
 260
 261         /** mapping nodes in DG to faces in DG */
 262         NodeArray<int> nDG_to_fPG;
 263
 264         /** the block-cutface tree of G (only the graph, rooted at the external face */
 265         Graph blockCutfaceTree;
 266
 267         /** the block-cutface tree of G (the BC-tree of the dual graph) */
 268         BCTree* pm_blockCutfaceTree;
 269
 270         /** mapping of nodes from the graph blockCutfaceTree to the BC-tree m_blockCutfaceTree */
 271         NodeArray<node> nBlockCutfaceTree_to_nm_blockCutfaceTree;
 272
 273         /** mapping of nodes from the BC-tree m_blockCutfaceTree to the graph blockCutfaceTree */
 274         NodeArray<node> nm_blockCutfaceTree_to_nBlockCutfaceTree;
 275
 276         /** a mapping of blocks of the graph G to its dual graph DG */
 277         NodeArray<node> bPG_to_bDG;
 278
 279         /** a mapping of blocks of the dual graph DG to its original graph G */
 280         NodeArray<node> bDG_to_bPG;
 281
 282         /** saving second highest eccentricity for every node of the block-cutface tree */
 283         NodeArray<int> eccentricity_alt;
 284
 285         /** saving eccentricity for every node of the block-cutface tree */
 286         NodeArray<int> eccentricity;
 287
 288         /**
 289          * list of nodes which are only in one block which exists of extactly this
 290          * node plus a cutvertex
 291          */
 292         List<node> oneEdgeBlockNodes;
 293
 294         /**
 295          * this list is saving the dummy nodes which were inserted to produce a face
 296          * in one-edge-blocks
 297          */
 298         List<node> dummyNodes;
 299
 300         /** saves for every node of G the new adjacency list */
 301         NodeArray< List<adjEntry> > newOrder;
 302
 303         /**
 304          * given a node nT (cutvertex or block), G_nT is the subgraph of G
 305          * associated with the subtree of the BC-tree T rooted at nT
 306          */
 307         NodeArray<Graph> G_nT;
 308
 309         /** a mapping of nodes in G_nT to nodes in G */
 310         NodeArray< NodeArray<node> > nG_nT_to_nPG;
 311
 312         /** a mapping of nodes in G to nodes in G_nT */
 313         NodeArray< NodeArray<node> > nPG_to_nG_nT;
 314
 315         /** a mapping of edges in G_nT to edges in G */
 316         NodeArray< EdgeArray<edge> > eG_nT_to_ePG;
 317
 318         /** a mapping of edges in G to edges in G_nT */
 319         NodeArray< EdgeArray<edge> > ePG_to_eG_nT;
 320
 321         /** adjacency entry of the external face of G_nT[nT] */
 322         NodeArray<adjEntry> Gamma_adjExt_nT;
 323 };
 324
 325 } // end namespace ogdf
 326
 327 #endif