ext/OGDF/ogdf/upward/FaceSinkGraph.h

   1 /*
   2  * $Revision: 2523 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of class FaceSinkGraph
  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_FACE_SINK_GRAPH_H
  48 #define OGDF_FACE_SINK_GRAPH_H
  49
  50
  51 #include <ogdf/basic/CombinatorialEmbedding.h>
  52 #include <ogdf/basic/NodeArray.h>
  53 #include <ogdf/basic/FaceArray.h>
  54 #include <ogdf/basic/SList.h>
  55
  56
  57 namespace ogdf {
  58
  59
  60 class OGDF_EXPORT FaceSinkGraph : public Graph
  61 {
  62 public:
  63         //! constructor (we assume that the original graph is connected!)
  64         FaceSinkGraph(const ConstCombinatorialEmbedding &E, node s);
  65
  66         //! default constructor (dummy)
  67         FaceSinkGraph() : m_pE(0) { }
  68
  69
  70         void init(const ConstCombinatorialEmbedding &E, node s);
  71
  72
  73         //! return a reference to the original graph G
  74         const Graph &originalGraph() const {
  75                 return *m_pE;
  76         }
  77
  78         //! returns a reference to the embedding E of the original graph G
  79         const ConstCombinatorialEmbedding  &originalEmbedding() const {
  80                 return *m_pE;
  81         }
  82
  83         //! returns the sink-switch in G corresponding to node v in the face-sink
  84         //! graph, 0 if v corresponds to a face
  85         node originalNode(node v) const {
  86                 return m_originalNode[v];
  87         }
  88
  89         //! returns the face in E corresponding to node v in the face-sink
  90         //! graph, 0 if v corresponds to a sink-switch
  91         face originalFace(node v) const {
  92                 return m_originalFace[v];
  93         }
  94
  95         // returns true iff node v in the face-sink graph corresponds to a
  96         // face in E containing the source
  97         bool containsSource(node v) const {
  98                 return m_containsSource[v];
  99         }
 100
 101
 102
 103
 104         //! returns the list of faces f in E such that there exists an upward-planar
 105         //! drawing realizing E with f as external face
 106         //! a node v_T in tree T is returned as representative. v_T is 0 if no possible external face exists.
 107         node possibleExternalFaces(SList<face> &externalFaces) {
 108                 node v_T = checkForest();
 109                 if (v_T != 0)
 110                         gatherExternalFaces(m_T,0,externalFaces);
 111                 return v_T;
 112         }
 113
 114
 115         node faceNodeOf(edge e) {
 116                 return dfsFaceNodeOf(m_T,0,
 117                         m_pE->rightFace(e->adjSource()),m_pE->rightFace(e->adjTarget()));
 118         }
 119
 120
 121         node faceNodeOf(face f) {
 122                 return dfsFaceNodeOf(m_T,0,f,0);
 123         }
 124
 125
 126         //! augments G to an st-planar graph (original implementation)
 127         /** introduces also new nodes into G corresponding to face-nodes in face sink graph)
 128          */
 129         void stAugmentation(
 130                 node h,                       // node corresponding to external face
 131                 Graph &G,                     // original graph (not const)
 132                 SList<node> &augmentedNodes,  // list of augmented nodes
 133                 SList<edge> &augmentedEdges); // list of augmented edges
 134
 135         //! augments G to an st-planar graph
 136         /** (introduces only one new node as super sink into G)
 137          */
 138         void stAugmentation(
 139                 node  h,                      // node corresponding to external face
 140                 Graph &G,                     // original graph (not const)
 141                 node  &superSink,             // super sink
 142                 SList<edge> &augmentedEdges); // list of augmented edges
 143
 144         //! compute the sink switches of all faces.
 145         // the ext. face muss be set
 146         void sinkSwitches(FaceArray< List<adjEntry> > &faceSwitches);
 147
 148
 149
 150 private:
 151         //! constructs face-sink graph
 152         void doInit();
 153
 154         //! performs dfs-traversal and checks for backwards edges
 155         bool dfsCheckForest(
 156                 node v,                   // current node
 157                 node parent,              // its parent in tree
 158                 NodeArray<bool> &visited, // not already visited ?
 159                 // number of internal vertices of G in current tree
 160                 int &nInternalVertices);
 161
 162         //! builds list of possible external faces
 163         /** all faces in tree T containing
 164          * the single source s) by a dfs traversal of T
 165          */
 166         void gatherExternalFaces(
 167                 node v,                      // current node
 168                 node parent,                 // its parent
 169                 SList<face> &externalFaces); // returns list of possible external faces
 170
 171         node dfsFaceNodeOf(node v, node parent,face f1, face f2);
 172
 173         node dfsStAugmentation(
 174                 node v,                       // current node
 175                 node parent,                  // its parent
 176                 Graph &G,                     // original graph (not const)
 177                 SList<node> &augmentedNodes,  // list of augmented nodes
 178                 SList<edge> &augmentedEdges); // list of augmented edges
 179
 180         node dfsStAugmentation(
 181                 node v,                       // current node
 182                 node parent,                  // its parent
 183                 Graph &G,                     // original graph (not const)
 184                 SList<edge> &augmentedEdges); // list of augmented edges
 185
 186
 187         //! associated embedding of graph G
 188         const ConstCombinatorialEmbedding *m_pE;
 189         node m_source; //!< the single source
 190         node m_T;      //!< representative of unique tree T
 191
 192         NodeArray<node> m_originalNode;   //!< original node in G
 193         NodeArray<face> m_originalFace;   //!< original face in E
 194         NodeArray<bool> m_containsSource; //!< contains face node the source ?
 195
 196         /*
 197         //! traverse the face sink tree and compute the sink witches of each internal faces
 198         void dfsFST(node v, //current node
 199                 node parent, //parent of v
 200                 FaceArray< List<adjEntry> > &faceSwitches,
 201                 NodeArray<bool> &visited);
 202                 */
 203
 204         //! checks if the face-sink graph is a forest with
 205         //!  1) there is exactly one tree T containing no internal vertex of G
 206         //!  2) all other trees contain exactly one internal vertex of G
 207         //! a node in tree T is returned as representative
 208         node checkForest();
 209
 210
 211         //! return a adjEntry of node v which right face is f. Be Carefully! The adjEntry is not always unique.
 212         adjEntry getAdjEntry(node v, face f);
 213
 214
 215 }; // class FaceSinkGraph
 216
 217
 218 } // end namespace ogdf
 219
 220
 221 #endif