COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_cost_max_flow.h @ 2587:061be2e64eca

Last change on this file since 2587:061be2e64eca was 2587:061be2e64eca, checked in by Peter Kovacs, 16 years ago

External flow and potential maps can be used in MinCostMaxFlow?.

File size: 7.2 KB
RevLine 
[2440]1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
[2553]5 * Copyright (C) 2003-2008
[2440]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
[2556]25/// \brief An efficient algorithm for finding a minimum cost maximum flow.
[2440]26
27#include <lemon/preflow.h>
28#include <lemon/network_simplex.h>
29#include <lemon/maps.h>
30
31namespace lemon {
32
33  /// \addtogroup min_cost_flow
34  /// @{
35
[2556]36  /// \brief An efficient algorithm for finding a minimum cost
37  /// maximum flow.
[2440]38  ///
[2556]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.
[2440]42  ///
[2576]43  /// \ref MinCostMaxFlow uses \ref Preflow for finding the maximum
44  /// flow value and \ref NetworkSimplex for finding a minimum cost
45  /// flow of that value.
46  /// According to our benchmark tests \ref Preflow is generally the
47  /// most efficient algorithm for the maximum flow problem and
48  /// \ref NetworkSimplex is the most efficient for the minimum cost
49  /// flow problem in LEMON.
[2440]50  ///
[2576]51  /// \tparam Graph The directed graph type the algorithm runs on.
52  /// \tparam CapacityMap The type of the capacity (upper bound) map.
53  /// \tparam CostMap The type of the cost (length) map.
[2440]54  ///
55  /// \warning
[2576]56  /// - Edge capacities and costs should be \e non-negative \e integers.
57  /// - \c CapacityMap::Value must be convertible to \c CostMap::Value.
[2582]58  /// - \c CostMap::Value must be signed type.
[2440]59  ///
60  /// \author Peter Kovacs
61
[2533]62  template < typename Graph,
[2556]63             typename CapacityMap = typename Graph::template EdgeMap<int>,
64             typename CostMap = typename Graph::template EdgeMap<int> >
[2440]65  class MinCostMaxFlow
66  {
[2587]67    GRAPH_TYPEDEFS(typename Graph);
[2440]68
69    typedef typename CapacityMap::Value Capacity;
[2556]70    typedef typename CostMap::Value Cost;
[2576]71    typedef typename Graph::template NodeMap<Cost> SupplyMap;
72
73    typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
[2440]74    typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
[2576]75                            CostMap, SupplyMap > MinCostFlowImpl;
[2440]76
77  public:
78
[2556]79    /// The type of the flow map.
[2440]80    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
[2576]81    /// The type of the potential map.
82    typedef typename Graph::template NodeMap<Cost> PotentialMap;
[2440]83
84  private:
85
[2576]86    // The directed graph the algorithm runs on
87    const Graph &_graph;
[2587]88    // The capacity map
[2576]89    const CapacityMap &_capacity;
90    // The cost map
91    const CostMap &_cost;
[2440]92
[2576]93    // Edge map of the found flow
[2587]94    FlowMap *_flow;
95    bool _local_flow;
96    // Node map of the current potentials
97    PotentialMap *_potential;
98    bool _local_potential;
[2576]99
100    // The source node
101    Node _source;
102    // The target node
103    Node _target;
[2440]104
105  public:
106
[2587]107    /// \brief Constructor.
[2440]108    ///
[2587]109    /// Constructor.
[2440]110    ///
[2587]111    /// \param graph The directed graph the algorithm runs on.
112    /// \param capacity The capacities (upper bounds) of the edges.
113    /// \param cost The cost (length) values of the edges.
114    /// \param s The source node.
115    /// \param t The target node.
[2576]116    MinCostMaxFlow( const Graph &graph,
117                    const CapacityMap &capacity,
118                    const CostMap &cost,
119                    Node s, Node t ) :
[2587]120      _graph(graph), _capacity(capacity), _cost(cost), _flow(0),
121      _local_flow(false), _potential(0), _local_potential(false),
122      _source(s), _target(t) {}
123
124    /// Destructor.
125    ~MinCostMaxFlow() {
126      if (_local_flow) delete _flow;
127      if (_local_potential) delete _potential;
128    }
129
130    /// \brief Sets the flow map.
131    ///
132    /// Sets the flow map.
133    ///
134    /// \return \c (*this)
135    MinCostMaxFlow& flowMap(FlowMap &map) {
136      if (_local_flow) {
137        delete _flow;
138        _local_flow = false;
139      }
140      _flow = &map;
141      return *this;
142    }
143
144    /// \brief Sets the potential map.
145    ///
146    /// Sets the potential map.
147    ///
148    /// \return \c (*this)
149    MinCostMaxFlow& potentialMap(PotentialMap &map) {
150      if (_local_potential) {
151        delete _potential;
152        _local_potential = false;
153      }
154      _potential = &map;
155      return *this;
156    }
157
158    /// \name Execution control
159    /// The only way to execute the algorithm is to call the run()
160    /// function.
161
162    /// @{
[2440]163
[2576]164    /// \brief Runs the algorithm.
[2440]165    ///
[2576]166    /// Runs the algorithm.
167    void run() {
[2587]168      // Initializing maps
169      if (!_flow) {
170        _flow = new FlowMap(_graph);
171        _local_flow = true;
172      }
173      if (!_potential) {
174        _potential = new PotentialMap(_graph);
175        _local_potential = true;
176      }
177      // Running Preflow
[2576]178      MaxFlowImpl preflow(_graph, _capacity, _source, _target);
[2587]179      preflow.flowMap(*_flow).runMinCut();
180      // Running NetworkSimplex
[2576]181      MinCostFlowImpl mcf( _graph, _capacity, _cost,
182                           _source, _target, preflow.flowValue() );
[2587]183      mcf.flowMap(*_flow).potentialMap(*_potential).run();
[2576]184    }
185
[2587]186    /// @}
187
188    /// \name Query Functions
189    /// The result of the algorithm can be obtained using these
190    /// functions.
191    /// \n run() must be called before using them.
192
193    /// @{
194
[2576]195    /// \brief Returns a const reference to the edge map storing the
196    /// found flow.
197    ///
198    /// Returns a const reference to the edge map storing the found flow.
[2440]199    ///
200    /// \pre \ref run() must be called before using this function.
201    const FlowMap& flowMap() const {
[2587]202      return *_flow;
[2576]203    }
204
205    /// \brief Returns a const reference to the node map storing the
206    /// found potentials (the dual solution).
207    ///
208    /// Returns a const reference to the node map storing the found
209    /// potentials (the dual solution).
210    ///
211    /// \pre \ref run() must be called before using this function.
212    const PotentialMap& potentialMap() const {
[2587]213      return *_potential;
214    }
215
216    /// \brief Returns the flow on the given edge.
217    ///
218    /// Returns the flow on the given edge.
219    ///
220    /// \pre \ref run() must be called before using this function.
221    Capacity flow(const Edge& edge) const {
222      return (*_flow)[edge];
223    }
224
225    /// \brief Returns the potential of the given node.
226    ///
227    /// Returns the potential of the given node.
228    ///
229    /// \pre \ref run() must be called before using this function.
230    Cost potential(const Node& node) const {
231      return (*_potential)[node];
[2440]232    }
233
234    /// \brief Returns the total cost of the found flow.
235    ///
236    /// Returns the total cost of the found flow. The complexity of the
237    /// function is \f$ O(e) \f$.
238    ///
239    /// \pre \ref run() must be called before using this function.
240    Cost totalCost() const {
241      Cost c = 0;
[2587]242      for (EdgeIt e(_graph); e != INVALID; ++e)
243        c += (*_flow)[e] * _cost[e];
[2440]244      return c;
245    }
246
[2587]247    /// @}
248
[2440]249  }; //class MinCostMaxFlow
250
251  ///@}
252
253} //namespace lemon
254
255#endif //LEMON_MIN_COST_MAX_FLOW_H
Note: See TracBrowser for help on using the repository browser.