ext/OGDF/ogdf/graphalg/MinimumCut.h

   1 /*
   2  * $Revision: 2523 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declares & implements a minimum-cut algorithm according
  11  * to an approach of Stoer and Wagner 1997. However, no Priority Queues
  12  * are used as suggested in the approach. Should be adapted to improve
  13  * performance.
  14  *
  15  * \author Mathias Jansen
  16  *
  17  * \par License:
  18  * This file is part of the Open Graph Drawing Framework (OGDF).
  19  *
  20  * \par
  21  * Copyright (C)<br>
  22  * See README.txt in the root directory of the OGDF installation for details.
  23  *
  24  * \par
  25  * This program is free software; you can redistribute it and/or
  26  * modify it under the terms of the GNU General Public License
  27  * Version 2 or 3 as published by the Free Software Foundation;
  28  * see the file LICENSE.txt included in the packaging of this file
  29  * for details.
  30  *
  31  * \par
  32  * This program is distributed in the hope that it will be useful,
  33  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  34  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  35  * GNU General Public License for more details.
  36  *
  37  * \par
  38  * You should have received a copy of the GNU General Public
  39  * License along with this program; if not, write to the Free
  40  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  41  * Boston, MA 02110-1301, USA.
  42  *
  43  * \see  http://www.gnu.org/copyleft/gpl.html
  44  ***************************************************************/
  45
  46 #ifdef _MSC_VER
  47 #pragma once
  48 #endif
  49
  50 #ifndef OGDF_MINIMUM_CUT_H
  51 #define OGDF_MINIMUM_CUT_H
  52
  53 #include <ogdf/basic/EdgeArray.h>
  54 #include <ogdf/basic/NodeArray.h>
  55 #include <ogdf/basic/GraphCopy.h>
  56 #include <ogdf/basic/simple_graph_alg.h>
  57
  58 namespace ogdf {
  59
  60
  61 class OGDF_EXPORT MinCut {
  62
  63 public:
  64         //Todo: Shift parameters to the call!
  65         //m_minCut is only initialized once!!!
  66         MinCut(Graph &G, EdgeArray<double> &w);
  67         ~MinCut();
  68
  69         // implements the main loop that computes the minimum cut by invoking function
  70         // minimumCutPhase() in each iteration. Returns the mincut value.
  71         double minimumCut();
  72
  73         // returns the edges defining the computed mincut in list \a edges.
  74         void cutEdges(List<edge> &edges, Graph &G);
  75
  76         // returns list of nodes belonging to one side of the bipartition in list \a nodes.
  77         void partition(List<node> &nodes);
  78
  79         double minCutValue() const {return m_minCut;}
  80
  81 private:
  82
  83         // stores the value of the minimum cut
  84         double m_minCut;
  85
  86         // GraphCopy of the corresponding Graph. Used for the computation in order not
  87         // to destroy the original Graph.
  88         GraphCopy m_GC;
  89
  90         // an EdgeArray containing the corresponding edge weights.
  91         EdgeArray<double> m_w;
  92
  93         // the two node lists corresponding to the node contraction
  94         List<node> m_contraction1, m_contraction2;
  95
  96         // store one side of the computed bipartition.
  97         List<node> m_partition;
  98
  99         // the list of edges defining the cut
 100         List<edge> m_cutEdges;
 101
 102         // each node has a list containing the nodes with which it has been contracted.
 103         // Because the GraphCopy \a m_GC is destroyed during the algorithm, this is
 104         // necessary to be able to determine the original nodes in the end.
 105         NodeArray<List<node> > m_contractedNodes;
 106
 107         // computes and returns the value of the minimum cut of the current phase (itertion).
 108         double minimumCutPhase();
 109
 110         // Contracts the nodes \a s and \a t, i.e \a s is collapsed to \a t.
 111         // The edge (if existing) between \a s and \t s is deleted. Edges incident to \a s are redirected to \t.
 112         // If parallel edges occur, one of them is deleted and its weight is added to the other one.
 113         void contraction(node t, node s);
 114
 115 };
 116
 117 }// end namespace
 118
 119 #endif