lemon/min_cost_max_flow.h
author alpar
Fri, 08 Feb 2008 10:38:08 +0000
changeset 2569 12c2c5c4330b
parent 2553 bfced05fa852
child 2576 ae092c63d3ba
permissions -rw-r--r--
#include<cmath> -> #include<lemon/math.h>
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_MIN_COST_MAX_FLOW_H
    20 #define LEMON_MIN_COST_MAX_FLOW_H
    21 
    22 /// \ingroup min_cost_flow
    23 ///
    24 /// \file
    25 /// \brief An efficient algorithm for finding a minimum cost maximum flow.
    26 
    27 #include <lemon/preflow.h>
    28 #include <lemon/network_simplex.h>
    29 #include <lemon/maps.h>
    30 
    31 namespace lemon {
    32 
    33   /// \addtogroup min_cost_flow
    34   /// @{
    35 
    36   /// \brief An efficient algorithm for finding a minimum cost
    37   /// maximum flow.
    38   ///
    39   /// \ref MinCostMaxFlow implements an efficient algorithm for
    40   /// finding a maximum flow having minimal total cost from a given
    41   /// source node to a given target node in a directed graph.
    42   ///
    43   /// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding
    44   /// the maximum flow value and \ref NetworkSimplex algorithm for
    45   /// finding a minimum cost flow of that value.
    46   ///
    47   /// \param Graph The directed graph type the algorithm runs on.
    48   /// \param CapacityMap The type of the capacity (upper bound) map.
    49   /// \param CostMap The type of the cost (length) map.
    50   ///
    51   /// \warning
    52   /// - Edge capacities and costs should be non-negative integers.
    53   ///   However \c CostMap::Value should be signed type.
    54   ///
    55   /// \author Peter Kovacs
    56 
    57   template < typename Graph,
    58              typename CapacityMap = typename Graph::template EdgeMap<int>,
    59              typename CostMap = typename Graph::template EdgeMap<int> >
    60   class MinCostMaxFlow
    61   {
    62     typedef typename Graph::Node Node;
    63     typedef typename Graph::Edge Edge;
    64 
    65     typedef typename CapacityMap::Value Capacity;
    66     typedef typename CostMap::Value Cost;
    67     typedef typename Graph::template NodeMap<Capacity> SupplyMap;
    68     typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
    69                             CostMap, SupplyMap >
    70       MinCostFlowImpl;
    71 
    72   public:
    73 
    74     /// The type of the flow map.
    75     typedef typename Graph::template EdgeMap<Capacity> FlowMap;
    76 
    77   private:
    78 
    79     /// The directed graph the algorithm runs on.
    80     const Graph &graph;
    81     /// The modified capacity map.
    82     const CapacityMap &capacity;
    83     /// The cost map.
    84     const CostMap &cost;
    85     /// The edge map of the found flow.
    86     FlowMap flow;
    87     /// The source node.
    88     Node source;
    89     /// The target node.
    90     Node target;
    91 
    92     typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
    93     /// \brief \ref Preflow class for finding the maximum flow value.
    94     MaxFlowImpl preflow;
    95 
    96   public:
    97 
    98     /// \brief The constructor of the class.
    99     ///
   100     /// The constructor of the class.
   101     ///
   102     /// \param _graph The directed graph the algorithm runs on.
   103     /// \param _capacity The capacities (upper bounds) of the edges.
   104     /// \param _cost The cost (length) values of the edges.
   105     /// \param _s The source node.
   106     /// \param _t The target node.
   107     MinCostMaxFlow( const Graph &_graph,
   108                     const CapacityMap &_capacity,
   109                     const CostMap &_cost,
   110                     Node _s, Node _t ) :
   111       graph(_graph), capacity(_capacity), cost(_cost),
   112       source(_s), target(_t), flow(_graph),
   113       preflow(_graph, _capacity, _s, _t)
   114     {}
   115 
   116     /// \brief Returns a const reference to the flow map.
   117     ///
   118     /// Returns a const reference to the flow map.
   119     ///
   120     /// \pre \ref run() must be called before using this function.
   121     const FlowMap& flowMap() const {
   122       return flow;
   123     }
   124 
   125     /// \brief Returns the total cost of the found flow.
   126     ///
   127     /// Returns the total cost of the found flow. The complexity of the
   128     /// function is \f$ O(e) \f$.
   129     ///
   130     /// \pre \ref run() must be called before using this function.
   131     Cost totalCost() const {
   132       Cost c = 0;
   133       for (typename Graph::EdgeIt e(graph); e != INVALID; ++e)
   134         c += flow[e] * cost[e];
   135       return c;
   136     }
   137 
   138     /// \brief Runs the algorithm.
   139     void run() {
   140       preflow.flowMap(flow);
   141       preflow.runMinCut();
   142       MinCostFlowImpl mcf_impl( graph, capacity, cost,
   143                                 source, target, preflow.flowValue() );
   144       mcf_impl.run();
   145       flow = mcf_impl.flowMap();
   146     }
   147 
   148   }; //class MinCostMaxFlow
   149 
   150   ///@}
   151 
   152 } //namespace lemon
   153 
   154 #endif //LEMON_MIN_COST_MAX_FLOW_H