ext/OGDF/ogdf/internal/cluster/CPlanarSubClusteredST.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 CPlanarSubClusteredST class.
  11  *
  12  * \author Karsten Klein
  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_CPLANAR_SUBCLUSTERED_ST_H
  48 #define OGDF_CPLANAR_SUBCLUSTERED_ST_H
  49
  50
  51 #include <ogdf/cluster/ClusterGraph.h>
  52 #include <ogdf/cluster/ClusterArray.h>
  53 #include <ogdf/basic/EdgeArray.h>
  54
  55 namespace ogdf {
  56
  57 //! Constructs a c-planar subclustered spanning tree of the input by setting edgearray values
  58 class CPlanarSubClusteredST
  59 {
  60
  61 public:
  62
  63         CPlanarSubClusteredST() { }
  64
  65         //! sets values in inST according to membership in c-planar STGraph
  66         virtual void call(const ClusterGraph& CG, EdgeArray<bool>& inST);
  67         //! sets values in inST according to membership in c-planar STGraph,
  68         //! computes minimum spanning tree according to weight in \a weight
  69         virtual void call(const ClusterGraph& CG,
  70                 EdgeArray<bool>& inST,
  71                 EdgeArray<double>& weight);
  72
  73 private:
  74
  75         //! builds spanning tree on original graph out of repgraphs STs
  76         void dfsBuildOriginalST(/*ClusterGraph& CG,*/
  77         node v,
  78         ClusterArray< EdgeArray<bool> > &treeEdges,    //edges in repgraph
  79         EdgeArray<bool>& inST,                         //original edges
  80         NodeArray<bool> &visited);
  81         //builds spanning tree on graph of node v in treeEdges
  82         void dfsBuildSpanningTree(node v,
  83                                                           EdgeArray<bool> &treeEdges,
  84                                                           NodeArray<bool> &visited);
  85
  86         //! constructs for every cluster a graph representing its
  87         //! main structure (children & their connections)
  88         //! only insert nodes here
  89         void constructRepresentationGraphNodes(const ClusterGraph& CG,
  90                                                                                    Graph& g,
  91                                                                                cluster c
  92                                                                                    )
  93         {
  94
  95                 //insert nodes for all child clusters
  96                 ListConstIterator<cluster> it;
  97                 for (it = c->cBegin(); it.valid(); it++)
  98                 {
  99                         node v = g.newNode();
 100                         m_cRepNode[*it] = v;
 101                 }//for
 102                 //insert nodes for all node entries in c
 103                 ListConstIterator<node> itn;
 104                 for (itn = c->nBegin(); itn.valid(); itn++)
 105                 {
 106                         node v = g.newNode();
 107                         m_vRepNode[*itn] = v;
 108                 }//for
 109         }//constructRepresentationGraphNodes
 110
 111         //! insert rep edges for all edges in clustergraph
 112         void constructRepresentationGraphEdges(const ClusterGraph& CG,
 113                                                                                    ClusterArray<Graph*>& RepGraph)
 114         {
 115                 edge e;
 116                 forall_edges(e, CG.getGraph())
 117                 {
 118                         //insert representation in RepGraph[allocation cluster]
 119                         //defined by lowest common ancestor of end points
 120                         node u = e->source();
 121                         node v = e->target();
 122                         cluster uAncestor, vAncestor;
 123                         cluster allocCluster =
 124                                 CG.commonClusterLastAncestors(u,v, uAncestor, vAncestor);
 125                         m_allocCluster[e] = allocCluster;
 126                         //now derive the real ancestors (maybe the nodes themselves from
 127                         //the supplied clusters
 128
 129                         //Case1: both nodes in same cluster => connect the nodes in the
 130                         //cluster representation graph
 131                         if (uAncestor == vAncestor)
 132                         {
 133                                 m_repEdge[e] = RepGraph[uAncestor]->newEdge(
 134                                                                 m_vRepNode[u], m_vRepNode[v]);
 135                         }//if
 136                         else
 137                         {
 138                                 OGDF_ASSERT(!((uAncestor == CG.rootCluster())&&
 139                                         (vAncestor == CG.rootCluster())))
 140                                 //now only one node can be directly in rootcluster
 141                                 //this case now seems to fall together with else else...
 142                                 if (uAncestor == CG.rootCluster())
 143                                 {
 144                                         m_repEdge[e] = RepGraph[uAncestor]->newEdge(
 145                                                                 m_vRepNode[u], m_cRepNode[vAncestor]);
 146                                 }//if u in rootcluster
 147                                 else if (vAncestor == CG.rootCluster())
 148                                 {
 149                                         m_repEdge[e] = RepGraph[vAncestor]->newEdge(
 150                                                                 m_cRepNode[uAncestor], m_vRepNode[v]);
 151                                 }//if v in rootcluster
 152                                 else
 153                                 {
 154                                         OGDF_ASSERT(allocCluster != 0)
 155                                         //now create edge in lowest common cluster
 156                                         node v1, v2;
 157                                         v1 = ( (uAncestor == 0) ? m_vRepNode[u] :
 158                                                                 m_cRepNode[uAncestor]);
 159                                         v2 = ( (vAncestor == 0) ? m_vRepNode[v] :
 160                                                                 m_cRepNode[vAncestor]);
 161                                         m_repEdge[e] = RepGraph[allocCluster]->newEdge(v1, v2);
 162                                 }
 163                         }//else
 164
 165                 }//foralledges
 166                 //m_repEdge
 167         }//constructRepresentationGraphEdges
 168
 169         //! Computes representation graphs used for spanning tree computation
 170         void computeRepresentationGraphs(const ClusterGraph& CG,
 171                                                                          ClusterArray<Graph*>& RepGraph)
 172         {
 173                 cluster c;
 174                 forall_clusters(c, CG)
 175                 {
 176                         RepGraph[c] = new Graph;
 177                         constructRepresentationGraphNodes(CG, *RepGraph[c], c);
 178                 }//forallclusters
 179                 constructRepresentationGraphEdges(CG, RepGraph);
 180         }//computeRepresentationGraphs
 181
 182         void deleteRepresentationGraphs(const ClusterGraph& CG,
 183                                                                          ClusterArray<Graph*>& RepGraph)
 184         {
 185                 cluster c;
 186                 forall_clusters(c, CG)
 187                 {
 188                         if (RepGraph[c])
 189                                 delete RepGraph[c];
 190                 }//forallclusters
 191
 192         }//deleteRepresentationGraphs
 193
 194         //! Initializes some internally used members on CG
 195         void initialize(const ClusterGraph& CG);
 196
 197     //****************************************************
 198         //data fields
 199
 200         // store status of original edge: in subclustered graph? also used to check spanning tree
 201         //EdgeArray<int> m_edgeStatus;
 202
 203         //! store the allocation cluster to avoid multiple computation
 204         EdgeArray<cluster> m_allocCluster;
 205         //! store the representation edge
 206         EdgeArray<edge> m_repEdge;
 207         //! store the representation nodes for nodes and clusters
 208         ClusterArray<node> m_cRepNode;
 209         NodeArray<node> m_vRepNode;
 210         //pointer to input ClusterPlanRep
 211         //set in call, not to be used anywhere else
 212         //m_pCPR;
 213         //int m_genDebug; //only for debugging
 214
 215 };//cplanarsubclusteredST
 216
 217 } // end namespace ogdf
 218
 219
 220 #endif