COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_cost_max_flow.h @ 2619:30fb4d68b0e8

Last change on this file since 2619:30fb4d68b0e8 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
Line 
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
31namespace 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  /// \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.
50  ///
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.
54  ///
55  /// \warning
56  /// - Edge capacities and costs should be \e non-negative \e integers.
57  /// - \c CapacityMap::Value must be convertible to \c CostMap::Value.
58  /// - \c CostMap::Value must be signed type.
59  ///
60  /// \author Peter Kovacs
61
62  template < typename Graph,
63             typename CapacityMap = typename Graph::template EdgeMap<int>,
64             typename CostMap = typename Graph::template EdgeMap<int> >
65  class MinCostMaxFlow
66  {
67    GRAPH_TYPEDEFS(typename Graph);
68
69    typedef typename CapacityMap::Value Capacity;
70    typedef typename CostMap::Value Cost;
71    typedef typename Graph::template NodeMap<Cost> SupplyMap;
72
73    typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
74    typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
75                            CostMap, SupplyMap > MinCostFlowImpl;
76
77  public:
78
79    /// The type of the flow map.
80    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
81    /// The type of the potential map.
82    typedef typename Graph::template NodeMap<Cost> PotentialMap;
83
84  private:
85
86    // The directed graph the algorithm runs on
87    const Graph &_graph;
88    // The capacity map
89    const CapacityMap &_capacity;
90    // The cost map
91    const CostMap &_cost;
92
93    // Edge map of the found flow
94    FlowMap *_flow;
95    bool _local_flow;
96    // Node map of the current potentials
97    PotentialMap *_potential;
98    bool _local_potential;
99
100    // The source node
101    Node _source;
102    // The target node
103    Node _target;
104
105  public:
106
107    /// \brief Constructor.
108    ///
109    /// Constructor.
110    ///
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.
116    MinCostMaxFlow( const Graph &graph,
117                    const CapacityMap &capacity,
118                    const CostMap &cost,
119                    Node s, Node t ) :
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    /// @{
163
164    /// \brief Runs the algorithm.
165    ///
166    /// Runs the algorithm.
167    void run() {
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
178      MaxFlowImpl preflow(_graph, _capacity, _source, _target);
179      preflow.flowMap(*_flow).runMinCut();
180      // Running NetworkSimplex
181      MinCostFlowImpl mcf( _graph, _capacity, _cost,
182                           _source, _target, preflow.flowValue() );
183      mcf.flowMap(*_flow).potentialMap(*_potential).run();
184    }
185
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
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.
199    ///
200    /// \pre \ref run() must be called before using this function.
201    const FlowMap& flowMap() const {
202      return *_flow;
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 {
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];
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;
242      for (EdgeIt e(_graph); e != INVALID; ++e)
243        c += (*_flow)[e] * _cost[e];
244      return c;
245    }
246
247    /// @}
248
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.