COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/min_cost_flow.h @ 2581:054566ac0934

Last change on this file since 2581:054566ac0934 was 2581:054566ac0934, checked in by Peter Kovacs, 11 years ago

Query improvements in the min cost flow algorithms.

  • External flow and potential maps can be used.
  • New query functions: flow() and potential().
  • CycleCanceling? also provides dual solution (node potentials).
  • Doc improvements.
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  /// 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 The capacity scaling algorithm.
48  /// - \ref CostScaling The cost scaling algorithm.
49  /// - \ref CycleCanceling A cycle-canceling algorithm.
50  /// - \ref NetworkSimplex The network simplex algorithm.
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
66  template < typename Graph,
67             typename LowerMap = typename Graph::template EdgeMap<int>,
68             typename CapacityMap = typename Graph::template EdgeMap<int>,
69             typename CostMap = typename Graph::template EdgeMap<int>,
70             typename SupplyMap = typename Graph::template NodeMap<int> >
71  class MinCostFlow :
72    public NetworkSimplex< Graph, LowerMap, CapacityMap,
73                           CostMap, SupplyMap >
74  {
75    typedef NetworkSimplex< Graph, LowerMap, CapacityMap,
76                            CostMap, SupplyMap > MinCostFlowImpl;
77    typedef typename Graph::Node Node;
78    typedef typename SupplyMap::Value Supply;
79
80  public:
81
82    /// General constructor (with lower bounds).
83    MinCostFlow( const Graph &graph,
84                 const LowerMap &lower,
85                 const CapacityMap &capacity,
86                 const CostMap &cost,
87                 const SupplyMap &supply ) :
88      MinCostFlowImpl(graph, lower, capacity, cost, supply) {}
89
90    /// General constructor of the class (without lower bounds).
91    MinCostFlow( const Graph &graph,
92                 const CapacityMap &capacity,
93                 const CostMap &cost,
94                 const SupplyMap &supply ) :
95      MinCostFlowImpl(graph, capacity, cost, supply) {}
96
97    /// Simple constructor (with lower bounds).
98    MinCostFlow( const Graph &graph,
99                 const LowerMap &lower,
100                 const CapacityMap &capacity,
101                 const CostMap &cost,
102                 Node s, Node t,
103                 Supply flow_value ) :
104      MinCostFlowImpl( graph, lower, capacity, cost,
105                       s, t, flow_value ) {}
106
107    /// Simple constructor (without lower bounds).
108    MinCostFlow( const Graph &graph,
109                 const CapacityMap &capacity,
110                 const CostMap &cost,
111                 Node s, Node t,
112                 Supply flow_value ) :
113      MinCostFlowImpl( graph, capacity, cost,
114                       s, t, flow_value ) {}
115
116  }; //class MinCostFlow
117
118  ///@}
119
120} //namespace lemon
121
122#endif //LEMON_MIN_COST_FLOW_H
Note: See TracBrowser for help on using the repository browser.