COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_cost_max_flow.h @ 2620:8f41a3129746

Last change on this file since 2620:8f41a3129746 was 2620:8f41a3129746, checked in by Peter Kovacs, 11 years ago

Doc improvements

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  template < typename Graph,
62             typename CapacityMap = typename Graph::template EdgeMap<int>,
63             typename CostMap = typename Graph::template EdgeMap<int> >
64  class MinCostMaxFlow
65  {
66    GRAPH_TYPEDEFS(typename Graph);
67
68    typedef typename CapacityMap::Value Capacity;
69    typedef typename CostMap::Value Cost;
70    typedef typename Graph::template NodeMap<Cost> SupplyMap;
71
72    typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
73    typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
74                            CostMap, SupplyMap > MinCostFlowImpl;
75
76  public:
77
78    /// The type of the flow map.
79    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
80    /// The type of the potential map.
81    typedef typename Graph::template NodeMap<Cost> PotentialMap;
82
83  private:
84
85    // The directed graph the algorithm runs on
86    const Graph &_graph;
87    // The capacity map
88    const CapacityMap &_capacity;
89    // The cost map
90    const CostMap &_cost;
91
92    // Edge map of the found flow
93    FlowMap *_flow;
94    bool _local_flow;
95    // Node map of the current potentials
96    PotentialMap *_potential;
97    bool _local_potential;
98
99    // The source node
100    Node _source;
101    // The target node
102    Node _target;
103
104  public:
105
106    /// \brief Constructor.
107    ///
108    /// Constructor.
109    ///
110    /// \param graph The directed graph the algorithm runs on.
111    /// \param capacity The capacities (upper bounds) of the edges.
112    /// \param cost The cost (length) values of the edges.
113    /// \param s The source node.
114    /// \param t The target node.
115    MinCostMaxFlow( const Graph &graph,
116                    const CapacityMap &capacity,
117                    const CostMap &cost,
118                    Node s, Node t ) :
119      _graph(graph), _capacity(capacity), _cost(cost), _flow(0),
120      _local_flow(false), _potential(0), _local_potential(false),
121      _source(s), _target(t) {}
122
123    /// Destructor.
124    ~MinCostMaxFlow() {
125      if (_local_flow) delete _flow;
126      if (_local_potential) delete _potential;
127    }
128
129    /// \brief Set the flow map.
130    ///
131    /// Set the flow map.
132    ///
133    /// \return \c (*this)
134    MinCostMaxFlow& flowMap(FlowMap &map) {
135      if (_local_flow) {
136        delete _flow;
137        _local_flow = false;
138      }
139      _flow = &map;
140      return *this;
141    }
142
143    /// \brief Set the potential map.
144    ///
145    /// Set the potential map.
146    ///
147    /// \return \c (*this)
148    MinCostMaxFlow& potentialMap(PotentialMap &map) {
149      if (_local_potential) {
150        delete _potential;
151        _local_potential = false;
152      }
153      _potential = &map;
154      return *this;
155    }
156
157    /// \name Execution control
158
159    /// @{
160
161    /// \brief Run the algorithm.
162    ///
163    /// Run the algorithm.
164    void run() {
165      // Initializing maps
166      if (!_flow) {
167        _flow = new FlowMap(_graph);
168        _local_flow = true;
169      }
170      if (!_potential) {
171        _potential = new PotentialMap(_graph);
172        _local_potential = true;
173      }
174      // Running Preflow
175      MaxFlowImpl preflow(_graph, _capacity, _source, _target);
176      preflow.flowMap(*_flow).runMinCut();
177      // Running NetworkSimplex
178      MinCostFlowImpl mcf( _graph, _capacity, _cost,
179                           _source, _target, preflow.flowValue() );
180      mcf.flowMap(*_flow).potentialMap(*_potential).run();
181    }
182
183    /// @}
184
185    /// \name Query Functions
186    /// The results of the algorithm can be obtained using these
187    /// functions.\n
188    /// \ref lemon::MinCostMaxFlow::run() "run()" must be called before
189    /// using them.
190
191    /// @{
192
193    /// \brief Return a const reference to the edge map storing the
194    /// found flow.
195    ///
196    /// Return a const reference to the edge map storing the found flow.
197    ///
198    /// \pre \ref run() must be called before using this function.
199    const FlowMap& flowMap() const {
200      return *_flow;
201    }
202
203    /// \brief Return a const reference to the node map storing the
204    /// found potentials (the dual solution).
205    ///
206    /// Return a const reference to the node map storing the found
207    /// potentials (the dual solution).
208    ///
209    /// \pre \ref run() must be called before using this function.
210    const PotentialMap& potentialMap() const {
211      return *_potential;
212    }
213
214    /// \brief Return the flow on the given edge.
215    ///
216    /// Return the flow on the given edge.
217    ///
218    /// \pre \ref run() must be called before using this function.
219    Capacity flow(const Edge& edge) const {
220      return (*_flow)[edge];
221    }
222
223    /// \brief Return the potential of the given node.
224    ///
225    /// Return the potential of the given node.
226    ///
227    /// \pre \ref run() must be called before using this function.
228    Cost potential(const Node& node) const {
229      return (*_potential)[node];
230    }
231
232    /// \brief Return the total cost of the found flow.
233    ///
234    /// Return the total cost of the found flow. The complexity of the
235    /// function is \f$ O(e) \f$.
236    ///
237    /// \pre \ref run() must be called before using this function.
238    Cost totalCost() const {
239      Cost c = 0;
240      for (EdgeIt e(_graph); e != INVALID; ++e)
241        c += (*_flow)[e] * _cost[e];
242      return c;
243    }
244
245    /// @}
246
247  }; //class MinCostMaxFlow
248
249  ///@}
250
251} //namespace lemon
252
253#endif //LEMON_MIN_COST_MAX_FLOW_H
Note: See TracBrowser for help on using the repository browser.