COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_cost_max_flow.h @ 2533:aea952a1af99

Last change on this file since 2533:aea952a1af99 was 2533:aea952a1af99, checked in by Peter Kovacs, 16 years ago

Bug fixes.

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