ext/OGDF/ogdf/planarity/PlanRepInc.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 PlanRepInc.
  11  *
  12  * The PlanRepInc is especially suited for incremental drawing
  13  * modes. It derives from GraphObserver and therefore is always
  14  * informed about changes of the underlying graph. Keeps the
  15  * m_nodesInCC and m_numCC fields up-to-date.
  16  *
  17  * \author Karsten Klein
  18  *
  19  * \par License:
  20  * This file is part of the Open Graph Drawing Framework (OGDF).
  21  *
  22  * \par
  23  * Copyright (C)<br>
  24  * See README.txt in the root directory of the OGDF installation for details.
  25  *
  26  * \par
  27  * This program is free software; you can redistribute it and/or
  28  * modify it under the terms of the GNU General Public License
  29  * Version 2 or 3 as published by the Free Software Foundation;
  30  * see the file LICENSE.txt included in the packaging of this file
  31  * for details.
  32  *
  33  * \par
  34  * This program is distributed in the hope that it will be useful,
  35  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  36  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  37  * GNU General Public License for more details.
  38  *
  39  * \par
  40  * You should have received a copy of the GNU General Public
  41  * License along with this program; if not, write to the Free
  42  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  43  * Boston, MA 02110-1301, USA.
  44  *
  45  * \see  http://www.gnu.org/copyleft/gpl.html
  46  ***************************************************************/
  47
  48
  49 #ifdef _MSC_VER
  50 #pragma once
  51 #endif
  52
  53
  54 #ifndef OGDF_PLAN_REP_INC_H
  55 #define OGDF_PLAN_REP_INC_H
  56
  57
  58
  59 #include <ogdf/planarity/PlanRep.h>
  60 #include <ogdf/planarity/PlanRepUML.h>
  61 #include <ogdf/basic/UMLGraph.h>
  62 #include <ogdf/basic/GraphAttributes.h>
  63 #include <ogdf/basic/GraphObserver.h>
  64 #include <ogdf/basic/Array2D.h>
  65
  66
  67 namespace ogdf {
  68
  69
  70 //===============================================
  71 //main function(s):
  72 //
  73 //              this class is only an adaption of PlanRep
  74 //      for the special incremental drawing case
  75 //      As incremental layout only makes sense with
  76 //      a given layout, this PlanRepInc copes with
  77 //      layout information and embedding
  78 //===============================================
  79
  80 class OGDF_EXPORT PlanRepInc : public PlanRepUML, public GraphObserver
  81 {
  82 public:
  83         //construction
  84         //constructor for interactive updates (parts added step by step)
  85         PlanRepInc(const UMLGraph& UG);
  86         //constructor for incremental updates (whole graph already given)
  87         //part to stay fixed has fixed value set to true
  88         PlanRepInc(const UMLGraph& UG, const NodeArray<bool> &fixed);
  89
  90         //init a CC only with active elements
  91         void initActiveCC(int i);
  92         //but with at least one active node, makes a node active if necessary
  93         //and returns it. returns 0 otherwise
  94         node initMinActiveCC(int i);
  95
  96         //in the case that the underlying incremental structure
  97         //changes, we update this copy
  98         virtual void nodeDeleted(node v);
  99         virtual void nodeAdded(node v);
 100         virtual void edgeDeleted(edge e);
 101         virtual void edgeAdded(edge e);
 102         virtual void reInit();
 103         virtual void cleared();//Graph cleared
 104
 105         //sets activity status to true and updates the structures
 106         //node activation activates all adjacent edges
 107         void activateNode(node v);
 108         //TODO: auch deaktivieren
 109         //void activateNode(node v, bool b);
 110         void activateEdge(edge e);
 111
 112         //handles copies of original CCs that are split into
 113         //unconnected parts of active nodes by connecting them
 114         //tree-like adding necessary edges at "external" nodes
 115         //of the partial CCs. Note that this only makes sense
 116         //when the CC parts are already correctly embedded
 117         bool makeTreeConnected(adjEntry adjExternal);
 118         //delete an edge again
 119         void deleteTreeConnection(int i, int j);
 120         void deleteTreeConnection(int i, int j, CombinatorialEmbedding &E);
 121         //sets a list of adjentries on "external" faces of
 122         //unconnected active parts of the current CC
 123         void getExtAdjs(List<adjEntry> &extAdjs);
 124         adjEntry getExtAdj(GraphCopy &GC, CombinatorialEmbedding &E);
 125
 126         //component number
 127         int& componentNumber(node v) {return m_component[v];}
 128
 129         bool& treeEdge(edge e) {return m_treeEdge[e];}
 130         //only valid if m_eTreeArray initialized, should be replaced later
 131         edge treeEdge(int i, int j) const
 132         {
 133                 if (m_treeInit) {
 134                         return m_eTreeArray(i, j);
 135                 }
 136                 return 0;
 137         }
 138         bool treeInit() {return m_treeInit;}
 139
 140         //
 141         // extension of methods defined by GraphCopy/PlanRep
 142         //
 143
 144         // splits edge e, can be removed when edge status in edgetype
 145         // m_treedge can be removed afterwards
 146         virtual edge split(edge e) {
 147
 148                 edge eNew = PlanRepUML::split(e);
 149                 if (m_treeEdge[e]) m_treeEdge[eNew] = true;
 150
 151                 return eNew;
 152
 153         }//split
 154
 155         //debug output
 156 #ifdef OGDF_DEBUG
 157         void writeGML(const char *fileName)
 158         {
 159                 const GraphAttributes &AG = getUMLGraph();
 160                 ofstream os(fileName);
 161                 PlanRepInc::writeGML(os, AG);//getUMLGraph());//l);
 162         }
 163         void writeGML(const char *fileName, const Layout &drawing)
 164         {
 165                 ofstream os(fileName);
 166                 writeGML(os, drawing);
 167         }
 168
 169         void writeGML(ostream &os, const GraphAttributes &AG);
 170         void writeGML(ostream &os, const Layout &drawing, bool colorEmbed = true);
 171         void writeGML(const char *fileName, GraphAttributes &AG, bool colorEmbed = true);
 172
 173         //outputs a drawing if genus != 0
 174         int genusLayout(Layout &drawing) const;
 175 #endif
 176
 177 protected:
 178         void initMembers(const UMLGraph &UG);
 179         //initialize CC with active nodes (minNode ? at least one node)
 180         node initActiveCCGen(int i, bool minNode);
 181
 182 private:
 183         NodeArray<bool> m_activeNodes; //stores the status of the nodes
 184         EdgeArray<bool> m_treeEdge; //edge inserted for connnectivity
 185         NodeArray<int> m_component; //number of partial component in current CC
 186                                                                 //used for treeConnection
 187         Array2D<edge> m_eTreeArray;    //used for treeConnection
 188         bool m_treeInit;           //check if the tree edge Array2D was initialized
 189 };//PlanrepInc
 190
 191
 192 }//namespace ogdf
 193
 194 #endif