ext/OGDF/src/energybased/multilevelmixer/LocalBiconnectedMerger.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 Merges nodes with neighbour to get a Multilevel Graph
  11  *
  12  * \author Gereon Bartel
  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 #include <ogdf/energybased/multilevelmixer/LocalBiconnectedMerger.h>
  44 #include <ogdf/decomposition/BCTree.h>
  45 #include <ogdf/basic/List.h>
  46 #include <ogdf/basic/HashArray.h>
  47
  48 namespace ogdf {
  49
  50 LocalBiconnectedMerger::LocalBiconnectedMerger()
  51 :m_levelSizeFactor(2.0)
  52 {
  53 }
  54
  55
  56 bool LocalBiconnectedMerger::canMerge( Graph &G, node parent, node mergePartner )
  57 {
  58         return canMerge(G, parent, mergePartner, 1) && canMerge(G, parent, mergePartner, 0);
  59 }
  60
  61
  62 bool LocalBiconnectedMerger::canMerge( Graph &G, node parent, node mergePartner, int testStrength )
  63 {
  64         if ( parent->degree() <= 2 || mergePartner->degree() <= 2 || m_isCut[parent] || m_isCut[mergePartner] ) {
  65                 return true;
  66         }
  67
  68         unsigned int nodeLimit = (int)log((double)G.numberOfNodes()) * 2 + 50;
  69         unsigned int visitedNodes = 0;
  70         m_realNodeMarks.clear();
  71         HashArray<node, int> nodeMark(-1);
  72
  73         HashArray<node, bool> seen(false);
  74         seen[parent] = true;
  75         seen[mergePartner] = true;
  76
  77         HashArray<node, int> neighborStatus(0);
  78         neighborStatus[parent] = -1;
  79         neighborStatus[mergePartner] = -1;
  80
  81         List<node> bfsQueue;
  82         List<node> neighbors;
  83         int minIndex = INT_MAX;
  84         adjEntry adj;
  85         forall_adj(adj, parent) {
  86                 node temp = adj->twinNode();
  87                 bfsQueue.pushBack(temp);
  88                 nodeMark[temp] = temp->index();
  89                 if(neighborStatus[temp] == 0) {
  90                         neighbors.pushBack(temp);
  91                         neighborStatus[temp] = 1;
  92                         if (temp->index() < minIndex) {
  93                                 minIndex = temp->index();
  94                         }
  95                 }
  96         }
  97         forall_adj(adj, mergePartner) {
  98                 node temp = adj->twinNode();
  99                 bfsQueue.pushBack(temp);
 100                 nodeMark[temp] = temp->index();
 101                 if(neighborStatus[temp] == 0) {
 102                         neighbors.pushBack(temp);
 103                         neighborStatus[temp] = 1;
 104                         if (temp->index() < minIndex) {
 105                                 minIndex = temp->index();
 106                         }
 107                 }
 108         }
 109
 110         List<node> nonReachedNeighbors;
 111
 112         if (testStrength > 0)
 113         {
 114                 minIndex = INT_MAX;
 115                 for (List<node>::iterator i = neighbors.begin(); i != neighbors.end(); i++) {
 116                         node temp = *i;
 117                         forall_adj(adj, temp) {
 118                                 node neighbor = adj->twinNode();
 119                                 if (neighborStatus[neighbor] == 0 && !seen[neighbor]) {
 120                                         nonReachedNeighbors.pushBack(neighbor);
 121                                         neighborStatus[neighbor] = 2;
 122                                         bfsQueue.pushBack(neighbor);
 123                                         nodeMark[neighbor] = neighbor->index();
 124                                         if (neighbor->index() < minIndex) {
 125                                                 minIndex = neighbor->index();
 126                                         }
 127                                 }
 128                         }
 129                 }
 130
 131                 for (List<node>::iterator i = neighbors.begin(); i != neighbors.end(); i++) {
 132                         seen[*i] = true;
 133                 }
 134                 neighbors.clear();
 135         }
 136
 137         nonReachedNeighbors.conc(neighbors);
 138
 139         if (nonReachedNeighbors.empty()) {
 140                 return true;
 141         }
 142
 143         // BFS from all neighbors
 144         while(!bfsQueue.empty() && visitedNodes < nodeLimit) {
 145                 node temp = bfsQueue.popFrontRet();
 146                 if (seen[temp] || m_isCut[temp]) {
 147                         continue;
 148                 }
 149                 seen[temp] = true;
 150                 visitedNodes++;
 151
 152                 forall_adj(adj, temp) {
 153                         node neighbor = adj->twinNode();
 154                         if (neighbor == parent || neighbor == mergePartner) {
 155                                 continue;
 156                         }
 157                         if (nodeMark[neighbor] == -1) {
 158                                 nodeMark[neighbor] = realNodeMark(nodeMark[temp]);
 159                         } else {
 160                                 int neighborNM = realNodeMark(nodeMark[neighbor]);
 161                                 int tempNM = realNodeMark(nodeMark[temp]);
 162                                 int minNM = min(tempNM, neighborNM);
 163                                 if (tempNM != neighborNM) {
 164                                         int maxNM = max(tempNM, neighborNM);
 165                                         nodeMark[neighbor] = minNM;
 166                                         nodeMark[temp] = minNM;
 167                                         m_realNodeMarks[maxNM] = minNM;
 168                                         if (minNM == minIndex) {
 169                                                 // check nonReachedNeighbors
 170                                                 for (List<node>::iterator i = nonReachedNeighbors.begin(); i != nonReachedNeighbors.end(); ) {
 171                                                         if (realNodeMark(nodeMark[*i]) == minIndex) {
 172                                                                 List<node>::iterator j = i;
 173                                                                 i++;
 174                                                                 nonReachedNeighbors.del(j);
 175                                                         } else {
 176                                                                 i++;
 177                                                         }
 178                                                 }
 179                                                 if (nonReachedNeighbors.empty()) {
 180                                                         return true;
 181                                                 }
 182                                         }
 183                                 }
 184                         }
 185                         if (!seen[neighbor]) {
 186                                 bfsQueue.pushBack(neighbor);
 187                         }
 188                 }
 189         }
 190
 191         // free some space
 192         m_realNodeMarks.clear();
 193         return false;
 194 }
 195
 196
 197 bool LocalBiconnectedMerger::doMergeIfPossible( Graph &G, MultilevelGraph &MLG, node parent, node mergePartner, int level )
 198 {
 199         if (canMerge(G, parent, mergePartner)) {
 200                 return doMerge(MLG, parent, mergePartner, level);
 201         }
 202         return true;
 203 }
 204
 205
 206 // tracks substitute Nodes
 207 // updates the bi-connectivity check data structure m_isCut
 208 // merges the nodes
 209 bool LocalBiconnectedMerger::doMerge( MultilevelGraph &MLG, node parent, node mergePartner, int level )
 210 {
 211         NodeMerge * NM = new NodeMerge(level);
 212         bool ret = MLG.changeNode(NM, parent, MLG.radius(parent), mergePartner);
 213         OGDF_ASSERT( ret );
 214         MLG.moveEdgesToParent(NM, mergePartner, parent, true, m_adjustEdgeLengths);
 215         ret = MLG.postMerge(NM, mergePartner);
 216         if( !ret ) {
 217                 delete NM;
 218                 return false;
 219         }
 220         m_substituteNodes[mergePartner] = parent;
 221         if (m_isCut[mergePartner]) {
 222                 m_isCut[parent] = true;
 223         }
 224         return true;
 225 }
 226
 227
 228 void LocalBiconnectedMerger::initCuts(Graph &G)
 229 {
 230         // BCTree does not work for large graphs due to recursion depth (stack overflow)
 231         // Uncomment below to get speedup once BCTree is fixed.
 232
 233 //      BCTree BCT(G);
 234         m_isCut.init(G, false);
 235
 236 /*      node v;
 237         forall_nodes(v, G) {
 238                 if( BCT.typeOfGNode(v) == BCTree::GNodeType::CutVertex ) {
 239                         m_isCut[v] = true;
 240                 }
 241         }*/
 242 }
 243
 244
 245 bool LocalBiconnectedMerger::buildOneLevel(MultilevelGraph &MLG)
 246 {
 247         Graph &G = MLG.getGraph();
 248         int level = MLG.getLevel() + 1;
 249 //      std::cout << "Level: " << level << std::endl;
 250
 251         m_substituteNodes.init(G, 0);
 252         initCuts(G);
 253
 254         int numNodes = G.numberOfNodes();
 255
 256         if (numNodes <= 3) {
 257                 return false;
 258         }
 259
 260         NodeArray<bool> nodeMarks(G, false);
 261         std::vector<edge> untouchedEdges;
 262         std::vector<edge> matching;
 263         std::vector<edge> edgeCover;
 264         std::vector<edge> rest;
 265         edge e;
 266         forall_edges(e, G) {
 267                 untouchedEdges.push_back(e);
 268         }
 269
 270         while (!untouchedEdges.empty())
 271         {
 272                 int rndIndex = randomNumber(0, (int)untouchedEdges.size()-1);
 273                 edge randomEdge = untouchedEdges[rndIndex];
 274                 untouchedEdges[rndIndex] = untouchedEdges.back();
 275                 untouchedEdges.pop_back();
 276
 277                 node one = randomEdge->source();
 278                 node two = randomEdge->target();
 279                 if (!nodeMarks[one] && !nodeMarks[two]) {
 280                         matching.push_back(randomEdge);
 281                         nodeMarks[one] = true;
 282                         nodeMarks[two] = true;
 283                 } else {
 284                         rest.push_back(randomEdge);
 285                 }
 286         }
 287
 288         while (!rest.empty())
 289         {
 290                 int rndIndex = randomNumber(0, (int)rest.size()-1);
 291                 edge randomEdge = rest[rndIndex];
 292                 rest[rndIndex] = rest.back();
 293                 rest.pop_back();
 294
 295                 node one = randomEdge->source();
 296                 node two = randomEdge->target();
 297                 if (!nodeMarks[one] || !nodeMarks[two]) {
 298                         edgeCover.push_back(randomEdge);
 299                         nodeMarks[one] = true;
 300                         nodeMarks[two] = true;
 301                 }
 302         }
 303
 304         bool retVal = false;
 305
 306         while ((!matching.empty() || !edgeCover.empty()) && G.numberOfNodes() > numNodes / m_levelSizeFactor) {
 307                 int rndIndex;
 308                 edge coveringEdge;
 309
 310                 if (!matching.empty()) {
 311                         rndIndex = randomNumber(0, (int)matching.size()-1);
 312                         coveringEdge = matching[rndIndex];
 313                         matching[rndIndex] = matching.back();
 314                         matching.pop_back();
 315                 } else {
 316                         rndIndex = randomNumber(0, (int)edgeCover.size()-1);
 317                         coveringEdge = edgeCover[rndIndex];
 318                         edgeCover[rndIndex] = edgeCover.back();
 319                         edgeCover.pop_back();
 320                 }
 321
 322                 node mergeNode;
 323                 node parent;
 324
 325                 // choose high degree node as parent!
 326                 mergeNode = coveringEdge->source();
 327                 parent = coveringEdge->target();
 328                 if (mergeNode->degree() > parent->degree()) {
 329                         mergeNode = coveringEdge->target();
 330                         parent = coveringEdge->source();
 331                 }
 332
 333                 while(m_substituteNodes[parent] != 0) {
 334                         parent = m_substituteNodes[parent];
 335                 }
 336                 while(m_substituteNodes[mergeNode] != 0) {
 337                         mergeNode = m_substituteNodes[mergeNode];
 338                 }
 339
 340                 if (MLG.getNode(parent->index()) != parent
 341                         || MLG.getNode(mergeNode->index()) != mergeNode
 342                         || parent == mergeNode)
 343                 {
 344                         continue;
 345                 }
 346                 //KK: looks like a flaw? TODO: Check the return value concept
 347                 retVal = doMergeIfPossible(G, MLG, parent, mergeNode, level);
 348         }
 349
 350         if (numNodes == G.numberOfNodes()) {
 351                 return false;
 352         } else {
 353                 return retVal;
 354         }
 355 }
 356
 357
 358 void LocalBiconnectedMerger::setFactor(double factor)
 359 {
 360         m_levelSizeFactor = factor;
 361 }
 362
 363
 364 int LocalBiconnectedMerger::realNodeMark( int index )
 365 {
 366         if (!m_realNodeMarks.isDefined(index) || m_realNodeMarks[index] == index) {
 367                 return index;
 368         } else {
 369                 return realNodeMark(m_realNodeMarks[index]);
 370         }
 371 }
 372
 373 } // namespace ogdf