1.1 --- a/lemon/min_cost_flow.h Sun Jan 13 10:26:55 2008 +0000
1.2 +++ b/lemon/min_cost_flow.h Sun Jan 13 10:32:14 2008 +0000
1.3 @@ -33,19 +33,22 @@
1.4
1.5 /// \brief An efficient algorithm for finding a minimum cost flow.
1.6 ///
1.7 - /// \ref lemon::MinCostFlow "MinCostFlow" implements an efficient
1.8 - /// algorithm for finding a minimum cost flow.
1.9 + /// \ref MinCostFlow provides an efficient algorithm for finding
1.10 + /// a minimum cost flow.
1.11 ///
1.12 - /// \note \ref lemon::MinCostFlow "MinCostFlow" is just an alias for
1.13 - /// \ref lemon::NetworkSimplex "NetworkSimplex", wich is the most
1.14 - /// efficient implementation for the minimum cost flow problem in the
1.15 - /// LEMON library according to our benchmark tests.
1.16 + /// \note \ref MinCostFlow is just an alias for \ref NetworkSimplex,
1.17 + /// which is the most efficient implementation for the minimum cost
1.18 + /// flow problem in the LEMON library according to our benchmark
1.19 + /// tests.
1.20 ///
1.21 /// \note There are three implementations for the minimum cost flow
1.22 - /// problem, that can be used in the same way.
1.23 - /// - \ref lemon::CapacityScaling "CapacityScaling"
1.24 - /// - \ref lemon::CycleCanceling "CycleCanceling"
1.25 - /// - \ref lemon::NetworkSimplex "NetworkSimplex"
1.26 + /// problem, that can be used exactly the same way.
1.27 + /// - \ref CapacityScaling
1.28 + /// - \ref CycleCanceling
1.29 + /// - \ref NetworkSimplex
1.30 + ///
1.31 + /// \note For the detailed documentation of this class see
1.32 + /// \ref NetworkSimplex.
1.33 ///
1.34 /// \param Graph The directed graph type the algorithm runs on.
1.35 /// \param LowerMap The type of the lower bound map.
1.36 @@ -54,12 +57,12 @@
1.37 /// \param SupplyMap The type of the supply map.
1.38 ///
1.39 /// \warning
1.40 - /// - Edge capacities and costs should be nonnegative integers.
1.41 - /// However \c CostMap::Value should be signed type.
1.42 + /// - Edge capacities and costs should be non-negative integers.
1.43 + /// However \c CostMap::Value should be signed type.
1.44 /// - Supply values should be signed integers.
1.45 /// - \c LowerMap::Value must be convertible to
1.46 - /// \c CapacityMap::Value and \c CapacityMap::Value must be
1.47 - /// convertible to \c SupplyMap::Value.
1.48 + /// \c CapacityMap::Value and \c CapacityMap::Value must be
1.49 + /// convertible to \c SupplyMap::Value.
1.50 ///
1.51 /// \author Peter Kovacs
1.52
1.53 @@ -70,53 +73,49 @@
1.54 typename SupplyMap = typename Graph::template NodeMap
1.55 <typename CapacityMap::Value> >
1.56 class MinCostFlow :
1.57 - public NetworkSimplex< Graph,
1.58 - LowerMap,
1.59 - CapacityMap,
1.60 - CostMap,
1.61 - SupplyMap >
1.62 + public NetworkSimplex< Graph, LowerMap, CapacityMap,
1.63 + CostMap, SupplyMap >
1.64 {
1.65 typedef NetworkSimplex< Graph, LowerMap, CapacityMap,
1.66 - CostMap, SupplyMap >
1.67 - MinCostFlowImpl;
1.68 + CostMap, SupplyMap > MinCostFlowImpl;
1.69 typedef typename Graph::Node Node;
1.70 typedef typename SupplyMap::Value Supply;
1.71
1.72 public:
1.73
1.74 - /// \brief General constructor of the class (with lower bounds).
1.75 - MinCostFlow( const Graph &_graph,
1.76 - const LowerMap &_lower,
1.77 - const CapacityMap &_capacity,
1.78 - const CostMap &_cost,
1.79 - const SupplyMap &_supply ) :
1.80 - MinCostFlowImpl(_graph, _lower, _capacity, _cost, _supply) {}
1.81 + /// General constructor of the class (with lower bounds).
1.82 + MinCostFlow( const Graph &graph,
1.83 + const LowerMap &lower,
1.84 + const CapacityMap &capacity,
1.85 + const CostMap &cost,
1.86 + const SupplyMap &supply ) :
1.87 + MinCostFlowImpl(graph, lower, capacity, cost, supply) {}
1.88
1.89 - /// \brief General constructor of the class (without lower bounds).
1.90 - MinCostFlow( const Graph &_graph,
1.91 - const CapacityMap &_capacity,
1.92 - const CostMap &_cost,
1.93 - const SupplyMap &_supply ) :
1.94 - MinCostFlowImpl(_graph, _capacity, _cost, _supply) {}
1.95 + /// General constructor of the class (without lower bounds).
1.96 + MinCostFlow( const Graph &graph,
1.97 + const CapacityMap &capacity,
1.98 + const CostMap &_ost,
1.99 + const SupplyMap &supply ) :
1.100 + MinCostFlowImpl(graph, capacity, cost, supply) {}
1.101
1.102 - /// \brief Simple constructor of the class (with lower bounds).
1.103 - MinCostFlow( const Graph &_graph,
1.104 - const LowerMap &_lower,
1.105 - const CapacityMap &_capacity,
1.106 - const CostMap &_cost,
1.107 - Node _s, Node _t,
1.108 - Supply _flow_value ) :
1.109 - MinCostFlowImpl( _graph, _lower, _capacity, _cost,
1.110 - _s, _t, _flow_value ) {}
1.111 + /// Simple constructor of the class (with lower bounds).
1.112 + MinCostFlow( const Graph &graph,
1.113 + const LowerMap &lower,
1.114 + const CapacityMap &capacity,
1.115 + const CostMap &_ost,
1.116 + Node s, Node t,
1.117 + Supply flow_value ) :
1.118 + MinCostFlowImpl( graph, lower, capacity, cost,
1.119 + s, t, flow_value ) {}
1.120
1.121 - /// \brief Simple constructor of the class (without lower bounds).
1.122 - MinCostFlow( const Graph &_graph,
1.123 - const CapacityMap &_capacity,
1.124 - const CostMap &_cost,
1.125 - Node _s, Node _t,
1.126 - Supply _flow_value ) :
1.127 - MinCostFlowImpl( _graph, _capacity, _cost,
1.128 - _s, _t, _flow_value ) {}
1.129 + /// Simple constructor of the class (without lower bounds).
1.130 + MinCostFlow( const Graph &graph,
1.131 + const CapacityMap &capacity,
1.132 + const CostMap &cost,
1.133 + Node s, Node t,
1.134 + Supply flow_value ) :
1.135 + MinCostFlowImpl( graph, capacity, cost,
1.136 + s, t, flow_value ) {}
1.137
1.138 }; //class MinCostFlow
1.139