ext/OGDF/ogdf/module/MinCostFlowModule.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 Declaration of base class of min-cost-flow algorithms
  11  *
  12  * Includes some useful functions dealing with min-cost flow
  13  * (generater, checker).
  14  *
  15  * \author Carsten Gutwenger
  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
  47 #ifdef _MSC_VER
  48 #pragma once
  49 #endif
  50
  51 #ifndef OGDF_MIN_COST_FLOW_MODULE_H
  52 #define OGDF_MIN_COST_FLOW_MODULE_H
  53
  54
  55 #include <ogdf/basic/Graph.h>
  56
  57
  58 namespace ogdf {
  59
  60
  61 /**
  62  * \brief Interface for min-cost flow algorithms.
  63  */
  64 class OGDF_EXPORT MinCostFlowModule
  65 {
  66 public:
  67         //! Initializes a min-cost flow module.
  68         MinCostFlowModule() { }
  69
  70         // destruction
  71         virtual ~MinCostFlowModule() { }
  72
  73         /**
  74          * \brief Computes a min-cost flow in the directed graph \a G.
  75          *
  76          * \pre \a G must be connected, \a lowerBound[\a e] \f$\leq\f$ \a upperBound[\a e]
  77          *      for all edges \a e, and the sum over all supplies must be zero.
  78          *
  79          * @param G is the directed input graph.
  80          * @param lowerBound gives the lower bound for the flow on each edge.
  81          * @param upperBound gives the upper bound for the flow on each edge.
  82          * @param cost gives the costs for each edge.
  83          * @param supply gives the supply (or demand if negative) of each node.
  84          * @param flow is assigned the computed flow on each edge.
  85          * @param dual is assigned the computed dual variables.
  86          * \return true iff a feasible min-cost flow exists.
  87          */
  88         virtual bool call(
  89                 const Graph &G,                   // directed graph
  90                 const EdgeArray<int> &lowerBound, // lower bound for flow
  91                 const EdgeArray<int> &upperBound, // upper bound for flow
  92                 const EdgeArray<int> &cost,       // cost of an edge
  93                 const NodeArray<int> &supply,     // supply (if neg. demand) of a node
  94                 EdgeArray<int> &flow,                     // computed flow
  95                 NodeArray<int> &dual            // computed dual variables
  96                 ) = 0;
  97
  98
  99         //
 100         // static functions
 101         //
 102
 103         /**
 104          * \brief Generates an instance of a min-cost flow problem with \a n nodes and
 105          *        \a m+\a n edges.
 106          */
 107         static void generateProblem(
 108                 Graph &G,
 109                 int n,
 110                 int m,
 111                 EdgeArray<int> &lowerBound,
 112                 EdgeArray<int> &upperBound,
 113                 EdgeArray<int> &cost,
 114                 NodeArray<int> &supply);
 115
 116
 117         /**
 118          * \brief Checks if a given min-cost flow problem instance satisfies
 119          *        the preconditions.
 120          * The following preconditions are checked:
 121          *   - \a lowerBound[\a e] \f$\leq\f$ \a upperBound[\a e] for all edges \a e
 122          *   - sum over all \a supply[\a v] = 0
 123          *
 124          * @param G is the input graph.
 125          * @param lowerBound gives the lower bound for the flow on each edge.
 126          * @param upperBound gives the upper bound for the flow on each edge.
 127          * @param supply gives the supply (or demand if negative) of each node.
 128          * \return true iff the problem satisfies the preconditions.
 129          */
 130         static bool checkProblem(
 131                 const Graph &G,
 132                 const EdgeArray<int> &lowerBound,
 133                 const EdgeArray<int> &upperBound,
 134                 const NodeArray<int> &supply);
 135
 136
 137
 138         /**
 139          * \brief checks if a computed flow is a feasible solution to the given problem
 140          *        instance.
 141          *
 142          * Checks in particular if:
 143          *   - \a lowerBound[\a e] \f$\leq\f$ \a flow[\a e] \f$\leq\f$ \a upperBound[\a e]
 144          *   - sum \a flow[\a e], \a e is outgoing edge of \a v minus
 145          *     sum \a flow[\a e], \a e is incoming edge of \a v equals \a supply[\a v]
 146          *     for each node \a v
 147          *
 148          * @param G is the input graph.
 149          * @param lowerBound gives the lower bound for the flow on each edge.
 150          * @param upperBound gives the upper bound for the flow on each edge.
 151          * @param cost gives the costs for each edge.
 152          * @param supply gives the supply (or demand if negative) of each node.
 153          * @param flow is the flow on each edge.
 154          * @param value is assigned the value of the flow.
 155          * \return true iff the solution is feasible.
 156          */
 157         static bool checkComputedFlow(
 158                 const Graph &G,
 159                 EdgeArray<int> &lowerBound,
 160                 EdgeArray<int> &upperBound,
 161                 EdgeArray<int> &cost,
 162                 NodeArray<int> &supply,
 163                 EdgeArray<int> &flow,
 164                 int &value);
 165
 166         /**
 167          * \brief checks if a computed flow is a feasible solution to the given problem
 168          *        instance.
 169          *
 170          * Checks in particular if:
 171          *   - \a lowerBound[\a e] \f$\leq\f$ \a flow[\a e] \f$\leq\f$ \a upperBound[\a e]
 172          *   - sum \a flow[\a e], \a e is outgoing edge of \a v minus
 173          *     sum \a flow[\a e], \a e is incoming edge of \a v equals \a supply[\a v]
 174          *     for each node \a v
 175          *
 176          * @param G is the input graph.
 177          * @param lowerBound gives the lower bound for the flow on each edge.
 178          * @param upperBound gives the upper bound for the flow on each edge.
 179          * @param cost gives the costs for each edge.
 180          * @param supply gives the supply (or demand if negative) of each node.
 181          * @param flow is the flow on each edge.
 182          * \return true iff the solution is feasible.
 183          */
 184         static bool checkComputedFlow(
 185                 const Graph &G,
 186                 EdgeArray<int> &lowerBound,
 187                 EdgeArray<int> &upperBound,
 188                 EdgeArray<int> &cost,
 189                 NodeArray<int> &supply,
 190                 EdgeArray<int> &flow)
 191         {
 192                 int value;
 193                 return checkComputedFlow(
 194                         G,lowerBound,upperBound,cost,supply,flow,value);
 195         }
 196 };
 197
 198
 199 } // end namespace ogdf
 200
 201
 202 #endif