COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_cost_flow.h @ 2579:691ce54544c5

Last change on this file since 2579:691ce54544c5 was 2579:691ce54544c5, checked in by Peter Kovacs, 13 years ago

Bug fixes in min cost flow files.
Use enum type instead of static constants in NetworkSimplex? to avoid
linker errors.

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-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_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 MinCostFlow provides an efficient algorithm for finding
37  /// a minimum cost flow.
38  ///
39  /// This class is just an alias for \ref NetworkSimplex,
40  /// which is the most efficient algorithm for the minimum cost
41  /// flow problem in LEMON according to our benchmark tests.
42  /// For the detailed documentation of this class see
43  /// \ref NetworkSimplex.
44  ///
45  /// There are four implementations for the minimum cost flow problem,
46  /// which can be used exactly the same way except for the fact that
47  /// \ref CycleCanceling does not provide dual solution (node
48  /// potentials) since it is a pure primal method.
49  /// - \ref CapacityScaling The capacity scaling algorithm.
50  /// - \ref CostScaling The cost scaling algorithm.
51  /// - \ref CycleCanceling A cycle-canceling algorithm.
52  /// - \ref NetworkSimplex The network simplex algorithm.
53  ///
54  /// \tparam Graph The directed graph type the algorithm runs on.
55  /// \tparam LowerMap The type of the lower bound map.
56  /// \tparam CapacityMap The type of the capacity (upper bound) map.
57  /// \tparam CostMap The type of the cost (length) map.
58  /// \tparam SupplyMap The type of the supply map.
59  ///
60  /// \warning
61  /// - Edge capacities and costs should be \e non-negative \e integers.
62  /// - Supply values should be \e signed \e integers.
63  /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
64  /// - \c CapacityMap::Value and \c SupplyMap::Value must be
65  ///   convertible to each other.
66  /// - All value types must be convertible to \c CostMap::Value, which
67  ///   must be signed type.
68  ///
69  /// \author Peter Kovacs
70
71  template < typename Graph,
72             typename LowerMap = typename Graph::template EdgeMap<int>,
73             typename CapacityMap = LowerMap,
74             typename CostMap = typename Graph::template EdgeMap<int>,
75             typename SupplyMap = typename Graph::template NodeMap
76                                  <typename CapacityMap::Value> >
77  class MinCostFlow :
78    public NetworkSimplex< Graph, LowerMap, CapacityMap,
79                           CostMap, SupplyMap >
80  {
81    typedef NetworkSimplex< Graph, LowerMap, CapacityMap,
82                            CostMap, SupplyMap > MinCostFlowImpl;
83    typedef typename Graph::Node Node;
84    typedef typename SupplyMap::Value Supply;
85
86  public:
87
88    /// General constructor of the class (with lower bounds).
89    MinCostFlow( const Graph &graph,
90                 const LowerMap &lower,
91                 const CapacityMap &capacity,
92                 const CostMap &cost,
93                 const SupplyMap &supply ) :
94      MinCostFlowImpl(graph, lower, capacity, cost, supply) {}
95
96    /// General constructor of the class (without lower bounds).
97    MinCostFlow( const Graph &graph,
98                 const CapacityMap &capacity,
99                 const CostMap &cost,
100                 const SupplyMap &supply ) :
101      MinCostFlowImpl(graph, capacity, cost, supply) {}
102
103    /// Simple constructor of the class (with lower bounds).
104    MinCostFlow( const Graph &graph,
105                 const LowerMap &lower,
106                 const CapacityMap &capacity,
107                 const CostMap &cost,
108                 Node s, Node t,
109                 Supply flow_value ) :
110      MinCostFlowImpl( graph, lower, capacity, cost,
111                       s, t, flow_value ) {}
112
113    /// Simple constructor of the class (without lower bounds).
114    MinCostFlow( const Graph &graph,
115                 const CapacityMap &capacity,
116                 const CostMap &cost,
117                 Node s, Node t,
118                 Supply flow_value ) :
119      MinCostFlowImpl( graph, capacity, cost,
120                       s, t, flow_value ) {}
121
122  }; //class MinCostFlow
123
124  ///@}
125
126} //namespace lemon
127
128#endif //LEMON_MIN_COST_FLOW_H
Note: See TracBrowser for help on using the repository browser.