ext/OGDF/ogdf/planarity/MMVariableEmbeddingInserter.h

   1 /*
   2  * $Revision: 2583 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-12 01:02:21 +0200 (Do, 12. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief declaration of class MMVariableEmbeddingInserter
  11  *
  12  * \author Carsten Gutwenger
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43 #ifdef _MSC_VER
  44 #pragma once
  45 #endif
  46
  47 #ifndef OGDF_MM_VARIABLE_EMBEDDING_INSERTER_H
  48 #define OGDF_MM_VARIABLE_EMBEDDING_INSERTER_H
  49
  50
  51
  52 #include <ogdf/module/MMEdgeInsertionModule.h>
  53 #include <ogdf/basic/CombinatorialEmbedding.h>
  54 #include <ogdf/basic/FaceArray.h>
  55 #include <ogdf/basic/tuples.h>
  56
  57
  58
  59 namespace ogdf {
  60
  61 class OGDF_EXPORT NodeSet;
  62 class OGDF_EXPORT StaticPlanarSPQRTree;
  63
  64
  65 //! Minor-monotone edge insertion with variable embedding.
  66 class OGDF_EXPORT MMVariableEmbeddingInserter : public MMEdgeInsertionModule
  67 {
  68 public:
  69         //! Creates a minor-monotone fixed embedding inserter.
  70         MMVariableEmbeddingInserter();
  71
  72         // destruction
  73         virtual ~MMVariableEmbeddingInserter() { }
  74
  75
  76         //! Sets the remove-reinsert option for postprocessing.
  77         void removeReinsert(RemoveReinsertType rrOption) {
  78                 m_rrOption = rrOption;
  79         }
  80
  81         //! Returns the current setting of the remove-reinsert option.
  82         RemoveReinsertType removeReinsert() const {
  83                 return m_rrOption;
  84         }
  85
  86
  87         //! Sets the portion of most crossed edges used during postprocessing.
  88         /**
  89          * The value is only used if the remove-reinsert option is set to rrMostCrossed.
  90          * The number of edges used in postprocessing is then
  91          * number of edges * percentMostCrossed() / 100.
  92          */
  93         void percentMostCrossed(double percent) {
  94                 m_percentMostCrossed = percent;
  95         }
  96
  97         //! Returns the current setting of the option percentMostCrossed.
  98         double percentMostCrossed() const {
  99                 return m_percentMostCrossed;
 100         }
 101
 102
 103 private:
 104         class Block;
 105         class ExpandedSkeleton;
 106
 107         typedef PlanRepExpansion::Crossing Crossing;
 108
 109         struct AnchorNodeInfo {
 110                 AnchorNodeInfo() { m_adj_1 = m_adj_2 = 0; }
 111                 AnchorNodeInfo(adjEntry adj) {
 112                         m_adj_1 = adj;
 113                         m_adj_2 = 0;
 114                 }
 115                 AnchorNodeInfo(adjEntry adj_1, adjEntry adj_2) {
 116                         m_adj_1 = adj_1;
 117                         m_adj_2 = adj_2;
 118                 }
 119
 120                 adjEntry m_adj_1;
 121                 adjEntry m_adj_2;
 122         };
 123
 124         enum PathType { pathToEdge = 0, pathToSource = 1, pathToTarget = 2 };
 125
 126         struct Paths {
 127                 Paths() :
 128                         m_addPartLeft(3), m_addPartRight(3),
 129                         m_paths(3),
 130                         m_src(0,2,0), m_tgt(0,2,0),
 131                         m_pred(0,2,0)
 132                 { }
 133
 134                 Array<SList<adjEntry> > m_addPartLeft;
 135                 Array<SList<adjEntry> > m_addPartRight;
 136                 Array<List<Crossing> >  m_paths;
 137                 Array<AnchorNodeInfo>   m_src;
 138                 Array<AnchorNodeInfo>   m_tgt;
 139                 Array<int>              m_pred;
 140         };
 141
 142         /**
 143          * \brief Implementation of algorithm call.
 144          *
 145          * @param PG is the input planarized expansion and will also receive the result.
 146          * @param origEdges is the list of original edges (edges in the original graph
 147          *        of \a PG) that have to be inserted.
 148          * @param forbiddenEdgeOrig points to an edge array indicating if an original edge is
 149          *        forbidden to be crossed.
 150          */
 151         ReturnType doCall(
 152                 PlanRepExpansion &PG,
 153                 const List<edge> &origEdges,
 154                 const EdgeArray<bool> *forbiddenEdgeOrig);
 155
 156         /**
 157          * \brief Collects all anchor nodes (including dummies) of a node.
 158          *
 159          * @param v is the current node when traversing all copy nodes of an original node
 160          *        that are connected in a tree-wise manner.
 161          * @param nodes is assigned the set of anchor nodes.
 162          * @param nsParent is the parent node split.
 163          */
 164         void collectAnchorNodes(
 165                 node v,
 166                 NodeSet &nodes,
 167                 const PlanRepExpansion::NodeSplit *nsParent) const;
 168
 169         /**
 170          * \brief Finds the set of anchor nodes of \a src and \a tgt.
 171          *
 172          * @param src is a node in \a PG representing an original node.
 173          * @param tgt is a node in \a PG representing an original node.
 174          * @param sources ia assigned the set of anchor nodes of \a src's original node.
 175          * @param targets ia assigned the set of anchor nodes of \a tgt's original node.
 176          */
 177         void findSourcesAndTargets(
 178                 node src, node tgt,
 179                 NodeSet &sources,
 180                 NodeSet &targets) const;
 181
 182         /**
 183          * \brief Returns all anchor nodes of \a vOrig in n\a nodes.
 184          *
 185          * @param vOrig is a node in the original graph.
 186          * @param nodes ia assigned the set of anchor nodes.
 187          */
 188         void anchorNodes(
 189                 node vOrig,
 190                 NodeSet &nodes) const;
 191
 192         static node commonDummy(
 193                 NodeSet &sources,
 194                 NodeSet &targets);
 195
 196         /**
 197          * \brief Computes insertion path \a eip.
 198          *
 199          * The possible start and end nodes of the insertion path have to be stored in
 200          * \a m_pSources and \a m_pTargets.
 201          * @param eip    is assigned the insertion path (the crossed edges).
 202          * @param vStart is assigned the start point of the insertion path.
 203          * @param vEnd   is assigned the end point of the insertion path.
 204          */
 205         void insert(List<Crossing> &eip, AnchorNodeInfo &vStart, AnchorNodeInfo &vEnd);
 206
 207         node prepareAnchorNode(
 208                 const AnchorNodeInfo &anchor,
 209                 node vOrig,
 210                 bool isSrc,
 211                 edge &eExtra);
 212
 213         void preprocessInsertionPath(
 214                 const AnchorNodeInfo &srcInfo,
 215                 const AnchorNodeInfo &tgtInfo,
 216                 node srcOrig,
 217                 node tgtOrig,
 218                 node &src,
 219                 node &tgt,
 220                 edge &eSrc,
 221                 edge &eTgt);
 222
 223         node preparePath(
 224                 node vAnchor,
 225                 adjEntry adjPath,
 226                 bool bOrigEdge,
 227                 node vOrig);
 228
 229         void findPseudos(
 230                 node vDummy,
 231                 adjEntry adjSrc,
 232                 AnchorNodeInfo &infoSrc,
 233                 SListPure<node> &pseudos);
 234
 235         void insertWithCommonDummy(
 236                 edge eOrig,
 237                 node vDummy,
 238                 node &src,
 239                 node &tgt);
 240
 241         /**
 242          * \brief Implements vertex case of recursive path search in BC-tree.
 243          *
 244          * @param v      is the node in the graph currently visited during BC-tree traversal.
 245          * @param parent is the parent block in DFS-traversal.
 246          * @param eip is (step-by-step) assigned the insertion path (crossed edges).
 247          * @param vStart is assigned the start point of \a eip.
 248          * @param vEnd   is assigned the end point of \a eip.
 249          */
 250         bool dfsVertex(node v,
 251                 int parent,
 252                 List<Crossing> &eip,
 253                 AnchorNodeInfo &vStart,
 254                 AnchorNodeInfo &vEnd);
 255
 256         /**
 257          * \brief Implements block case of recursive path search in BC-tree.
 258          *
 259          * @param i is the block in the graph currently visited during BC-tree traversal.
 260          * @param parent is the parent node in DFS-traversal.
 261          * @param repS is assigned the representative (nodein the graph) of a source node.
 262          * @param eip is (step-by-step) assigned the insertion path (crossed edges).
 263          * @param vStart is assigned the start point of \a eip.
 264          * @param vEnd   is assigned the end point of \a eip.
 265          */
 266         bool dfsBlock(int i,
 267                 node parent,
 268                 node &repS,
 269                 List<Crossing> &eip,
 270                 AnchorNodeInfo &vStart,
 271                 AnchorNodeInfo &vEnd);
 272
 273         bool pathSearch(node v, edge parent, const Block &BC, List<edge> &path);
 274
 275         /**
 276          * \brief Computes optimal insertion path in block \a BC.
 277          *
 278          * @param BC      is the block.
 279          * @param L       is assigned the insertion path (the crossed edges).
 280          * @param srcInfo is assigned the start point of the insertion path.
 281          * @param tgtInfo is assigned the end point of the insertion path.
 282          */
 283         void blockInsert(
 284                 Block &BC,
 285                 List<Crossing> &L,
 286                 AnchorNodeInfo &srcInfo,
 287                 AnchorNodeInfo &tgtInfo);
 288
 289         void buildSubpath(
 290                 node v,
 291                 edge eIn,
 292                 edge eOut,
 293                 Paths &paths,
 294                 bool &bPathToEdge,
 295                 bool &bPathToSrc,
 296                 bool &bPathToTgt,
 297                 ExpandedSkeleton &Exp);
 298
 299         void contractSplitIfReq(node u);
 300         void convertDummy(
 301                 node u,
 302                 node vOrig,
 303                 PlanRepExpansion::nodeSplit ns_0);
 304
 305         void writeEip(const List<Crossing> &eip);
 306
 307         RemoveReinsertType m_rrOption; //!< The remove-reinsert option.
 308         double m_percentMostCrossed;   //!< The percentMostCrossed option.
 309
 310         PlanRepExpansion *m_pPG; //!< Pointer to the planarized expansion.
 311
 312         NodeSet *m_pSources; //!< The set of possible start nodes of an insertion path.
 313         NodeSet *m_pTargets; //!< The set of possible end nodes of an insertion path.
 314
 315         NodeArray<SList<int> > m_compV; //!< The list of blocks containing a node \a v.
 316         Array<SList<node> >    m_nodeB; //!< The list of nodes in block \a i.
 317         Array<SList<edge> >    m_edgeB; //!< The list of edges in block \a i.
 318         NodeArray<node>        m_GtoBC; //!< Maps a node in the planarized expansion to the corresponding node in block.
 319
 320         bool m_conFinished; //!< Stores if a possible target node in a block has already been found.
 321         const EdgeArray<bool> *m_forbiddenEdgeOrig;
 322 };
 323
 324 } // end namespace ogdf
 325
 326 #endif