COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_cost_max_flow.h @ 2442:27b7c7de9cac

Last change on this file since 2442:27b7c7de9cac was 2440:c9218405595b, checked in by Balazs Dezso, 17 years ago

Various min cost flow solvers

Patch from Peter Kovacs

File size: 4.6 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
60template < 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
79  private:
80
81    /// \brief The directed graph the algorithm runs on.
82    const Graph &graph;
83    /// \brief The modified capacity map.
84    const CapacityMap &capacity;
85    /// \brief The cost map.
86    const CostMap &cost;
87    /// \brief The source node.
88    Node source;
89    /// \brief The target node.
90    Node target;
91    /// \brief The edge map of the found flow.
92    FlowMap flow;
93
94    typedef Preflow<Graph, Capacity, CapacityMap, FlowMap> PreflowImpl;
95    /// \brief \ref lemon::Preflow "Preflow" class for finding the
96    /// maximum flow value.
97    PreflowImpl preflow;
98
99  public:
100
101    /// \brief The constructor of the class.
102    ///
103    /// The constructor of the class.
104    ///
105    /// \param _graph The directed graph the algorithm runs on.
106    /// \param _capacity The capacities (upper bounds) of the edges.
107    /// \param _cost The cost (length) values of the edges.
108    /// \param _s The source node.
109    /// \param _t The target node.
110    MinCostMaxFlow( const Graph &_graph,
111                    const CapacityMap &_capacity,
112                    const CostMap &_cost,
113                    Node _s, Node _t ) :
114      graph(_graph), capacity(_capacity), cost(_cost),
115      source(_s), target(_t), flow(_graph),
116      preflow(_graph, _s, _t, _capacity, flow)
117    {}
118
119    /// \brief Returns a const reference to the flow map.
120    ///
121    /// Returns a const reference to the flow map.
122    ///
123    /// \pre \ref run() must be called before using this function.
124    const FlowMap& flowMap() const {
125      return flow;
126    }
127
128    /// \brief Returns the total cost of the found flow.
129    ///
130    /// Returns the total cost of the found flow. The complexity of the
131    /// function is \f$ O(e) \f$.
132    ///
133    /// \pre \ref run() must be called before using this function.
134    Cost totalCost() const {
135      Cost c = 0;
136      for (EdgeIt e(graph); e != INVALID; ++e)
137        c += flow[e] * cost[e];
138      return c;
139    }
140
141    /// \brief Runs the algorithm.
142    void run() {
143      preflow.phase1();
144      MinCostFlowImpl mcf_impl( graph, capacity, cost,
145                                source, target, preflow.flowValue() );
146      mcf_impl.run();
147      flow = mcf_impl.flowMap();
148    }
149
150  }; //class MinCostMaxFlow
151
152  ///@}
153
154} //namespace lemon
155
156#endif //LEMON_MIN_COST_MAX_FLOW_H
Note: See TracBrowser for help on using the repository browser.