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, 15 years ago

Doc improvements

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
[2533]61  template < typename Graph,
[2556]62             typename CapacityMap = typename Graph::template EdgeMap<int>,
63             typename CostMap = typename Graph::template EdgeMap<int> >
[2440]64  class MinCostMaxFlow
65  {
[2587]66    GRAPH_TYPEDEFS(typename Graph);
[2440]67
68    typedef typename CapacityMap::Value Capacity;
[2556]69    typedef typename CostMap::Value Cost;
[2576]70    typedef typename Graph::template NodeMap<Cost> SupplyMap;
71
72    typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
[2440]73    typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
[2576]74                            CostMap, SupplyMap > MinCostFlowImpl;
[2440]75
76  public:
77
[2556]78    /// The type of the flow map.
[2440]79    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
[2576]80    /// The type of the potential map.
81    typedef typename Graph::template NodeMap<Cost> PotentialMap;
[2440]82
83  private:
84
[2576]85    // The directed graph the algorithm runs on
86    const Graph &_graph;
[2587]87    // The capacity map
[2576]88    const CapacityMap &_capacity;
89    // The cost map
90    const CostMap &_cost;
[2440]91
[2576]92    // Edge map of the found flow
[2587]93    FlowMap *_flow;
94    bool _local_flow;
95    // Node map of the current potentials
96    PotentialMap *_potential;
97    bool _local_potential;
[2576]98
99    // The source node
100    Node _source;
101    // The target node
102    Node _target;
[2440]103
104  public:
105
[2587]106    /// \brief Constructor.
[2440]107    ///
[2587]108    /// Constructor.
[2440]109    ///
[2587]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.
[2576]115    MinCostMaxFlow( const Graph &graph,
116                    const CapacityMap &capacity,
117                    const CostMap &cost,
118                    Node s, Node t ) :
[2587]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
[2620]129    /// \brief Set the flow map.
[2587]130    ///
[2620]131    /// Set the flow map.
[2587]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
[2620]143    /// \brief Set the potential map.
[2587]144    ///
[2620]145    /// Set the potential map.
[2587]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    /// @{
[2440]160
[2620]161    /// \brief Run the algorithm.
[2440]162    ///
[2620]163    /// Run the algorithm.
[2576]164    void run() {
[2587]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
[2576]175      MaxFlowImpl preflow(_graph, _capacity, _source, _target);
[2587]176      preflow.flowMap(*_flow).runMinCut();
177      // Running NetworkSimplex
[2576]178      MinCostFlowImpl mcf( _graph, _capacity, _cost,
179                           _source, _target, preflow.flowValue() );
[2587]180      mcf.flowMap(*_flow).potentialMap(*_potential).run();
[2576]181    }
182
[2587]183    /// @}
184
185    /// \name Query Functions
[2620]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.
[2587]190
191    /// @{
192
[2620]193    /// \brief Return a const reference to the edge map storing the
[2576]194    /// found flow.
195    ///
[2620]196    /// Return a const reference to the edge map storing the found flow.
[2440]197    ///
198    /// \pre \ref run() must be called before using this function.
199    const FlowMap& flowMap() const {
[2587]200      return *_flow;
[2576]201    }
202
[2620]203    /// \brief Return a const reference to the node map storing the
[2576]204    /// found potentials (the dual solution).
205    ///
[2620]206    /// Return a const reference to the node map storing the found
[2576]207    /// potentials (the dual solution).
208    ///
209    /// \pre \ref run() must be called before using this function.
210    const PotentialMap& potentialMap() const {
[2587]211      return *_potential;
212    }
213
[2620]214    /// \brief Return the flow on the given edge.
[2587]215    ///
[2620]216    /// Return the flow on the given edge.
[2587]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
[2620]223    /// \brief Return the potential of the given node.
[2587]224    ///
[2620]225    /// Return the potential of the given node.
[2587]226    ///
227    /// \pre \ref run() must be called before using this function.
228    Cost potential(const Node& node) const {
229      return (*_potential)[node];
[2440]230    }
231
[2620]232    /// \brief Return the total cost of the found flow.
[2440]233    ///
[2620]234    /// Return the total cost of the found flow. The complexity of the
[2440]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;
[2587]240      for (EdgeIt e(_graph); e != INVALID; ++e)
241        c += (*_flow)[e] * _cost[e];
[2440]242      return c;
243    }
244
[2587]245    /// @}
246
[2440]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.