source:lemon-0.x/lemon/min_cost_max_flow.h@2582:4f1ac622bb7a

Last change on this file since 2582:4f1ac622bb7a was 2582:4f1ac622bb7a, checked in by Peter Kovacs, 12 years ago

Avoid map copy in MinCostMaxFlow?.

File size: 5.4 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    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.flowMap(_flow).potentialMap(_potential).run();
132    }
133
134    /// \brief Returns a const reference to the edge map storing the
135    /// found flow.
136    ///
137    /// Returns a const reference to the edge map storing the found flow.
138    ///
139    /// \pre \ref run() must be called before using this function.
140    const FlowMap& flowMap() const {
141      return _flow;
142    }
143
144    /// \brief Returns a const reference to the node map storing the
145    /// found potentials (the dual solution).
146    ///
147    /// Returns a const reference to the node map storing the found
148    /// potentials (the dual solution).
149    ///
150    /// \pre \ref run() must be called before using this function.
151    const PotentialMap& potentialMap() const {
152      return _potential;
153    }
154
155    /// \brief Returns the total cost of the found flow.
156    ///
157    /// Returns the total cost of the found flow. The complexity of the
158    /// function is \f$O(e) \f$.
159    ///
160    /// \pre \ref run() must be called before using this function.
161    Cost totalCost() const {
162      Cost c = 0;
163      for (typename Graph::EdgeIt e(_graph); e != INVALID; ++e)
164        c += _flow[e] * _cost[e];
165      return c;
166    }
167
168  }; //class MinCostMaxFlow
169
170  ///@}
171
172} //namespace lemon
173
174#endif //LEMON_MIN_COST_MAX_FLOW_H
Note: See TracBrowser for help on using the repository browser.