ext/OGDF/src/decomposition/DynamicBCTree.cpp

   1 /*
   2  * $Revision: 2552 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of class DynamicBCTree
  11  *
  12  * \author Jan Papenfu&szlig;
  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
  44 #include <ogdf/decomposition/DynamicBCTree.h>
  45
  46
  47 namespace ogdf {
  48
  49
  50 void DynamicBCTree::init ()
  51 {
  52         m_bNode_owner.init(m_B);
  53         m_bNode_degree.init(m_B);
  54         node vB;
  55         forall_nodes (vB,m_B) {
  56                 m_bNode_owner[vB] = vB;
  57                 m_bNode_degree[vB] = vB->degree();
  58         }
  59 }
  60
  61
  62 node DynamicBCTree::unite (node uB, node vB, node wB)
  63 {
  64         node uH = cutVertex(vB,uB);
  65         node vH = cutVertex(vB,vB);
  66         node wH = cutVertex(vB,wB);
  67
  68         node mH,sH;
  69         if (uH->degree()>=wH->degree()) { mH = uH; sH = wH; } else { mH = wH; sH = uH; }
  70
  71         node mB,sB,tB;
  72         if (m_bNode_numNodes[uB]>=m_bNode_numNodes[wB]) { mB = uB; sB = wB; } else { mB = wB; sB = uB; }
  73         if (m_bNode_degree[vB]==2) {
  74                 if (m_bNode_numNodes[mB]==0) { mB = vB; sB = uB; tB = wB; } else tB = vB;
  75         }
  76
  77         if (m_bNode_hParNode[vB]==uH) {
  78                 m_bNode_hParNode[vB] = mH;
  79                 m_bNode_hRefNode[mB] = m_bNode_hRefNode[uB];
  80                 m_bNode_hParNode[mB] = m_bNode_hParNode[uB];
  81         }
  82         else if (m_bNode_hParNode[vB]==wH) {
  83                 m_bNode_hParNode[vB] = mH;
  84                 m_bNode_hRefNode[mB] = m_bNode_hRefNode[wB];
  85                 m_bNode_hParNode[mB] = m_bNode_hParNode[wB];
  86         }
  87         else if (m_bNode_degree[vB]==2) {
  88                 m_bNode_hRefNode[mB] = 0;
  89                 m_bNode_hParNode[mB] = 0;
  90         }
  91         else {
  92                 m_bNode_hRefNode[mB] = mH;
  93                 m_bNode_hParNode[mB] = vH;
  94         }
  95
  96         adjEntry aH = sH->firstAdj();
  97         while (aH) {
  98                 adjEntry bH = aH->succ();
  99                 if (aH->theEdge()->source()==sH) m_H.moveSource(aH->theEdge(),mH);
 100                 else m_H.moveTarget(aH->theEdge(),mH);
 101                 aH = bH;
 102         }
 103         m_H.delNode(sH);
 104
 105         m_numB--;
 106         m_bNode_owner[sB] = mB;
 107         m_bNode_hEdges[mB].conc(m_bNode_hEdges[sB]);
 108         m_bNode_numNodes[mB] = m_bNode_numNodes[uB] + m_bNode_numNodes[wB] - 1;
 109         m_bNode_degree[mB] = m_bNode_degree[uB] + m_bNode_degree[wB] - 1;
 110
 111         if (m_bNode_degree[vB]==2) {
 112                 m_numC--;
 113                 m_bNode_type[vB] = BComp;
 114                 m_gNode_hNode[m_hNode_gNode[vH]] = mH;
 115                 m_H.delNode(vH);
 116                 m_bNode_owner[tB] = mB;
 117                 m_bNode_hEdges[mB].conc(m_bNode_hEdges[tB]);
 118                 m_bNode_degree[mB]--;
 119         }
 120         else m_bNode_degree[vB]--;
 121
 122         return mB;
 123 }
 124
 125
 126 node DynamicBCTree::find (node vB) const
 127 {
 128         if (!vB) return 0;
 129         if (m_bNode_owner[vB]==vB) return vB;
 130         return m_bNode_owner[vB] = find(m_bNode_owner[vB]);
 131 }
 132
 133
 134 node DynamicBCTree::bcproper (node vG) const
 135 {
 136         if (!vG) return 0;
 137         node vH = m_gNode_hNode[vG];
 138         return m_hNode_bNode[vH] = find(m_hNode_bNode[vH]);
 139 }
 140
 141
 142 node DynamicBCTree::bcproper (edge eG) const
 143 {
 144         if (!eG) return 0;
 145         edge eH = m_gEdge_hEdge[eG];
 146         return m_hEdge_bNode[eH] = find(m_hEdge_bNode[eH]);
 147 }
 148
 149
 150 node DynamicBCTree::parent (node vB) const
 151 {
 152         if (!vB) return 0;
 153         node vH = m_bNode_hParNode[vB];
 154         if (!vH) return 0;
 155         return m_hNode_bNode[vH] = find(m_hNode_bNode[vH]);
 156 }
 157
 158
 159 node DynamicBCTree::condensePath (node sG, node tG)
 160 {
 161         SList<node>& pB = findPath(sG,tG);
 162         SListConstIterator<node> iB = pB.begin();
 163         node uB = *iB++;
 164         if (iB.valid()) {
 165                 if (m_bNode_type[uB]==CComp) uB = *iB++;
 166                 while (iB.valid()) {
 167                         node vB = *iB++;
 168                         if (!iB.valid()) break;
 169                         node wB = *iB++;
 170                         uB = unite(uB,vB,wB);
 171                 }
 172         }
 173         delete &pB;
 174         return uB;
 175 }
 176
 177
 178 edge DynamicBCTree::updateInsertedEdge (edge eG)
 179 {
 180         node vB = condensePath(eG->source(),eG->target());
 181         edge eH = m_H.newEdge(repVertex(eG->source(),vB),repVertex(eG->target(),vB));
 182         m_bNode_hEdges[vB].pushBack(eH);
 183         m_hEdge_bNode[eH] = vB;
 184         m_hEdge_gEdge[eH] = eG;
 185         m_gEdge_hEdge[eG] = eH;
 186         return eG;
 187 }
 188
 189
 190 node DynamicBCTree::updateInsertedNode (edge eG, edge fG)
 191 {
 192         node eB = bcproper(eG);
 193         node uG = fG->source();
 194         m_gNode_isMarked[uG] = false;
 195
 196         if (numberOfEdges(eB)==1) {
 197                 node tG = fG->target();
 198                 node sH = m_gEdge_hEdge[eG]->target();
 199                 m_hNode_gNode[sH] = uG;
 200
 201                 node uB = m_B.newNode();
 202                 node uH = m_H.newNode();
 203                 m_bNode_type[uB] = CComp;
 204                 m_bNode_owner[uB] = uB;
 205                 m_bNode_numNodes[uB] = 1;
 206                 m_bNode_degree[uB] = 2;
 207                 m_bNode_isMarked[uB] = false;
 208                 m_bNode_hRefNode[uB] = uH;
 209                 m_hNode_bNode[uH] = uB;
 210                 m_hNode_gNode[uH] = uG;
 211                 m_gNode_hNode[uG] = uH;
 212
 213                 node fB = m_B.newNode();
 214                 node vH = m_H.newNode();
 215                 node wH = m_H.newNode();
 216                 edge fH = m_H.newEdge(vH,wH);
 217                 m_bNode_type[fB] = BComp;
 218                 m_bNode_owner[fB] = fB;
 219                 m_bNode_numNodes[fB] = 2;
 220                 m_bNode_degree[fB] = 2;
 221                 m_bNode_isMarked[fB] = false;
 222                 m_bNode_hEdges[fB].pushBack(fH);
 223                 m_hNode_bNode[vH] = fB;
 224                 m_hNode_bNode[wH] = fB;
 225                 m_hEdge_bNode[fH] = fB;
 226                 m_hNode_gNode[vH] = uG;
 227                 m_hNode_gNode[wH] = tG;
 228                 m_hEdge_gEdge[fH] = fG;
 229                 m_gEdge_hEdge[fG] = fH;
 230
 231                 node tH = m_gNode_hNode[tG];
 232                 if (m_bNode_hParNode[eB]==tH) {
 233                         m_bNode_hParNode[eB] = uH;
 234                         m_bNode_hParNode[uB] = vH;
 235                         m_bNode_hRefNode[fB] = wH;
 236                         m_bNode_hParNode[fB] = tH;
 237                 }
 238                 else {
 239                         node tB = bcproper(tG);
 240                         m_bNode_hParNode[tB] = wH;
 241                         m_bNode_hRefNode[fB] = vH;
 242                         m_bNode_hParNode[fB] = uH;
 243                         m_bNode_hParNode[uB] = sH;
 244                 }
 245         }
 246         else {
 247                 edge fH = m_H.split(m_gEdge_hEdge[eG]);
 248                 m_bNode_hEdges[eB].pushBack(fH);
 249                 m_hEdge_bNode[fH] = eB;
 250                 m_hEdge_gEdge[fH] = fG;
 251                 m_gEdge_hEdge[fG] = fH;
 252                 node uH = fH->source();
 253                 m_bNode_numNodes[eB]++;
 254                 m_hNode_bNode[uH] = eB;
 255                 m_hNode_gNode[uH] = uG;
 256                 m_gNode_hNode[uG] = uH;
 257         }
 258         return uG;
 259 }
 260
 261
 262 node DynamicBCTree::bComponent (node uG, node vG) const
 263 {
 264         node uB = this->bcproper(uG);
 265         node vB = this->bcproper(vG);
 266         if (uB==vB) return uB;
 267         if (typeOfBNode(uB)==BComp) {
 268                 if (typeOfBNode(vB)==BComp) return 0;
 269                 if (this->parent(uB)==vB) return uB;
 270                 if (this->parent(vB)==uB) return uB;
 271                 return 0;
 272         }
 273         if (typeOfBNode(vB)==BComp) {
 274                 if (this->parent(uB)==vB) return vB;
 275                 if (this->parent(vB)==uB) return vB;
 276                 return 0;
 277         }
 278         node pB = this->parent(uB);
 279         node qB = this->parent(vB);
 280         if (pB==qB) return pB;
 281         if (this->parent(pB)==vB) return pB;
 282         if (this->parent(qB)==uB) return qB;
 283         return 0;
 284 }
 285
 286
 287
 288 }