COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_cost_flow.h @ 2559:75dd6d724f26

Last change on this file since 2559:75dd6d724f26 was 2556:74c2c81055e1, checked in by Peter Kovacs, 16 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.3 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  /// \note \ref MinCostFlow is just an alias for \ref NetworkSimplex,
40  /// which is the most efficient implementation for the minimum cost
41  /// flow problem in the LEMON library according to our benchmark
42  /// tests.
43  ///
44  /// \note There are three implementations for the minimum cost flow
45  /// problem, that can be used exactly the same way.
46  /// - \ref CapacityScaling
47  /// - \ref CycleCanceling
48  /// - \ref NetworkSimplex
49  ///
50  /// \note For the detailed documentation of this class see
51  /// \ref NetworkSimplex.
52  ///
53  /// \param Graph The directed graph type the algorithm runs on.
54  /// \param LowerMap The type of the lower bound map.
55  /// \param CapacityMap The type of the capacity (upper bound) map.
56  /// \param CostMap The type of the cost (length) map.
57  /// \param SupplyMap The type of the supply map.
58  ///
59  /// \warning
60  /// - Edge capacities and costs should be non-negative integers.
61  ///   However \c CostMap::Value should be signed type.
62  /// - Supply values should be signed integers.
63  /// - \c LowerMap::Value must be convertible to
64  ///   \c CapacityMap::Value and \c CapacityMap::Value must be
65  ///   convertible to \c SupplyMap::Value.
66  ///
67  /// \author Peter Kovacs
68
69  template < typename Graph,
70             typename LowerMap = typename Graph::template EdgeMap<int>,
71             typename CapacityMap = LowerMap,
72             typename CostMap = typename Graph::template EdgeMap<int>,
73             typename SupplyMap = typename Graph::template NodeMap
74                                  <typename CapacityMap::Value> >
75  class MinCostFlow :
76    public NetworkSimplex< Graph, LowerMap, CapacityMap,
77                           CostMap, SupplyMap >
78  {
79    typedef NetworkSimplex< Graph, LowerMap, CapacityMap,
80                            CostMap, SupplyMap > MinCostFlowImpl;
81    typedef typename Graph::Node Node;
82    typedef typename SupplyMap::Value Supply;
83
84  public:
85
86    /// General constructor of the class (with lower bounds).
87    MinCostFlow( const Graph &graph,
88                 const LowerMap &lower,
89                 const CapacityMap &capacity,
90                 const CostMap &cost,
91                 const SupplyMap &supply ) :
92      MinCostFlowImpl(graph, lower, capacity, cost, supply) {}
93
94    /// General constructor of the class (without lower bounds).
95    MinCostFlow( const Graph &graph,
96                 const CapacityMap &capacity,
97                 const CostMap &_ost,
98                 const SupplyMap &supply ) :
99      MinCostFlowImpl(graph, capacity, cost, supply) {}
100
101    /// Simple constructor of the class (with lower bounds).
102    MinCostFlow( const Graph &graph,
103                 const LowerMap &lower,
104                 const CapacityMap &capacity,
105                 const CostMap &_ost,
106                 Node s, Node t,
107                 Supply flow_value ) :
108      MinCostFlowImpl( graph, lower, capacity, cost,
109                       s, t, flow_value ) {}
110
111    /// Simple constructor of the class (without lower bounds).
112    MinCostFlow( const Graph &graph,
113                 const CapacityMap &capacity,
114                 const CostMap &cost,
115                 Node s, Node t,
116                 Supply flow_value ) :
117      MinCostFlowImpl( graph, capacity, cost,
118                       s, t, flow_value ) {}
119
120  }; //class MinCostFlow
121
122  ///@}
123
124} //namespace lemon
125
126#endif //LEMON_MIN_COST_FLOW_H
Note: See TracBrowser for help on using the repository browser.