ext/OGDF/src/graphalg/MinimumCut.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 Declares & Implements a minimum-cut algorithmn according
  11  * to an approach of Stoer and Wagner 1997
  12  *
  13  * \author Mathias Jansen
  14  *
  15  * \par License:
  16  * This file is part of the Open Graph Drawing Framework (OGDF).
  17  *
  18  * \par
  19  * Copyright (C)<br>
  20  * See README.txt in the root directory of the OGDF installation for details.
  21  *
  22  * \par
  23  * This program is free software; you can redistribute it and/or
  24  * modify it under the terms of the GNU General Public License
  25  * Version 2 or 3 as published by the Free Software Foundation;
  26  * see the file LICENSE.txt included in the packaging of this file
  27  * for details.
  28  *
  29  * \par
  30  * This program is distributed in the hope that it will be useful,
  31  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  32  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  33  * GNU General Public License for more details.
  34  *
  35  * \par
  36  * You should have received a copy of the GNU General Public
  37  * License along with this program; if not, write to the Free
  38  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  39  * Boston, MA 02110-1301, USA.
  40  *
  41  * \see  http://www.gnu.org/copyleft/gpl.html
  42  ***************************************************************/
  43
  44 #include <ogdf/basic/BinaryHeap.h>
  45 #include <ogdf/graphalg/MinimumCut.h>
  46
  47 //used solely for efficiency and correctness checks of priority
  48 //queue usage
  49 //#define USE_PRIO
  50
  51
  52 namespace ogdf {
  53
  54
  55 MinCut::MinCut(Graph &G, EdgeArray<double> &w) : m_GC(G) {
  56
  57         // Due to the node contraction (which destroys the Graph step by step),
  58         // we have to create a GraphCopy.
  59         //m_GC = new GraphCopy(G);
  60
  61         // Edge weights are initialized.
  62         edge e;
  63         m_w.init(m_GC);
  64         forall_edges(e,m_GC) {
  65                 m_w[e] = w[(m_GC).original(e)];
  66         }
  67         m_contractedNodes.init(m_GC);
  68         m_minCut = 1e20;
  69 }
  70
  71
  72 MinCut::~MinCut() {}
  73
  74
  75 void MinCut::contraction(node t, node s) {
  76
  77         /*
  78          * The contraction of the two nodes \as and \a t is performed as follows:
  79          * in the first step, all edges between \a s and \a t are deleted, and all edges incident
  80          * to \a s are redirected to \a t. Then, node \a s is deleted and the adjacency list of \a t
  81          * is checked for parallel edges. If k parallel edges are found, k-1 of them are deleted
  82          * and their weights are added to the edge that is left.
  83          */
  84
  85         // Step 1: redirecting edges and deleting node \a s
  86         adjEntry adj = s->firstAdj();
  87         while (adj != 0)
  88         {
  89                 adjEntry succ = adj->succ();
  90                 edge e = adj->theEdge();
  91                 if (e->source() == t || e->target() == t) {
  92                         m_GC.delEdge(e);
  93                 }
  94                 else if (e->source() == s) {
  95                         m_GC.moveSource(e,t);
  96                 }
  97                 else {
  98                         m_GC.moveTarget(e,t);
  99                 }
 100                 adj = succ;
 101         }
 102         m_GC.delNode(s);
 103
 104         /*
 105          * Because of technical problems that occur when deleting edges and thus adjacency entries in a loop,
 106          * a NodeArray is filled with the edges incident to node \a t.
 107          * This NodeArray is checked for entries with more than one edge, which corresponds
 108          * to parallel edges.
 109          */
 110
 111         // NodeArray containing parallel edges
 112         NodeArray<List<edge> > adjNodes(m_GC);
 113
 114         forall_adj(adj,t) {
 115                 adjNodes[adj->twinNode()].pushBack(adj->theEdge());
 116         }
 117
 118         // Step 2: deleting parallel edges and adding their weights
 119         node v = m_GC.firstNode();
 120         while (v!=0) {
 121                 if (adjNodes[v].size() > 1) {
 122                         edge e = adjNodes[v].front();
 123                         adjNodes[v].popFront();
 124                         ListConstIterator<edge> it;
 125                         for (it=adjNodes[v].begin(); it.valid(); ++it) {
 126
 127                                 // Add weight of current edge to \a e.
 128                                 m_w[e] += m_w[(*it)];
 129                                 m_GC.delEdge(*it);
 130                         }
 131                 }
 132                 v = v->succ();
 133         }
 134 }
 135
 136
 137 double MinCut::minimumCutPhase() {
 138
 139         /*
 140          * This function computes the mincut of the current phase.
 141          * First, nodes are added successively in descending order of the sum of
 142          * their incident edge weights to the list \a markedNodes.
 143          * Afterwards, the current mincut value \a cutOfThePhase is computed, which corresponds to the
 144          * sum of the weights of those edges incident to node \a t, which is the node that has been
 145          * added to list \a markedNodes at last.
 146          * At the end, the two last added nodes (\a s and \a t) are contracted and the \cutOfThePhase
 147          * is returned.
 148          */
 149
 150         // Contains the mincut value according to the current phase.
 151         double cutOfThePhase;
 152
 153         List<node> markedNodes;
 154         List<node> leftoverNodes;
 155
 156         // Contains for each node the sum of the edge weights of those edges
 157         // incident to nodes in list \a markedNodes
 158         NodeArray<double> nodePrio(m_GC);
 159 #ifdef USE_PRIO
 160         BinaryHeap<node> pq(m_GC.numberOfNodes());
 161         NodeArray<const BinaryHeap<node>::Element*> pqEntry(m_GC);
 162 #endif
 163         // The two nodes that have been added last to the list \a markedNodes.
 164         // These are the two nodes that have to be contracted at the end of the function.
 165         node s,t;
 166
 167         // Initialization of data structures
 168         node v;
 169         forall_nodes(v,m_GC) {
 170                 leftoverNodes.pushBack(v);
 171 #ifdef USE_PRIO
 172                 pqEntry[v] = &(pq.insert(v, 0.0));
 173 #endif
 174         }
 175         nodePrio.fill(0.0); //should do this in constructor init above
 176
 177         // The start-node can be chosen arbitrarily. It has no effect on the correctness of the algorithm.
 178         // Here, always the first node in the list \a leftoverNodes is chosen.
 179         v = leftoverNodes.popFrontRet(); markedNodes.pushBack(v);
 180         adjEntry adj;
 181         //assumes that no multiedges exist
 182         forall_adj(adj,v) {
 183                 nodePrio[adj->twinNode()] = m_w[adj->theEdge()];
 184 #ifdef USE_PRIO
 185                 pq.decPriority(*pqEntry[adj->twinNode()], -m_w[adj->theEdge()]);
 186 #endif
 187         }
 188
 189         // Temporary variables
 190         ListIterator<node> it1;
 191         node maxWeightNode; ListIterator<node> maxWeightNodeIt;
 192         //replaces line above
 193 #ifdef USE_PRIO
 194         node maxWeightNodePq;
 195 #endif
 196         double mostTightly;
 197
 198         // Successively adding the most tightly connected node.
 199         while (markedNodes.size() != m_GC.numberOfNodes()) {
 200
 201                 mostTightly = 0.0;
 202                 maxWeightNode = NULL;
 203 #ifdef USE_PRIO
 204                 //Find the most tightly connected node
 205                 maxWeightNodePq = NULL;
 206                 if (pq.top()->getPriority() < mostTightly)
 207                 {
 208                         mostTightly = (maxWeightNodePq = pq.extractMin())->getPriority();
 209                 }
 210 #endif
 211                 // The loop computing the most tightly connected node to the current set \a markedNodes.
 212                 // For better performance, this should be done using PriorityQueues! Since this algorithmn
 213                 // is only used for the Cut-separation within the Branch&Cut-algorithmn for MCPSP, only small
 214                 // and moderate Graph sizes are considered. Thus, the total running time is hardly affected.
 215                 for(it1=leftoverNodes.begin(); it1.valid(); ++it1) {
 216
 217                         if(nodePrio[(*it1)] > mostTightly) {
 218                                 maxWeightNode = (*it1);
 219                                 maxWeightNodeIt = it1;
 220                                 mostTightly = nodePrio[(*it1)];
 221                         }
 222                 }
 223 #ifdef USE_PRIO
 224                 OGDF_ASSERT(maxWeightNode == maxWeightNodePq);
 225 #endif
 226
 227                 // If the graph is not connected, maxWeightNode might not be updated in each iteration.
 228                 // Todo: Why not? Just because priority is zero? Then we can simplify this...
 229                 // Hence, in this case we simply choose one of the leftoverNodes (the first one).
 230                 if (maxWeightNode == NULL) {
 231                         maxWeightNode = leftoverNodes.front();
 232                         maxWeightNodeIt = leftoverNodes.begin();
 233                 }
 234
 235                 // Adding \a maxWeightNode to the list \a markedNodes
 236                 markedNodes.pushBack(maxWeightNode);
 237
 238                 // Deleting \a maxWeightNode from list \a leftoverNodes
 239                 leftoverNodes.del(maxWeightNodeIt);
 240
 241                 // Updating the node priorities
 242                 adjEntry a;
 243                 forall_adj(a,maxWeightNode) {
 244                         nodePrio[a->twinNode()] += m_w[a->theEdge()];
 245                 }
 246 #ifdef USE_PRIO
 247                 //replaces loop above
 248                 forall_adj(a, maxWeightNodePq) {
 249                         //should have some decreasePriorityBy instead...
 250                         pq.decPriority(*pqEntry[a->twinNode()],
 251                                 pqEntry[a->twinNode()]->getPriority() - m_w[a->theEdge()]);
 252                 }
 253 #endif
 254         }// end of loop while(markedNodes.size()...)
 255
 256         // Computing value \a cutOfThePhase
 257         cutOfThePhase = 0.0;
 258         ListConstIterator<node> last = markedNodes.rbegin();
 259         t = (*last); s = *(last.pred());
 260         adjEntry t_adj;
 261         forall_adj(t_adj,t) {
 262                 cutOfThePhase += m_w[t_adj->theEdge()];
 263         }
 264
 265         // If the current \a cutOfThePhase is strictly smaller than the global mincut value,
 266         // the partition defining the mincut has to be updated.
 267         if(cutOfThePhase < m_minCut) {
 268                 m_partition.clear();
 269                 m_partition.pushBack(m_GC.original(t));
 270                 for(ListConstIterator<node> it = m_contractedNodes[t].begin(); it.valid(); ++it) {
 271                         m_partition.pushBack(*it);
 272                 }
 273         }
 274
 275         // Since nodes in \a m_GC correspond to sets of nodes (due to the node contraction),
 276         // the NodeArray \a m_contractedNodes has to be updated.
 277         m_contractedNodes[t].pushBack(m_GC.original(s));
 278         ListConstIterator<node> contractIt;
 279         for (contractIt = m_contractedNodes[s].begin(); contractIt.valid(); ++contractIt) {
 280                 m_contractedNodes[t].pushBack((*contractIt));
 281         }
 282
 283         // Performing the node contraction of nodes \a s and \a t.
 284         contraction(t,s);
 285
 286         return cutOfThePhase;
 287 }
 288
 289
 290 double MinCut::minimumCut() {
 291
 292         /*
 293          * Main loop of the algorithm
 294          * As long as GraphCopy \a m_GC contains at least two nodes,
 295          * function minimumCutPhase() is invoked and \a m_minCut is updated
 296          */
 297
 298         for (int i=m_GC.numberOfNodes(); i>1; --i) {
 299                 m_minCut = min(m_minCut,minimumCutPhase());
 300                 if (m_minCut == 0.0) return m_minCut;
 301         }
 302         return m_minCut;
 303 }
 304
 305
 306 void MinCut::partition(List<node> &nodes) {
 307
 308         nodes.clear();
 309         ListConstIterator<node> it;
 310         for (it=m_partition.begin(); it.valid(); ++it) {
 311                 nodes.pushBack(*it);
 312         }
 313 }
 314
 315
 316 void MinCut::cutEdges(List<edge> &edges, Graph &G) {
 317
 318         edges.clear();
 319         NodeArray<bool> inPartition(G);
 320         inPartition.fill(false);
 321         ListConstIterator<node> nodeIt;
 322
 323         for (nodeIt=m_partition.begin(); nodeIt.valid(); ++nodeIt) {
 324                 inPartition[*nodeIt] = true;
 325         }
 326
 327         for (nodeIt=m_partition.begin(); nodeIt.valid(); ++nodeIt) {
 328                 edge e;
 329                 forall_adj_edges(e,(*nodeIt)) {
 330                         if(e->source() == (*nodeIt)) {
 331                                 if(inPartition[e->target()] == false) {
 332                                         edges.pushBack(e);
 333                                 }
 334                         } else {
 335                                 if(inPartition[e->source()] == false) {
 336                                         edges.pushBack(e);
 337                                 }
 338                         }
 339                 }
 340         }
 341 }
 342
 343 }