COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_cost_max_flow.h @ 2578:979a0b389f84

Last change on this file since 2578:979a0b389f84 was 2576:ae092c63d3ba, checked in by Peter Kovacs, 12 years ago

Improvements in MinCostFlow? and MinCostMaxFlow?.

Main changes:

  • MinCostMaxFlow? also provides dual solution.
  • Change the name of private members to start with "_".
  • Change the name of function parameters not to start with "_".
  • Remove unnecessary documentation for private members.
  • Doc improvements.
File size: 5.5 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  ///   However \c CostMap::Value must be signed type.
58  /// - \c CapacityMap::Value must be convertible to \c CostMap::Value.
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    typedef typename Graph::Node Node;
68    typedef typename Graph::Edge Edge;
69
70    typedef typename CapacityMap::Value Capacity;
71    typedef typename CostMap::Value Cost;
72    typedef typename Graph::template NodeMap<Cost> SupplyMap;
73
74    typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
75    typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
76                            CostMap, SupplyMap > MinCostFlowImpl;
77
78  public:
79
80    /// The type of the flow map.
81    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
82    /// The type of the potential map.
83    typedef typename Graph::template NodeMap<Cost> PotentialMap;
84
85  private:
86
87    // The directed graph the algorithm runs on
88    const Graph &_graph;
89    // The modified capacity map
90    const CapacityMap &_capacity;
91    // The cost map
92    const CostMap &_cost;
93
94    // Edge map of the found flow
95    FlowMap _flow;
96    // Node map of the found potentials
97    PotentialMap _potential;
98
99    // The source node
100    Node _source;
101    // The target node
102    Node _target;
103
104  public:
105
106    /// \brief The constructor of the class.
107    ///
108    /// The constructor of the class.
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(graph),
120      _potential(graph), _source(s), _target(t)
121    {}
122
123    /// \brief Runs the algorithm.
124    ///
125    /// Runs the algorithm.
126    void run() {
127      MaxFlowImpl preflow(_graph, _capacity, _source, _target);
128      preflow.flowMap(_flow).runMinCut();
129      MinCostFlowImpl mcf( _graph, _capacity, _cost,
130                           _source, _target, preflow.flowValue() );
131      mcf.run();
132      _flow = mcf.flowMap();
133      _potential = mcf.potentialMap();
134    }
135
136    /// \brief Returns a const reference to the edge map storing the
137    /// found flow.
138    ///
139    /// Returns a const reference to the edge map storing the found flow.
140    ///
141    /// \pre \ref run() must be called before using this function.
142    const FlowMap& flowMap() const {
143      return _flow_result;
144    }
145
146    /// \brief Returns a const reference to the node map storing the
147    /// found potentials (the dual solution).
148    ///
149    /// Returns a const reference to the node map storing the found
150    /// potentials (the dual solution).
151    ///
152    /// \pre \ref run() must be called before using this function.
153    const PotentialMap& potentialMap() const {
154      return _potential_result;
155    }
156
157    /// \brief Returns the total cost of the found flow.
158    ///
159    /// Returns the total cost of the found flow. The complexity of the
160    /// function is \f$ O(e) \f$.
161    ///
162    /// \pre \ref run() must be called before using this function.
163    Cost totalCost() const {
164      Cost c = 0;
165      for (typename Graph::EdgeIt e(graph); e != INVALID; ++e)
166        c += _flow[e] * _cost[e];
167      return c;
168    }
169
170  }; //class MinCostMaxFlow
171
172  ///@}
173
174} //namespace lemon
175
176#endif //LEMON_MIN_COST_MAX_FLOW_H
Note: See TracBrowser for help on using the repository browser.