ext/OGDF/src/energybased/multilevelmixer/EdgeCoverMerger.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/EdgeCoverMerger.h>
  44
  45 namespace ogdf {
  46
  47 EdgeCoverMerger::EdgeCoverMerger()
  48 :m_levelSizeFactor(2.0)
  49 {
  50 }
  51
  52 bool EdgeCoverMerger::buildOneLevel(MultilevelGraph &MLG)
  53 {
  54         Graph &G = MLG.getGraph();
  55         int level = MLG.getLevel() + 1;
  56         m_substituteNodes.init(G, 0);
  57
  58         int numNodes = G.numberOfNodes();
  59
  60         if (numNodes <= 3) {
  61                 return false;
  62         }
  63
  64         NodeArray<bool> nodeMarks(G, false);
  65         std::vector<edge> untouchedEdges;
  66         std::vector<edge> matching;
  67         std::vector<edge> edgeCover;
  68         std::vector<edge> rest;
  69         edge e;
  70         forall_edges(e, G) {
  71                 untouchedEdges.push_back(e);
  72         }
  73
  74         while (!untouchedEdges.empty())
  75         {
  76                 int rndIndex = randomNumber(0, (int)untouchedEdges.size()-1);
  77                 edge randomEdge = untouchedEdges[rndIndex];
  78                 untouchedEdges[rndIndex] = untouchedEdges.back();
  79                 untouchedEdges.pop_back();
  80
  81                 node one = randomEdge->source();
  82                 node two = randomEdge->target();
  83                 if (!nodeMarks[one] && !nodeMarks[two]) {
  84                         matching.push_back(randomEdge);
  85                         nodeMarks[one] = true;
  86                         nodeMarks[two] = true;
  87                 } else {
  88                         rest.push_back(randomEdge);
  89                 }
  90         }
  91
  92         while (!rest.empty())
  93         {
  94                 int rndIndex = randomNumber(0, (int)rest.size()-1);
  95                 edge randomEdge = rest[rndIndex];
  96                 rest[rndIndex] = rest.back();
  97                 rest.pop_back();
  98
  99                 node one = randomEdge->source();
 100                 node two = randomEdge->target();
 101                 if (!nodeMarks[one] || !nodeMarks[two]) {
 102                         edgeCover.push_back(randomEdge);
 103                         nodeMarks[one] = true;
 104                         nodeMarks[two] = true;
 105                 }
 106         }
 107
 108         bool retVal = false;
 109
 110         while ((!matching.empty() || !edgeCover.empty()) && G.numberOfNodes() > numNodes / m_levelSizeFactor) {
 111                 int rndIndex;
 112                 edge coveringEdge;
 113
 114                 if (!matching.empty()) {
 115                         rndIndex = randomNumber(0, (int)matching.size()-1);
 116                         coveringEdge = matching[rndIndex];
 117                         matching[rndIndex] = matching.back();
 118                         matching.pop_back();
 119                 } else {
 120                         rndIndex = randomNumber(0, (int)edgeCover.size()-1);
 121                         coveringEdge = edgeCover[rndIndex];
 122                         edgeCover[rndIndex] = edgeCover.back();
 123                         edgeCover.pop_back();
 124                 }
 125
 126                 node mergeNode;
 127                 node parent;
 128
 129                 // choose high degree node as parent!
 130                 mergeNode = coveringEdge->source();
 131                 parent = coveringEdge->target();
 132                 if (mergeNode->degree() > parent->degree()) {
 133                         mergeNode = coveringEdge->target();
 134                         parent = coveringEdge->source();
 135                 }
 136
 137                 while(m_substituteNodes[parent] != 0) {
 138                         parent = m_substituteNodes[parent];
 139                 }
 140                 while(m_substituteNodes[mergeNode] != 0) {
 141                         mergeNode = m_substituteNodes[mergeNode];
 142                 }
 143
 144                 if (MLG.getNode(parent->index()) != parent
 145                         || MLG.getNode(mergeNode->index()) != mergeNode
 146                         || parent == mergeNode)
 147                 {
 148                         continue;
 149                 }
 150
 151                 retVal = doMerge(MLG, parent, mergeNode, level);
 152         }
 153
 154         return retVal;
 155 }
 156
 157
 158 void EdgeCoverMerger::setFactor(double factor)
 159 {
 160         m_levelSizeFactor = factor;
 161 }
 162
 163
 164 // tracks substitute Nodes
 165 bool EdgeCoverMerger::doMerge( MultilevelGraph &MLG, node parent, node mergePartner, int level )
 166 {
 167         NodeMerge * NM = new NodeMerge(level);
 168         bool ret = MLG.changeNode(NM, parent, MLG.radius(parent), mergePartner);
 169         OGDF_ASSERT( ret );
 170         MLG.moveEdgesToParent(NM, mergePartner, parent, true, m_adjustEdgeLengths);
 171         ret = MLG.postMerge(NM, mergePartner);
 172         if( !ret ) {
 173                 delete NM;
 174                 return false;
 175         }
 176         m_substituteNodes[mergePartner] = parent;
 177         return true;
 178 }
 179
 180 } // namespace ogdf