ext/OGDF/ogdf/cluster/ClusterPlanRep.h

   1 /*
   2  * $Revision: 2564 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 00:03:48 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of ClusterPlanRep class, allowing cluster
  11  * boundary insertion and shortest path edge insertion
  12  *
  13  * \author Karsten Klein
  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_CLUSTER_PLAN_REP_H
  49 #define OGDF_CLUSTER_PLAN_REP_H
  50
  51
  52
  53 #include <ogdf/planarity/PlanRepUML.h>
  54 #include <ogdf/cluster/ClusterGraphAttributes.h>
  55 #include <ogdf/cluster/ClusterGraph.h>
  56 #include <ogdf/cluster/ClusterArray.h>
  57
  58 #include <ogdf/basic/HashArray.h>
  59
  60
  61 namespace ogdf {
  62
  63
  64 class OGDF_EXPORT ClusterPlanRep : public PlanRep
  65 {
  66
  67 public:
  68
  69         ClusterPlanRep(
  70                 const ClusterGraphAttributes &acGraph,
  71                 const ClusterGraph &clusterGraph);
  72
  73         virtual ~ClusterPlanRep() { }
  74
  75         void initCC(int i);
  76
  77         //edge on the cluster boundary, adjSource
  78         void setClusterBoundary(edge e) {
  79                 setEdgeTypeOf(e, edgeTypeOf(e) | clusterPattern());
  80         }
  81         bool isClusterBoundary(edge e) {
  82                 return ((edgeTypeOf(e) & clusterPattern()) == clusterPattern());
  83         }
  84         const ClusterGraph &getClusterGraph() const {
  85                 return *m_pClusterGraph;
  86         }
  87
  88         /** re-inserts edge eOrig by "crossing" the edges in crossedEdges;
  89          *   splits each edge in crossedEdges
  90          * Precond.: eOrig is an edge in the original graph,
  91          *           the edges in crossedEdges are in this graph,
  92          *           cluster boundaries are modelled as edge paths
  93          * \param eOrig: Original edge to be inserted
  94          * \param crossedEdges: Edges that are crossed by this insertion
  95          * \param E: The embedding in which the edge is inserted
  96          */
  97         void insertEdgePathEmbedded(
  98                 edge eOrig,
  99                 CombinatorialEmbedding &E,
 100                 const SList<adjEntry> &crossedEdges);
 101
 102         void ModelBoundaries();
 103
 104         //rootadj is set by ModelBoundaries
 105         adjEntry externalAdj() { return m_rootAdj; }
 106
 107
 108         //*************************************************************************
 109         //structural alterations
 110
 111         // Expands nodes with degree > 4 and merge nodes for generalizations
 112         virtual void expand(bool lowDegreeExpand = false);
 113
 114         virtual void expandLowDegreeVertices(OrthoRep &OR);
 115
 116         //splits edge e, updates clustercage lists if necessary and returns new edge
 117         virtual edge split(edge e)
 118         {
 119                 edge eNew = PlanRep::split(e);
 120
 121                 //update edge to cluster info
 122                 m_edgeClusterID[eNew] = m_edgeClusterID[e];
 123                 m_nodeClusterID[eNew->source()] = m_edgeClusterID[e];
 124
 125                 return eNew;
 126         }//split
 127
 128
 129         //returns cluster of edge e
 130         //edges only have unique numbers if clusters are already modelled
 131         //we derive the edge cluster from the endnode cluster information
 132         cluster clusterOfEdge(edge e)
 133         {
 134
 135                 OGDF_ASSERT(m_clusterOfIndex.isDefined(ClusterID(e->source())))
 136                 OGDF_ASSERT(m_clusterOfIndex.isDefined(ClusterID(e->target())))
 137
 138                 OGDF_ASSERT(
 139                         (ClusterID(e->source()) == ClusterID(e->target())) ||
 140                         (clusterOfIndex(ClusterID(e->source())) ==
 141                         clusterOfIndex(ClusterID(e->target()))->parent()) ||
 142                         (clusterOfIndex(ClusterID(e->target())) ==
 143                         clusterOfIndex(ClusterID(e->source()))->parent()) ||
 144                         (clusterOfIndex(ClusterID(e->target()))->parent() ==
 145                         clusterOfIndex(ClusterID(e->source()))->parent())
 146                 )
 147
 148                 if (ClusterID(e->source()) == ClusterID(e->target()))
 149                         return clusterOfIndex(ClusterID(e->target()));
 150                 if (clusterOfIndex(ClusterID(e->source())) ==
 151                         clusterOfIndex(ClusterID(e->target()))->parent())
 152                         return clusterOfIndex(ClusterID(e->source()));
 153                 if (clusterOfIndex(ClusterID(e->target())) ==
 154                         clusterOfIndex(ClusterID(e->source()))->parent())
 155                         return clusterOfIndex(ClusterID(e->target()));
 156                 if (clusterOfIndex(ClusterID(e->target()))->parent() ==
 157                         clusterOfIndex(ClusterID(e->source()))->parent())
 158                         return clusterOfIndex(ClusterID(e->source()))->parent();
 159
 160                 OGDF_THROW(AlgorithmFailureException);
 161                 //return 0;
 162         }//clusterOfEdge
 163
 164         inline int ClusterID(node v) const {return m_nodeClusterID[v];}
 165         inline int ClusterID(edge e) const {return m_edgeClusterID[e];}
 166         cluster clusterOfIndex(int i) {return m_clusterOfIndex[i];}
 167
 168         inline cluster clusterOfDummy(node v)
 169                 {
 170                         OGDF_ASSERT(!original(v))
 171                         OGDF_ASSERT(ClusterID(v) != -1)
 172                         return clusterOfIndex(ClusterID(v));
 173                 }
 174
 175         //output functions
 176         void writeGML(const char *fileName, const Layout &drawing);
 177         void writeGML(const char *fileName);
 178         void writeGML(ostream &os, const Layout &drawing);
 179
 180
 181 protected:
 182
 183         //insert boundaries for all given clusters
 184         void convertClusterGraph(cluster act,
 185                                                          AdjEntryArray<edge>& currentEdge,
 186                                                          AdjEntryArray<int>& outEdge);
 187
 188         //insert edges to represent the cluster boundary
 189         void insertBoundary(cluster C,
 190                                                 AdjEntryArray<edge>& currentEdge,
 191                                                 AdjEntryArray<int>& outEdge,
 192                                                 bool clusterIsLeaf);
 193
 194         //reinsert edges to planarize the graph after convertClusterGraph
 195         void reinsertEdge(edge e);
 196
 197 private:
 198
 199         const ClusterGraph *m_pClusterGraph;
 200
 201         edgeType clusterPattern() { return etcSecCluster << etoSecondary; }
 202
 203         adjEntry m_rootAdj; //connects cluster on highest level with non cluster or
 204                                                 //same level
 205
 206
 207         //******************
 208         EdgeArray<int> m_edgeClusterID;
 209         NodeArray<int> m_nodeClusterID;
 210         //we maintain an array of index to cluster mappings (CG is const)
 211         //cluster numbers don't need to be consecutive
 212         HashArray<int, cluster> m_clusterOfIndex;
 213 };
 214
 215
 216 }//namespace
 217
 218 #endif