1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/lemon/min_cost_flow.h Mon May 07 11:42:18 2007 +0000
1.3 @@ -0,0 +1,127 @@
1.4 +/* -*- C++ -*-
1.5 + *
1.6 + * This file is a part of LEMON, a generic C++ optimization library
1.7 + *
1.8 + * Copyright (C) 2003-2007
1.9 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
1.10 + * (Egervary Research Group on Combinatorial Optimization, EGRES).
1.11 + *
1.12 + * Permission to use, modify and distribute this software is granted
1.13 + * provided that this copyright notice appears in all copies. For
1.14 + * precise terms see the accompanying LICENSE file.
1.15 + *
1.16 + * This software is provided "AS IS" with no warranty of any kind,
1.17 + * express or implied, and with no claim as to its suitability for any
1.18 + * purpose.
1.19 + *
1.20 + */
1.21 +
1.22 +#ifndef LEMON_MIN_COST_FLOW_H
1.23 +#define LEMON_MIN_COST_FLOW_H
1.24 +
1.25 +/// \ingroup min_cost_flow
1.26 +///
1.27 +/// \file
1.28 +/// \brief An efficient algorithm for finding a minimum cost flow.
1.29 +
1.30 +#include <lemon/network_simplex.h>
1.31 +
1.32 +namespace lemon {
1.33 +
1.34 + /// \addtogroup min_cost_flow
1.35 + /// @{
1.36 +
1.37 + /// \brief An efficient algorithm for finding a minimum cost flow.
1.38 + ///
1.39 + /// \ref lemon::MinCostFlow "MinCostFlow" implements an efficient
1.40 + /// algorithm for finding a minimum cost flow.
1.41 + ///
1.42 + /// \note \ref lemon::MinCostFlow "MinCostFlow" is just an alias for
1.43 + /// \ref lemon::NetworkSimplex "NetworkSimplex", wich is the most
1.44 + /// efficient implementation for the minimum cost flow problem in the
1.45 + /// Lemon library according to our benchmark tests.
1.46 + ///
1.47 + /// \note There are three implementations for the minimum cost flow
1.48 + /// problem, that can be used in the same way.
1.49 + /// - \ref lemon::CapacityScaling "CapacityScaling"
1.50 + /// - \ref lemon::CycleCanceling "CycleCanceling"
1.51 + /// - \ref lemon::NetworkSimplex "NetworkSimplex"
1.52 + ///
1.53 + /// \param Graph The directed graph type the algorithm runs on.
1.54 + /// \param LowerMap The type of the lower bound map.
1.55 + /// \param CapacityMap The type of the capacity (upper bound) map.
1.56 + /// \param CostMap The type of the cost (length) map.
1.57 + /// \param SupplyMap The type of the supply map.
1.58 + ///
1.59 + /// \warning
1.60 + /// - Edge capacities and costs should be nonnegative integers.
1.61 + /// However \c CostMap::Value should be signed type.
1.62 + /// - Supply values should be integers.
1.63 + /// - \c LowerMap::Value must be convertible to
1.64 + /// \c CapacityMap::Value and \c CapacityMap::Value must be
1.65 + /// convertible to \c SupplyMap::Value.
1.66 + ///
1.67 + /// \author Peter Kovacs
1.68 +
1.69 +template < typename Graph,
1.70 + typename LowerMap = typename Graph::template EdgeMap<int>,
1.71 + typename CapacityMap = LowerMap,
1.72 + typename CostMap = typename Graph::template EdgeMap<int>,
1.73 + typename SupplyMap = typename Graph::template NodeMap
1.74 + <typename CapacityMap::Value> >
1.75 + class MinCostFlow :
1.76 + public NetworkSimplex< Graph,
1.77 + LowerMap,
1.78 + CapacityMap,
1.79 + CostMap,
1.80 + SupplyMap >
1.81 + {
1.82 + typedef NetworkSimplex< Graph, LowerMap, CapacityMap,
1.83 + CostMap, SupplyMap >
1.84 + MinCostFlowImpl;
1.85 + typedef typename Graph::Node Node;
1.86 + typedef typename SupplyMap::Value Supply;
1.87 +
1.88 + public:
1.89 +
1.90 + /// \brief General constructor of the class (with lower bounds).
1.91 + MinCostFlow( const Graph &_graph,
1.92 + const LowerMap &_lower,
1.93 + const CapacityMap &_capacity,
1.94 + const CostMap &_cost,
1.95 + const SupplyMap &_supply ) :
1.96 + MinCostFlowImpl(_graph, _lower, _capacity, _cost, _supply) {}
1.97 +
1.98 + /// \brief General constructor of the class (without lower bounds).
1.99 + MinCostFlow( const Graph &_graph,
1.100 + const CapacityMap &_capacity,
1.101 + const CostMap &_cost,
1.102 + const SupplyMap &_supply ) :
1.103 + MinCostFlowImpl(_graph, _capacity, _cost, _supply) {}
1.104 +
1.105 + /// \brief Simple constructor of the class (with lower bounds).
1.106 + MinCostFlow( const Graph &_graph,
1.107 + const LowerMap &_lower,
1.108 + const CapacityMap &_capacity,
1.109 + const CostMap &_cost,
1.110 + Node _s, Node _t,
1.111 + Supply _flow_value ) :
1.112 + MinCostFlowImpl( _graph, _lower, _capacity, _cost,
1.113 + _s, _t, _flow_value ) {}
1.114 +
1.115 + /// \brief Simple constructor of the class (without lower bounds).
1.116 + MinCostFlow( const Graph &_graph,
1.117 + const CapacityMap &_capacity,
1.118 + const CostMap &_cost,
1.119 + Node _s, Node _t,
1.120 + Supply _flow_value ) :
1.121 + MinCostFlowImpl( _graph, _capacity, _cost,
1.122 + _s, _t, _flow_value ) {}
1.123 +
1.124 + }; //class MinCostFlow
1.125 +
1.126 + ///@}
1.127 +
1.128 +} //namespace lemon
1.129 +
1.130 +#endif //LEMON_MIN_COST_FLOW_H