# source:lemon-0.x/lemon/min_cost_flow.h@2476:059dcdda37c5

Last change on this file since 2476:059dcdda37c5 was 2474:e6368948d5f7, checked in by Peter Kovacs, 12 years ago

Small bug fixes and changes in the documentation.

File size: 4.1 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_FLOW_H
20#define LEMON_MIN_COST_FLOW_H
21
22/// \ingroup min_cost_flow
23///
24/// \file
25/// \brief An efficient algorithm for finding a minimum cost flow.
26
27#include <lemon/network_simplex.h>
28
29namespace lemon {
30
31  /// \addtogroup min_cost_flow
32  /// @{
33
34  /// \brief An efficient algorithm for finding a minimum cost flow.
35  ///
36  /// \ref lemon::MinCostFlow "MinCostFlow" implements an efficient
37  /// algorithm for finding a minimum cost flow.
38  ///
39  /// \note \ref lemon::MinCostFlow "MinCostFlow" is just an alias for
40  /// \ref lemon::NetworkSimplex "NetworkSimplex", wich is the most
41  /// efficient implementation for the minimum cost flow problem in the
42  /// LEMON library according to our benchmark tests.
43  ///
44  /// \note There are three implementations for the minimum cost flow
45  /// problem, that can be used in the same way.
46  /// - \ref lemon::CapacityScaling "CapacityScaling"
47  /// - \ref lemon::CycleCanceling "CycleCanceling"
48  /// - \ref lemon::NetworkSimplex "NetworkSimplex"
49  ///
50  /// \param Graph The directed graph type the algorithm runs on.
51  /// \param LowerMap The type of the lower bound map.
52  /// \param CapacityMap The type of the capacity (upper bound) map.
53  /// \param CostMap The type of the cost (length) map.
54  /// \param SupplyMap The type of the supply map.
55  ///
56  /// \warning
57  /// - Edge capacities and costs should be nonnegative integers.
58  ///   However \c CostMap::Value should be signed type.
59  /// - Supply values should be integers.
60  /// - \c LowerMap::Value must be convertible to
61  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
62  ///   convertible to \c SupplyMap::Value.
63  ///
64  /// \author Peter Kovacs
65
66template < typename Graph,
67           typename LowerMap = typename Graph::template EdgeMap<int>,
68           typename CapacityMap = LowerMap,
69           typename CostMap = typename Graph::template EdgeMap<int>,
70           typename SupplyMap = typename Graph::template NodeMap
71                                <typename CapacityMap::Value> >
72  class MinCostFlow :
73    public NetworkSimplex< Graph,
74                           LowerMap,
75                           CapacityMap,
76                           CostMap,
77                           SupplyMap >
78  {
79    typedef NetworkSimplex< Graph, LowerMap, CapacityMap,
80                            CostMap, SupplyMap >
81      MinCostFlowImpl;
82    typedef typename Graph::Node Node;
83    typedef typename SupplyMap::Value Supply;
84
85  public:
86
87    /// \brief General constructor of the class (with lower bounds).
88    MinCostFlow( const Graph &_graph,
89                 const LowerMap &_lower,
90                 const CapacityMap &_capacity,
91                 const CostMap &_cost,
92                 const SupplyMap &_supply ) :
93      MinCostFlowImpl(_graph, _lower, _capacity, _cost, _supply) {}
94
95    /// \brief General constructor of the class (without lower bounds).
96    MinCostFlow( const Graph &_graph,
97                 const CapacityMap &_capacity,
98                 const CostMap &_cost,
99                 const SupplyMap &_supply ) :
100      MinCostFlowImpl(_graph, _capacity, _cost, _supply) {}
101
102    /// \brief Simple constructor of the class (with lower bounds).
103    MinCostFlow( const Graph &_graph,
104                 const LowerMap &_lower,
105                 const CapacityMap &_capacity,
106                 const CostMap &_cost,
107                 Node _s, Node _t,
108                 Supply _flow_value ) :
109      MinCostFlowImpl( _graph, _lower, _capacity, _cost,
110                       _s, _t, _flow_value ) {}
111
112    /// \brief Simple constructor of the class (without lower bounds).
113    MinCostFlow( const Graph &_graph,
114                 const CapacityMap &_capacity,
115                 const CostMap &_cost,
116                 Node _s, Node _t,
117                 Supply _flow_value ) :
118      MinCostFlowImpl( _graph, _capacity, _cost,
119                       _s, _t, _flow_value ) {}
120
121  }; //class MinCostFlow
122
123  ///@}
124
125} //namespace lemon
126
127#endif //LEMON_MIN_COST_FLOW_H
Note: See TracBrowser for help on using the repository browser.