# source:lemon-0.x/lemon/min_cost_max_flow.h@2556:74c2c81055e1

Last change on this file since 2556:74c2c81055e1 was 2556:74c2c81055e1, checked in by Peter Kovacs, 12 years ago

Cleanup in the minimum cost flow files.
The changes only affects the documentation and the look of the source codes.

File size: 4.6 KB
Line
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
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
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  /// \note \ref MinCostMaxFlow uses \ref Preflow algorithm for finding
44  /// the maximum flow value and \ref NetworkSimplex algorithm for
45  /// finding a minimum cost flow of that value.
46  ///
47  /// \param Graph The directed graph type the algorithm runs on.
48  /// \param CapacityMap The type of the capacity (upper bound) map.
49  /// \param CostMap The type of the cost (length) map.
50  ///
51  /// \warning
52  /// - Edge capacities and costs should be non-negative integers.
53  ///   However \c CostMap::Value should be signed type.
54  ///
55  /// \author Peter Kovacs
56
57  template < typename Graph,
58             typename CapacityMap = typename Graph::template EdgeMap<int>,
59             typename CostMap = typename Graph::template EdgeMap<int> >
60  class MinCostMaxFlow
61  {
62    typedef typename Graph::Node Node;
63    typedef typename Graph::Edge Edge;
64
65    typedef typename CapacityMap::Value Capacity;
66    typedef typename CostMap::Value Cost;
67    typedef typename Graph::template NodeMap<Capacity> SupplyMap;
68    typedef NetworkSimplex< Graph, CapacityMap, CapacityMap,
69                            CostMap, SupplyMap >
70      MinCostFlowImpl;
71
72  public:
73
74    /// The type of the flow map.
75    typedef typename Graph::template EdgeMap<Capacity> FlowMap;
76
77  private:
78
79    /// The directed graph the algorithm runs on.
80    const Graph &graph;
81    /// The modified capacity map.
82    const CapacityMap &capacity;
83    /// The cost map.
84    const CostMap &cost;
85    /// The edge map of the found flow.
86    FlowMap flow;
87    /// The source node.
88    Node source;
89    /// The target node.
90    Node target;
91
92    typedef Preflow<Graph, CapacityMap> MaxFlowImpl;
93    /// \brief \ref Preflow class for finding the maximum flow value.
94    MaxFlowImpl preflow;
95
96  public:
97
98    /// \brief The constructor of the class.
99    ///
100    /// The constructor of the class.
101    ///
102    /// \param _graph The directed graph the algorithm runs on.
103    /// \param _capacity The capacities (upper bounds) of the edges.
104    /// \param _cost The cost (length) values of the edges.
105    /// \param _s The source node.
106    /// \param _t The target node.
107    MinCostMaxFlow( const Graph &_graph,
108                    const CapacityMap &_capacity,
109                    const CostMap &_cost,
110                    Node _s, Node _t ) :
111      graph(_graph), capacity(_capacity), cost(_cost),
112      source(_s), target(_t), flow(_graph),
113      preflow(_graph, _capacity, _s, _t)
114    {}
115
116    /// \brief Returns a const reference to the flow map.
117    ///
118    /// Returns a const reference to the flow map.
119    ///
120    /// \pre \ref run() must be called before using this function.
121    const FlowMap& flowMap() const {
122      return flow;
123    }
124
125    /// \brief Returns the total cost of the found flow.
126    ///
127    /// Returns the total cost of the found flow. The complexity of the
128    /// function is \f$O(e) \f$.
129    ///
130    /// \pre \ref run() must be called before using this function.
131    Cost totalCost() const {
132      Cost c = 0;
133      for (typename Graph::EdgeIt e(graph); e != INVALID; ++e)
134        c += flow[e] * cost[e];
135      return c;
136    }
137
138    /// \brief Runs the algorithm.
139    void run() {
140      preflow.flowMap(flow);
141      preflow.runMinCut();
142      MinCostFlowImpl mcf_impl( graph, capacity, cost,
143                                source, target, preflow.flowValue() );
144      mcf_impl.run();
145      flow = mcf_impl.flowMap();
146    }
147
148  }; //class MinCostMaxFlow
149
150  ///@}
151
152} //namespace lemon
153
154#endif //LEMON_MIN_COST_MAX_FLOW_H
Note: See TracBrowser for help on using the repository browser.