ext/OGDF/src/decomposition/BCTree.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 BCTree
  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/BCTree.h>
  45
  46
  47 namespace ogdf {
  48
  49
  50 void BCTree::init (node vG)
  51 {
  52         m_numB = 0;
  53         m_numC = 0;
  54
  55         m_gNode_isMarked.init(m_G,false);
  56         m_gNode_hNode.init(m_G,0);
  57         m_gEdge_hEdge.init(m_G);
  58
  59         m_bNode_type.init(m_B);
  60         m_bNode_isMarked.init(m_B);
  61         m_bNode_hRefNode.init(m_B);
  62         m_bNode_hParNode.init(m_B);
  63         m_bNode_hEdges.init(m_B);
  64         m_bNode_numNodes.init(m_B);
  65
  66         m_hNode_bNode.init(m_H);
  67         m_hEdge_bNode.init(m_H);
  68         m_hNode_gNode.init(m_H);
  69         m_hEdge_gEdge.init(m_H);
  70
  71         m_count = 0;
  72         m_number.init(m_G,0);
  73         m_lowpt.init(m_G);
  74         m_gtoh.init(m_G);
  75
  76         biComp(0,vG);
  77
  78         m_number.init();
  79         m_lowpt.init();
  80         m_eStack.clear();
  81         m_gtoh.init();
  82
  83         node uB;
  84         forall_nodes (uB,m_B) {
  85                 node vB = parent(uB);
  86                 if (vB) m_B.newEdge(uB,vB);
  87         }
  88 }
  89
  90
  91 void BCTree::initNotConnected (node vG)
  92 {
  93         m_numB = 0;
  94         m_numC = 0;
  95
  96         m_gNode_isMarked.init(m_G,false);
  97         m_gNode_hNode.init(m_G,0);
  98         m_gEdge_hEdge.init(m_G);
  99
 100         m_bNode_type.init(m_B);
 101         m_bNode_isMarked.init(m_B);
 102         m_bNode_hRefNode.init(m_B);
 103         m_bNode_hParNode.init(m_B);
 104         m_bNode_hEdges.init(m_B);
 105         m_bNode_numNodes.init(m_B);
 106
 107         m_hNode_bNode.init(m_H);
 108         m_hEdge_bNode.init(m_H);
 109         m_hNode_gNode.init(m_H);
 110         m_hEdge_gEdge.init(m_H);
 111
 112         m_count = 0;
 113         m_number.init(m_G,0);
 114         m_lowpt.init(m_G);
 115         m_gtoh.init(m_G);
 116
 117         biComp(0,vG);
 118         // cout << m_count << endl << flush;
 119
 120         node v;
 121
 122         // call biComp for all nodes that are not in the
 123         //  first connected component
 124         forall_nodes(v, m_G)
 125                 if (m_number[v] == 0){
 126                         m_eStack.clear();
 127                         biComp(0, v);
 128                 }
 129
 130         m_lowpt.init();
 131         m_eStack.clear();
 132         m_gtoh.init();
 133
 134         node uB;
 135         forall_nodes (uB,m_B) {
 136                 node vB = parent(uB);
 137                 if (vB) m_B.newEdge(uB,vB);
 138         }
 139 }
 140
 141
 142 void BCTree::biComp (adjEntry adjuG, node vG)
 143 {
 144         m_lowpt[vG] = m_number[vG] = ++m_count;
 145
 146         adjEntry adj;
 147         forall_adj (adj,vG) {
 148                 //edge eG = adj->theEdge();
 149                 node wG = adj->twinNode();
 150                 if ((adjuG != 0) && (adj == adjuG->twin())) continue;
 151                 if (m_number[wG]==0) {
 152                         m_eStack.push(adj);
 153                         biComp(adj,wG);
 154                         if (m_lowpt[wG]<m_lowpt[vG]) m_lowpt[vG] = m_lowpt[wG];
 155                         if (m_lowpt[wG]>=m_number[vG]) {
 156                                 node bB = m_B.newNode();
 157                                 m_bNode_type[bB] = BComp;
 158                                 m_bNode_isMarked[bB] = false;
 159                                 m_bNode_hRefNode[bB] = 0;
 160                                 m_bNode_hParNode[bB] = 0;
 161                                 m_bNode_numNodes[bB] = 0;
 162                                 m_numB++;
 163                                 adjEntry adjfG;
 164                                 do {
 165                                         adjfG = m_eStack.pop();
 166                                         edge fG = adjfG->theEdge();
 167                                         for (int i=0; i<=1; ++i) {
 168                                                 node xG = i ? fG->target() : fG->source();
 169                                                 if (m_gNode_isMarked[xG]) continue;
 170                                                 m_gNode_isMarked[xG] = true;
 171                                                 m_nodes.pushBack(xG);
 172                                                 m_bNode_numNodes[bB]++;
 173                                                 node zH = m_H.newNode();
 174                                                 m_hNode_bNode[zH] = bB;
 175                                                 m_hNode_gNode[zH] = xG;
 176                                                 m_gtoh[xG] = zH;
 177                                                 node xH = m_gNode_hNode[xG];
 178                                                 if (!xH) m_gNode_hNode[xG] = zH;
 179                                                 else {
 180                                                         node xB = m_hNode_bNode[xH];
 181                                                         if (!m_bNode_hRefNode[xB]) {
 182                                                                 node cB = m_B.newNode();
 183                                                                 node yH = m_H.newNode();
 184                                                                 m_hNode_bNode[yH] = cB;
 185                                                                 m_hNode_gNode[yH] = xG;
 186                                                                 m_gNode_hNode[xG] = yH;
 187                                                                 m_bNode_type[cB] = CComp;
 188                                                                 m_bNode_isMarked[cB] = false;
 189                                                                 m_bNode_hRefNode[xB] = xH;
 190                                                                 m_bNode_hParNode[xB] = yH;
 191                                                                 m_bNode_hRefNode[cB] = yH;
 192                                                                 m_bNode_hParNode[cB] = zH;
 193                                                                 m_bNode_numNodes[cB] = 1;
 194                                                                 m_numC++;
 195                                                         }
 196                                                         else {
 197                                                                 node yH = m_bNode_hParNode[xB];
 198                                                                 node yB = m_hNode_bNode[yH];
 199                                                                 m_bNode_hParNode[yB] = xH;
 200                                                                 m_bNode_hRefNode[yB] = yH;
 201                                                                 m_bNode_hParNode[xB] = zH;
 202                                                         }
 203                                                 }
 204                                         }
 205                                         edge fH = m_H.newEdge(m_gtoh[fG->source()],m_gtoh[fG->target()]);
 206                                         m_bNode_hEdges[bB].pushBack(fH);
 207                                         m_hEdge_bNode[fH] = bB;
 208                                         m_hEdge_gEdge[fH] = fG;
 209                                         m_gEdge_hEdge[fG] = fH;
 210                                 } while (adj!=adjfG);
 211                                 while (!m_nodes.empty()) m_gNode_isMarked[m_nodes.popFrontRet()] = false;
 212                         }
 213                 }
 214                 else if (m_number[wG]<m_number[vG]) {
 215                         m_eStack.push(adj);
 216                         if (m_number[wG]<m_lowpt[vG]) m_lowpt[vG] = m_number[wG];
 217                 }
 218         }
 219 }
 220
 221
 222 node BCTree::parent (node vB) const
 223 {
 224         if (!vB) return 0;
 225         node vH = m_bNode_hParNode[vB];
 226         if (!vH) return 0;
 227         return m_hNode_bNode[vH];
 228 }
 229
 230
 231 node BCTree::bComponent (node uG, node vG) const
 232 {
 233         node uB = bcproper(uG);
 234         node vB = bcproper(vG);
 235         if (uB==vB) return uB;
 236         if (typeOfBNode(uB)==BComp) {
 237                 if (typeOfBNode(vB)==BComp) return 0;
 238                 if (parent(uB)==vB) return uB;
 239                 if (parent(vB)==uB) return uB;
 240                 return 0;
 241         }
 242         if (typeOfBNode(vB)==BComp) {
 243                 if (parent(uB)==vB) return vB;
 244                 if (parent(vB)==uB) return vB;
 245                 return 0;
 246         }
 247         node pB = parent(uB);
 248         node qB = parent(vB);
 249         if (pB==qB) return pB;
 250         if (parent(pB)==vB) return pB;
 251         if (parent(qB)==uB) return qB;
 252         return 0;
 253 }
 254
 255
 256 node BCTree::findNCA (node uB, node vB) const
 257 {
 258         if (m_bNode_isMarked[uB]) return uB;
 259         m_bNode_isMarked[uB] = true;
 260         node wB = parent(uB);
 261         if (wB) wB = findNCA(vB,wB);
 262         else for (wB=vB; !m_bNode_isMarked[wB]; wB=parent(wB));
 263         m_bNode_isMarked[uB] = false;
 264         return wB;
 265 }
 266
 267
 268 SList<node>& BCTree::findPath (node sG, node tG) const
 269 {
 270         SList<node>& pB = *OGDF_NEW SList<node>;
 271         node sB = bcproper(sG);
 272         node tB = bcproper(tG);
 273         node nB = findNCA(sB,tB);
 274         for (pB.pushBack(sB); sB!=nB; pB.pushBack(sB)) sB = parent(sB);
 275         for (SListIterator<node> iB=pB.rbegin(); tB!=nB; tB=parent(tB)) pB.insertAfter(tB,iB);
 276         return pB;
 277 }
 278
 279
 280 SList<node>* BCTree::findPathBCTree (node sB, node tB) const
 281 {
 282         SList<node> *pB = OGDF_NEW SList<node>;
 283         node nB = findNCA(sB,tB);
 284         for (pB->pushBack(sB); sB!=nB; pB->pushBack(sB)) sB = parent(sB);
 285         for (SListIterator<node> iB=pB->rbegin(); tB!=nB; tB=parent(tB)) pB->insertAfter(tB,iB);
 286         return pB;
 287 }
 288
 289
 290 node BCTree::repVertex (node uG, node vB) const
 291 {
 292         node uB = bcproper(uG);
 293         if (uB==vB) return m_gNode_hNode[uG];
 294         if (typeOfBNode(uB)==BComp) return 0;
 295         if (parent(uB)==vB) return m_bNode_hParNode[uB];
 296         if (uB==parent(vB)) return m_bNode_hRefNode[vB];
 297         return 0;
 298 }
 299
 300 node BCTree::cutVertex (node uB, node vB) const
 301 {
 302         if (uB==vB) return typeOfBNode(uB)==CComp ? m_bNode_hRefNode[vB] : 0;
 303         if (parent(uB)==vB) return m_bNode_hParNode[uB];
 304         if (uB==parent(vB)) return m_bNode_hRefNode[vB];
 305         return 0;
 306 }
 307
 308
 309 }