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

/* -*- C++ -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#ifndef LEMON_MIN_COST_FLOW_H
#define LEMON_MIN_COST_FLOW_H

/// \ingroup min_cost_flow
///
/// \file
/// \brief An efficient algorithm for finding a minimum cost flow.

#include <lemon/network_simplex.h>

namespace lemon {

  /// \addtogroup min_cost_flow
  /// @{

  /// \brief An efficient algorithm for finding a minimum cost flow.
  ///
  /// \ref MinCostFlow provides an efficient algorithm for finding
  /// a minimum cost flow.
  ///
  /// This class is just an alias for \ref NetworkSimplex,
  /// which is the most efficient algorithm for the minimum cost
  /// flow problem in LEMON according to our benchmark tests.
  /// For the detailed documentation of this class see
  /// \ref NetworkSimplex.
  ///
  /// There are four implementations for the minimum cost flow problem,
  /// which can be used exactly the same way except for the fact that
  /// \ref CycleCanceling does not provide dual solution (node
  /// potentials) since it is a pure primal method.
  /// - \ref CapacityScaling The capacity scaling algorithm.
  /// - \ref CostScaling The cost scaling algorithm.
  /// - \ref CycleCanceling A cycle-canceling algorithm.
  /// - \ref NetworkSimplex The network simplex algorithm.
  ///
  /// \tparam Graph The directed graph type the algorithm runs on.
  /// \tparam LowerMap The type of the lower bound map.
  /// \tparam CapacityMap The type of the capacity (upper bound) map.
  /// \tparam CostMap The type of the cost (length) map.
  /// \tparam SupplyMap The type of the supply map.
  ///
  /// \warning
  /// - Edge capacities and costs should be \e non-negative \e integers.
  /// - Supply values should be \e signed \e integers.
  /// - \c LowerMap::Value must be convertible to \c CapacityMap::Value.
  /// - \c CapacityMap::Value and \c SupplyMap::Value must be
  ///   convertible to each other.
  /// - All value types must be convertible to \c CostMap::Value, which
  ///   must be signed type.
  ///
  /// \author Peter Kovacs

  template < typename Graph,
             typename LowerMap = typename Graph::template EdgeMap<int>,
             typename CapacityMap = LowerMap,
             typename CostMap = typename Graph::template EdgeMap<int>,
             typename SupplyMap = typename Graph::template NodeMap
                                  <typename CapacityMap::Value> >
  class MinCostFlow :
    public NetworkSimplex< Graph, LowerMap, CapacityMap,
                           CostMap, SupplyMap >
  {
    typedef NetworkSimplex< Graph, LowerMap, CapacityMap,
                            CostMap, SupplyMap > MinCostFlowImpl;
    typedef typename Graph::Node Node;
    typedef typename SupplyMap::Value Supply;

  public:

    /// General constructor of the class (with lower bounds).
    MinCostFlow( const Graph &graph,
                 const LowerMap &lower,
                 const CapacityMap &capacity,
                 const CostMap &cost,
                 const SupplyMap &supply ) :
      MinCostFlowImpl(graph, lower, capacity, cost, supply) {}

    /// General constructor of the class (without lower bounds).
    MinCostFlow( const Graph &graph,
                 const CapacityMap &capacity,
                 const CostMap &cost,
                 const SupplyMap &supply ) :
      MinCostFlowImpl(graph, capacity, cost, supply) {}

    /// Simple constructor of the class (with lower bounds).
    MinCostFlow( const Graph &graph,
                 const LowerMap &lower,
                 const CapacityMap &capacity,
                 const CostMap &cost,
                 Node s, Node t,
                 Supply flow_value ) :
      MinCostFlowImpl( graph, lower, capacity, cost,
                       s, t, flow_value ) {}

    /// Simple constructor of the class (without lower bounds).
    MinCostFlow( const Graph &graph,
                 const CapacityMap &capacity,
                 const CostMap &cost,
                 Node s, Node t,
                 Supply flow_value ) :
      MinCostFlowImpl( graph, capacity, cost,
                       s, t, flow_value ) {}

  }; //class MinCostFlow

  ///@}

} //namespace lemon

#endif //LEMON_MIN_COST_FLOW_H