COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_cost_flow.h

Last change on this file was 2620:8f41a3129746, checked in by Peter Kovacs, 11 years ago

Doc improvements

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-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.
47  /// - \ref CapacityScaling
48  /// - \ref CostScaling
49  /// - \ref CycleCanceling
50  /// - \ref NetworkSimplex
51  ///
52  /// \tparam Graph The directed graph type the algorithm runs on.
53  /// \tparam LowerMap The type of the lower bound map.
54  /// \tparam CapacityMap The type of the capacity (upper bound) map.
55  /// \tparam CostMap The type of the cost (length) map.
56  /// \tparam SupplyMap The type of the supply map.
57  ///
58  /// \warning
59  /// - Edge capacities and costs should be \e non-negative \e integers.
60  /// - Supply values should be \e signed \e integers.
61  /// - The value types of the maps should be convertible to each other.
62  /// - \c CostMap::Value must be signed type.
63  ///
64  /// \author Peter Kovacs
65  template < typename Graph,
66             typename LowerMap = typename Graph::template EdgeMap<int>,
67             typename CapacityMap = typename Graph::template EdgeMap<int>,
68             typename CostMap = typename Graph::template EdgeMap<int>,
69             typename SupplyMap = typename Graph::template NodeMap<int> >
70  class MinCostFlow :
71    public NetworkSimplex< Graph, LowerMap, CapacityMap,
72                           CostMap, SupplyMap >
73  {
74    typedef NetworkSimplex< Graph, LowerMap, CapacityMap,
75                            CostMap, SupplyMap > MinCostFlowImpl;
76    typedef typename Graph::Node Node;
77    typedef typename SupplyMap::Value Supply;
78
79  public:
80
81    /// General constructor (with lower bounds).
82    MinCostFlow( const Graph &graph,
83                 const LowerMap &lower,
84                 const CapacityMap &capacity,
85                 const CostMap &cost,
86                 const SupplyMap &supply ) :
87      MinCostFlowImpl(graph, lower, capacity, cost, supply) {}
88
89    /// General constructor of the class (without lower bounds).
90    MinCostFlow( const Graph &graph,
91                 const CapacityMap &capacity,
92                 const CostMap &cost,
93                 const SupplyMap &supply ) :
94      MinCostFlowImpl(graph, capacity, cost, supply) {}
95
96    /// Simple constructor (with lower bounds).
97    MinCostFlow( const Graph &graph,
98                 const LowerMap &lower,
99                 const CapacityMap &capacity,
100                 const CostMap &cost,
101                 Node s, Node t,
102                 Supply flow_value ) :
103      MinCostFlowImpl( graph, lower, capacity, cost,
104                       s, t, flow_value ) {}
105
106    /// Simple constructor (without lower bounds).
107    MinCostFlow( const Graph &graph,
108                 const CapacityMap &capacity,
109                 const CostMap &cost,
110                 Node s, Node t,
111                 Supply flow_value ) :
112      MinCostFlowImpl( graph, capacity, cost,
113                       s, t, flow_value ) {}
114
115  }; //class MinCostFlow
116
117  ///@}
118
119} //namespace lemon
120
121#endif //LEMON_MIN_COST_FLOW_H
Note: See TracBrowser for help on using the repository browser.