diff --git a/lemon/network_simplex.h b/lemon/network_simplex.h --- a/lemon/network_simplex.h +++ b/lemon/network_simplex.h @@ -22,7 +22,7 @@ /// \ingroup min_cost_flow /// /// \file -/// \brief Network simplex algorithm for finding a minimum cost flow. +/// \brief Network Simplex algorithm for finding a minimum cost flow. #include #include @@ -36,80 +36,89 @@ /// \addtogroup min_cost_flow /// @{ - /// \brief Implementation of the primal network simplex algorithm + /// \brief Implementation of the primal Network Simplex algorithm /// for finding a \ref min_cost_flow "minimum cost flow". /// - /// \ref NetworkSimplex implements the primal network simplex algorithm + /// \ref NetworkSimplex implements the primal Network Simplex algorithm /// for finding a \ref min_cost_flow "minimum cost flow". /// - /// \tparam Digraph The digraph 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. + /// \tparam GR The digraph type the algorithm runs on. + /// \tparam V The value type used in the algorithm. + /// By default it is \c int. /// - /// \warning - /// - Arc capacities and costs should be \e non-negative \e integers. - /// - Supply values should be \e signed \e integers. - /// - The value types of the maps should be convertible to each other. - /// - \c CostMap::Value must be signed type. + /// \warning \c V must be a signed integer type. /// - /// \note \ref NetworkSimplex provides five different pivot rule - /// implementations that significantly affect the efficiency of the - /// algorithm. - /// By default "Block Search" pivot rule is used, which proved to be - /// by far the most efficient according to our benchmark tests. - /// However another pivot rule can be selected using \ref run() - /// function with the proper parameter. -#ifdef DOXYGEN - template < typename Digraph, - typename LowerMap, - typename CapacityMap, - typename CostMap, - typename SupplyMap > - -#else - template < typename Digraph, - typename LowerMap = typename Digraph::template ArcMap, - typename CapacityMap = typename Digraph::template ArcMap, - typename CostMap = typename Digraph::template ArcMap, - typename SupplyMap = typename Digraph::template NodeMap > -#endif + /// \note %NetworkSimplex provides five different pivot rule + /// implementations. For more information see \ref PivotRule. + template class NetworkSimplex { - TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); + public: - typedef typename CapacityMap::Value Capacity; - typedef typename CostMap::Value Cost; - typedef typename SupplyMap::Value Supply; + /// The value type of the algorithm + typedef V Value; + /// The type of the flow map + typedef typename GR::template ArcMap FlowMap; + /// The type of the potential map + typedef typename GR::template NodeMap PotentialMap; + + public: + + /// \brief Enum type for selecting the pivot rule. + /// + /// Enum type for selecting the pivot rule for the \ref run() + /// function. + /// + /// \ref NetworkSimplex provides five different pivot rule + /// implementations that significantly affect the running time + /// of the algorithm. + /// By default \ref BLOCK_SEARCH "Block Search" is used, which + /// proved to be the most efficient and the most robust on various + /// test inputs according to our benchmark tests. + /// However another pivot rule can be selected using the \ref run() + /// function with the proper parameter. + enum PivotRule { + + /// The First Eligible pivot rule. + /// The next eligible arc is selected in a wraparound fashion + /// in every iteration. + FIRST_ELIGIBLE, + + /// The Best Eligible pivot rule. + /// The best eligible arc is selected in every iteration. + BEST_ELIGIBLE, + + /// The Block Search pivot rule. + /// A specified number of arcs are examined in every iteration + /// in a wraparound fashion and the best eligible arc is selected + /// from this block. + BLOCK_SEARCH, + + /// The Candidate List pivot rule. + /// In a major iteration a candidate list is built from eligible arcs + /// in a wraparound fashion and in the following minor iterations + /// the best eligible arc is selected from this list. + CANDIDATE_LIST, + + /// The Altering Candidate List pivot rule. + /// It is a modified version of the Candidate List method. + /// It keeps only the several best eligible arcs from the former + /// candidate list and extends this list in every iteration. + ALTERING_LIST + }; + + private: + + TEMPLATE_DIGRAPH_TYPEDEFS(GR); + + typedef typename GR::template ArcMap ValueArcMap; + typedef typename GR::template NodeMap ValueNodeMap; typedef std::vector ArcVector; typedef std::vector NodeVector; typedef std::vector IntVector; typedef std::vector BoolVector; - typedef std::vector CapacityVector; - typedef std::vector CostVector; - typedef std::vector SupplyVector; - - public: - - /// The type of the flow map - typedef typename Digraph::template ArcMap FlowMap; - /// The type of the potential map - typedef typename Digraph::template NodeMap PotentialMap; - - public: - - /// Enum type for selecting the pivot rule used by \ref run() - enum PivotRuleEnum { - FIRST_ELIGIBLE_PIVOT, - BEST_ELIGIBLE_PIVOT, - BLOCK_SEARCH_PIVOT, - CANDIDATE_LIST_PIVOT, - ALTERING_LIST_PIVOT - }; - - private: + typedef std::vector ValueVector; // State constants for arcs enum ArcStateEnum { @@ -120,15 +129,19 @@ private: - // References for the original data - const Digraph &_graph; - const LowerMap *_orig_lower; - const CapacityMap &_orig_cap; - const CostMap &_orig_cost; - const SupplyMap *_orig_supply; - Node _orig_source; - Node _orig_target; - Capacity _orig_flow_value; + // Data related to the underlying digraph + const GR &_graph; + int _node_num; + int _arc_num; + + // Parameters of the problem + ValueArcMap *_plower; + ValueArcMap *_pupper; + ValueArcMap *_pcost; + ValueNodeMap *_psupply; + bool _pstsup; + Node _psource, _ptarget; + Value _pstflow; // Result maps FlowMap *_flow_map; @@ -136,22 +149,18 @@ bool _local_flow; bool _local_potential; - // The number of nodes and arcs in the original graph - int _node_num; - int _arc_num; - - // Data structures for storing the graph + // Data structures for storing the digraph IntNodeMap _node_id; ArcVector _arc_ref; IntVector _source; IntVector _target; - // Node and arc maps - CapacityVector _cap; - CostVector _cost; - CostVector _supply; - CapacityVector _flow; - CostVector _pi; + // Node and arc data + ValueVector _cap; + ValueVector _cost; + ValueVector _supply; + ValueVector _flow; + ValueVector _pi; // Data for storing the spanning tree structure IntVector _parent; @@ -169,17 +178,11 @@ int in_arc, join, u_in, v_in, u_out, v_out; int first, second, right, last; int stem, par_stem, new_stem; - Capacity delta; + Value delta; private: - /// \brief Implementation of the "First Eligible" pivot rule for the - /// \ref NetworkSimplex "network simplex" algorithm. - /// - /// This class implements the "First Eligible" pivot rule - /// for the \ref NetworkSimplex "network simplex" algorithm. - /// - /// For more information see \ref NetworkSimplex::run(). + // Implementation of the First Eligible pivot rule class FirstEligiblePivotRule { private: @@ -187,9 +190,9 @@ // References to the NetworkSimplex class const IntVector &_source; const IntVector &_target; - const CostVector &_cost; + const ValueVector &_cost; const IntVector &_state; - const CostVector &_pi; + const ValueVector &_pi; int &_in_arc; int _arc_num; @@ -198,16 +201,16 @@ public: - /// Constructor + // Constructor FirstEligiblePivotRule(NetworkSimplex &ns) : _source(ns._source), _target(ns._target), _cost(ns._cost), _state(ns._state), _pi(ns._pi), _in_arc(ns.in_arc), _arc_num(ns._arc_num), _next_arc(0) {} - /// Find next entering arc + // Find next entering arc bool findEnteringArc() { - Cost c; + Value c; for (int e = _next_arc; e < _arc_num; ++e) { c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); if (c < 0) { @@ -230,13 +233,7 @@ }; //class FirstEligiblePivotRule - /// \brief Implementation of the "Best Eligible" pivot rule for the - /// \ref NetworkSimplex "network simplex" algorithm. - /// - /// This class implements the "Best Eligible" pivot rule - /// for the \ref NetworkSimplex "network simplex" algorithm. - /// - /// For more information see \ref NetworkSimplex::run(). + // Implementation of the Best Eligible pivot rule class BestEligiblePivotRule { private: @@ -244,24 +241,24 @@ // References to the NetworkSimplex class const IntVector &_source; const IntVector &_target; - const CostVector &_cost; + const ValueVector &_cost; const IntVector &_state; - const CostVector &_pi; + const ValueVector &_pi; int &_in_arc; int _arc_num; public: - /// Constructor + // Constructor BestEligiblePivotRule(NetworkSimplex &ns) : _source(ns._source), _target(ns._target), _cost(ns._cost), _state(ns._state), _pi(ns._pi), _in_arc(ns.in_arc), _arc_num(ns._arc_num) {} - /// Find next entering arc + // Find next entering arc bool findEnteringArc() { - Cost c, min = 0; + Value c, min = 0; for (int e = 0; e < _arc_num; ++e) { c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); if (c < min) { @@ -275,13 +272,7 @@ }; //class BestEligiblePivotRule - /// \brief Implementation of the "Block Search" pivot rule for the - /// \ref NetworkSimplex "network simplex" algorithm. - /// - /// This class implements the "Block Search" pivot rule - /// for the \ref NetworkSimplex "network simplex" algorithm. - /// - /// For more information see \ref NetworkSimplex::run(). + // Implementation of the Block Search pivot rule class BlockSearchPivotRule { private: @@ -289,9 +280,9 @@ // References to the NetworkSimplex class const IntVector &_source; const IntVector &_target; - const CostVector &_cost; + const ValueVector &_cost; const IntVector &_state; - const CostVector &_pi; + const ValueVector &_pi; int &_in_arc; int _arc_num; @@ -301,7 +292,7 @@ public: - /// Constructor + // Constructor BlockSearchPivotRule(NetworkSimplex &ns) : _source(ns._source), _target(ns._target), _cost(ns._cost), _state(ns._state), _pi(ns._pi), @@ -315,9 +306,9 @@ MIN_BLOCK_SIZE ); } - /// Find next entering arc + // Find next entering arc bool findEnteringArc() { - Cost c, min = 0; + Value c, min = 0; int cnt = _block_size; int e, min_arc = _next_arc; for (e = _next_arc; e < _arc_num; ++e) { @@ -353,13 +344,7 @@ }; //class BlockSearchPivotRule - /// \brief Implementation of the "Candidate List" pivot rule for the - /// \ref NetworkSimplex "network simplex" algorithm. - /// - /// This class implements the "Candidate List" pivot rule - /// for the \ref NetworkSimplex "network simplex" algorithm. - /// - /// For more information see \ref NetworkSimplex::run(). + // Implementation of the Candidate List pivot rule class CandidateListPivotRule { private: @@ -367,9 +352,9 @@ // References to the NetworkSimplex class const IntVector &_source; const IntVector &_target; - const CostVector &_cost; + const ValueVector &_cost; const IntVector &_state; - const CostVector &_pi; + const ValueVector &_pi; int &_in_arc; int _arc_num; @@ -403,7 +388,7 @@ /// Find next entering arc bool findEnteringArc() { - Cost min, c; + Value min, c; int e, min_arc = _next_arc; if (_curr_length > 0 && _minor_count < _minor_limit) { // Minor iteration: select the best eligible arc from the @@ -464,13 +449,7 @@ }; //class CandidateListPivotRule - /// \brief Implementation of the "Altering Candidate List" pivot rule - /// for the \ref NetworkSimplex "network simplex" algorithm. - /// - /// This class implements the "Altering Candidate List" pivot rule - /// for the \ref NetworkSimplex "network simplex" algorithm. - /// - /// For more information see \ref NetworkSimplex::run(). + // Implementation of the Altering Candidate List pivot rule class AlteringListPivotRule { private: @@ -478,9 +457,9 @@ // References to the NetworkSimplex class const IntVector &_source; const IntVector &_target; - const CostVector &_cost; + const ValueVector &_cost; const IntVector &_state; - const CostVector &_pi; + const ValueVector &_pi; int &_in_arc; int _arc_num; @@ -488,15 +467,15 @@ int _block_size, _head_length, _curr_length; int _next_arc; IntVector _candidates; - CostVector _cand_cost; + ValueVector _cand_cost; // Functor class to compare arcs during sort of the candidate list class SortFunc { private: - const CostVector &_map; + const ValueVector &_map; public: - SortFunc(const CostVector &map) : _map(map) {} + SortFunc(const ValueVector &map) : _map(map) {} bool operator()(int left, int right) { return _map[left] > _map[right]; } @@ -506,7 +485,7 @@ public: - /// Constructor + // Constructor AlteringListPivotRule(NetworkSimplex &ns) : _source(ns._source), _target(ns._target), _cost(ns._cost), _state(ns._state), _pi(ns._pi), @@ -527,7 +506,7 @@ _curr_length = 0; } - /// Find next entering arc + // Find next entering arc bool findEnteringArc() { // Check the current candidate list int e; @@ -592,95 +571,23 @@ public: - /// \brief General constructor (with lower bounds). + /// \brief Constructor. /// - /// General constructor (with lower bounds). + /// Constructor. /// /// \param graph The digraph the algorithm runs on. - /// \param lower The lower bounds of the arcs. - /// \param capacity The capacities (upper bounds) of the arcs. - /// \param cost The cost (length) values of the arcs. - /// \param supply The supply values of the nodes (signed). - NetworkSimplex( const Digraph &graph, - const LowerMap &lower, - const CapacityMap &capacity, - const CostMap &cost, - const SupplyMap &supply ) : - _graph(graph), _orig_lower(&lower), _orig_cap(capacity), - _orig_cost(cost), _orig_supply(&supply), + NetworkSimplex(const GR& graph) : + _graph(graph), + _plower(NULL), _pupper(NULL), _pcost(NULL), + _psupply(NULL), _pstsup(false), _flow_map(NULL), _potential_map(NULL), _local_flow(false), _local_potential(false), _node_id(graph) - {} - - /// \brief General constructor (without lower bounds). - /// - /// General constructor (without lower bounds). - /// - /// \param graph The digraph the algorithm runs on. - /// \param capacity The capacities (upper bounds) of the arcs. - /// \param cost The cost (length) values of the arcs. - /// \param supply The supply values of the nodes (signed). - NetworkSimplex( const Digraph &graph, - const CapacityMap &capacity, - const CostMap &cost, - const SupplyMap &supply ) : - _graph(graph), _orig_lower(NULL), _orig_cap(capacity), - _orig_cost(cost), _orig_supply(&supply), - _flow_map(NULL), _potential_map(NULL), - _local_flow(false), _local_potential(false), - _node_id(graph) - {} - - /// \brief Simple constructor (with lower bounds). - /// - /// Simple constructor (with lower bounds). - /// - /// \param graph The digraph the algorithm runs on. - /// \param lower The lower bounds of the arcs. - /// \param capacity The capacities (upper bounds) of the arcs. - /// \param cost The cost (length) values of the arcs. - /// \param s The source node. - /// \param t The target node. - /// \param flow_value The required amount of flow from node \c s - /// to node \c t (i.e. the supply of \c s and the demand of \c t). - NetworkSimplex( const Digraph &graph, - const LowerMap &lower, - const CapacityMap &capacity, - const CostMap &cost, - Node s, Node t, - Capacity flow_value ) : - _graph(graph), _orig_lower(&lower), _orig_cap(capacity), - _orig_cost(cost), _orig_supply(NULL), - _orig_source(s), _orig_target(t), _orig_flow_value(flow_value), - _flow_map(NULL), _potential_map(NULL), - _local_flow(false), _local_potential(false), - _node_id(graph) - {} - - /// \brief Simple constructor (without lower bounds). - /// - /// Simple constructor (without lower bounds). - /// - /// \param graph The digraph the algorithm runs on. - /// \param capacity The capacities (upper bounds) of the arcs. - /// \param cost The cost (length) values of the arcs. - /// \param s The source node. - /// \param t The target node. - /// \param flow_value The required amount of flow from node \c s - /// to node \c t (i.e. the supply of \c s and the demand of \c t). - NetworkSimplex( const Digraph &graph, - const CapacityMap &capacity, - const CostMap &cost, - Node s, Node t, - Capacity flow_value ) : - _graph(graph), _orig_lower(NULL), _orig_cap(capacity), - _orig_cost(cost), _orig_supply(NULL), - _orig_source(s), _orig_target(t), _orig_flow_value(flow_value), - _flow_map(NULL), _potential_map(NULL), - _local_flow(false), _local_potential(false), - _node_id(graph) - {} + { + LEMON_ASSERT(std::numeric_limits::is_integer && + std::numeric_limits::is_signed, + "The value type of NetworkSimplex must be a signed integer"); + } /// Destructor. ~NetworkSimplex() { @@ -688,12 +595,165 @@ if (_local_potential) delete _potential_map; } + /// \brief Set the lower bounds on the arcs. + /// + /// This function sets the lower bounds on the arcs. + /// If neither this function nor \ref boundMaps() is used before + /// calling \ref run(), the lower bounds will be set to zero + /// on all arcs. + /// + /// \param map An arc map storing the lower bounds. + /// Its \c Value type must be convertible to the \c Value type + /// of the algorithm. + /// + /// \return (*this) + template + NetworkSimplex& lowerMap(const LOWER& map) { + delete _plower; + _plower = new ValueArcMap(_graph); + for (ArcIt a(_graph); a != INVALID; ++a) { + (*_plower)[a] = map[a]; + } + return *this; + } + + /// \brief Set the upper bounds (capacities) on the arcs. + /// + /// This function sets the upper bounds (capacities) on the arcs. + /// If none of the functions \ref upperMap(), \ref capacityMap() + /// and \ref boundMaps() is used before calling \ref run(), + /// the upper bounds (capacities) will be set to + /// \c std::numeric_limits::max() on all arcs. + /// + /// \param map An arc map storing the upper bounds. + /// Its \c Value type must be convertible to the \c Value type + /// of the algorithm. + /// + /// \return (*this) + template + NetworkSimplex& upperMap(const UPPER& map) { + delete _pupper; + _pupper = new ValueArcMap(_graph); + for (ArcIt a(_graph); a != INVALID; ++a) { + (*_pupper)[a] = map[a]; + } + return *this; + } + + /// \brief Set the upper bounds (capacities) on the arcs. + /// + /// This function sets the upper bounds (capacities) on the arcs. + /// It is just an alias for \ref upperMap(). + /// + /// \return (*this) + template + NetworkSimplex& capacityMap(const CAP& map) { + return upperMap(map); + } + + /// \brief Set the lower and upper bounds on the arcs. + /// + /// This function sets the lower and upper bounds on the arcs. + /// If neither this function nor \ref lowerMap() is used before + /// calling \ref run(), the lower bounds will be set to zero + /// on all arcs. + /// If none of the functions \ref upperMap(), \ref capacityMap() + /// and \ref boundMaps() is used before calling \ref run(), + /// the upper bounds (capacities) will be set to + /// \c std::numeric_limits::max() on all arcs. + /// + /// \param lower An arc map storing the lower bounds. + /// \param upper An arc map storing the upper bounds. + /// + /// The \c Value type of the maps must be convertible to the + /// \c Value type of the algorithm. + /// + /// \note This function is just a shortcut of calling \ref lowerMap() + /// and \ref upperMap() separately. + /// + /// \return (*this) + template + NetworkSimplex& boundMaps(const LOWER& lower, const UPPER& upper) { + return lowerMap(lower).upperMap(upper); + } + + /// \brief Set the costs of the arcs. + /// + /// This function sets the costs of the arcs. + /// If it is not used before calling \ref run(), the costs + /// will be set to \c 1 on all arcs. + /// + /// \param map An arc map storing the costs. + /// Its \c Value type must be convertible to the \c Value type + /// of the algorithm. + /// + /// \return (*this) + template + NetworkSimplex& costMap(const COST& map) { + delete _pcost; + _pcost = new ValueArcMap(_graph); + for (ArcIt a(_graph); a != INVALID; ++a) { + (*_pcost)[a] = map[a]; + } + return *this; + } + + /// \brief Set the supply values of the nodes. + /// + /// This function sets the supply values of the nodes. + /// If neither this function nor \ref stSupply() is used before + /// calling \ref run(), the supply of each node will be set to zero. + /// (It makes sense only if non-zero lower bounds are given.) + /// + /// \param map A node map storing the supply values. + /// Its \c Value type must be convertible to the \c Value type + /// of the algorithm. + /// + /// \return (*this) + template + NetworkSimplex& supplyMap(const SUP& map) { + delete _psupply; + _pstsup = false; + _psupply = new ValueNodeMap(_graph); + for (NodeIt n(_graph); n != INVALID; ++n) { + (*_psupply)[n] = map[n]; + } + return *this; + } + + /// \brief Set single source and target nodes and a supply value. + /// + /// This function sets a single source node and a single target node + /// and the required flow value. + /// If neither this function nor \ref supplyMap() is used before + /// calling \ref run(), the supply of each node will be set to zero. + /// (It makes sense only if non-zero lower bounds are given.) + /// + /// \param s The source node. + /// \param t The target node. + /// \param k The required amount of flow from node \c s to node \c t + /// (i.e. the supply of \c s and the demand of \c t). + /// + /// \return (*this) + NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) { + delete _psupply; + _psupply = NULL; + _pstsup = true; + _psource = s; + _ptarget = t; + _pstflow = k; + return *this; + } + /// \brief Set the flow map. /// /// This function sets the flow map. + /// If it is not used before calling \ref run(), an instance will + /// be allocated automatically. The destructor deallocates this + /// automatically allocated map, of course. /// /// \return (*this) - NetworkSimplex& flowMap(FlowMap &map) { + NetworkSimplex& flowMap(FlowMap& map) { if (_local_flow) { delete _flow_map; _local_flow = false; @@ -704,10 +764,14 @@ /// \brief Set the potential map. /// - /// This function sets the potential map. + /// This function sets the potential map, which is used for storing + /// the dual solution. + /// If it is not used before calling \ref run(), an instance will + /// be allocated automatically. The destructor deallocates this + /// automatically allocated map, of course. /// /// \return (*this) - NetworkSimplex& potentialMap(PotentialMap &map) { + NetworkSimplex& potentialMap(PotentialMap& map) { if (_local_potential) { delete _potential_map; _local_potential = false; @@ -716,47 +780,29 @@ return *this; } - /// \name Execution control - /// The algorithm can be executed using the - /// \ref lemon::NetworkSimplex::run() "run()" function. + /// \name Execution Control + /// The algorithm can be executed using \ref run(). + /// @{ /// \brief Run the algorithm. /// /// This function runs the algorithm. + /// The paramters can be specified using \ref lowerMap(), + /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(), + /// \ref costMap(), \ref supplyMap() and \ref stSupply() + /// functions. For example, + /// \code + /// NetworkSimplex ns(graph); + /// ns.boundMaps(lower, upper).costMap(cost) + /// .supplyMap(sup).run(); + /// \endcode /// - /// \param pivot_rule The pivot rule that is used during the - /// algorithm. - /// - /// The available pivot rules: - /// - /// - FIRST_ELIGIBLE_PIVOT The next eligible arc is selected in - /// a wraparound fashion in every iteration - /// (\ref FirstEligiblePivotRule). - /// - /// - BEST_ELIGIBLE_PIVOT The best eligible arc is selected in - /// every iteration (\ref BestEligiblePivotRule). - /// - /// - BLOCK_SEARCH_PIVOT A specified number of arcs are examined in - /// every iteration in a wraparound fashion and the best eligible - /// arc is selected from this block (\ref BlockSearchPivotRule). - /// - /// - CANDIDATE_LIST_PIVOT In a major iteration a candidate list is - /// built from eligible arcs in a wraparound fashion and in the - /// following minor iterations the best eligible arc is selected - /// from this list (\ref CandidateListPivotRule). - /// - /// - ALTERING_LIST_PIVOT It is a modified version of the - /// "Candidate List" pivot rule. It keeps only the several best - /// eligible arcs from the former candidate list and extends this - /// list in every iteration (\ref AlteringListPivotRule). - /// - /// According to our comprehensive benchmark tests the "Block Search" - /// pivot rule proved to be the fastest and the most robust on - /// various test inputs. Thus it is the default option. + /// \param pivot_rule The pivot rule that will be used during the + /// algorithm. For more information see \ref PivotRule. /// /// \return \c true if a feasible flow can be found. - bool run(PivotRuleEnum pivot_rule = BLOCK_SEARCH_PIVOT) { + bool run(PivotRule pivot_rule = BLOCK_SEARCH) { return init() && start(pivot_rule); } @@ -765,10 +811,53 @@ /// \name Query Functions /// The results of the algorithm can be obtained using these /// functions.\n - /// \ref lemon::NetworkSimplex::run() "run()" must be called before - /// using them. + /// The \ref run() function must be called before using them. + /// @{ + /// \brief Return the total cost of the found flow. + /// + /// This function returns the total cost of the found flow. + /// The complexity of the function is \f$ O(e) \f$. + /// + /// \note The return type of the function can be specified as a + /// template parameter. For example, + /// \code + /// ns.totalCost(); + /// \endcode + /// It is useful if the total cost cannot be stored in the \c Value + /// type of the algorithm, which is the default return type of the + /// function. + /// + /// \pre \ref run() must be called before using this function. + template + Num totalCost() const { + Num c = 0; + if (_pcost) { + for (ArcIt e(_graph); e != INVALID; ++e) + c += (*_flow_map)[e] * (*_pcost)[e]; + } else { + for (ArcIt e(_graph); e != INVALID; ++e) + c += (*_flow_map)[e]; + } + return c; + } + +#ifndef DOXYGEN + Value totalCost() const { + return totalCost(); + } +#endif + + /// \brief Return the flow on the given arc. + /// + /// This function returns the flow on the given arc. + /// + /// \pre \ref run() must be called before using this function. + Value flow(const Arc& a) const { + return (*_flow_map)[a]; + } + /// \brief Return a const reference to the flow map. /// /// This function returns a const reference to an arc map storing @@ -779,48 +868,28 @@ return *_flow_map; } + /// \brief Return the potential (dual value) of the given node. + /// + /// This function returns the potential (dual value) of the + /// given node. + /// + /// \pre \ref run() must be called before using this function. + Value potential(const Node& n) const { + return (*_potential_map)[n]; + } + /// \brief Return a const reference to the potential map /// (the dual solution). /// /// This function returns a const reference to a node map storing - /// the found potentials (the dual solution). + /// the found potentials, which form the dual solution of the + /// \ref min_cost_flow "minimum cost flow" problem. /// /// \pre \ref run() must be called before using this function. const PotentialMap& potentialMap() const { return *_potential_map; } - /// \brief Return the flow on the given arc. - /// - /// This function returns the flow on the given arc. - /// - /// \pre \ref run() must be called before using this function. - Capacity flow(const Arc& arc) const { - return (*_flow_map)[arc]; - } - - /// \brief Return the potential of the given node. - /// - /// This function returns the potential of the given node. - /// - /// \pre \ref run() must be called before using this function. - Cost potential(const Node& node) const { - return (*_potential_map)[node]; - } - - /// \brief Return the total cost of the found flow. - /// - /// This function returns the total cost of the found flow. - /// The complexity of the function is \f$ O(e) \f$. - /// - /// \pre \ref run() must be called before using this function. - Cost totalCost() const { - Cost c = 0; - for (ArcIt e(_graph); e != INVALID; ++e) - c += (*_flow_map)[e] * _orig_cost[e]; - return c; - } - /// @} private: @@ -842,6 +911,7 @@ _arc_num = countArcs(_graph); int all_node_num = _node_num + 1; int all_arc_num = _arc_num + _node_num; + if (_node_num == 0) return false; _arc_ref.resize(_arc_num); _source.resize(all_arc_num); @@ -864,12 +934,17 @@ // Initialize node related data bool valid_supply = true; - if (_orig_supply) { - Supply sum = 0; + if (!_pstsup && !_psupply) { + _pstsup = true; + _psource = _ptarget = NodeIt(_graph); + _pstflow = 0; + } + if (_psupply) { + Value sum = 0; int i = 0; for (NodeIt n(_graph); n != INVALID; ++n, ++i) { _node_id[n] = i; - _supply[i] = (*_orig_supply)[n]; + _supply[i] = (*_psupply)[n]; sum += _supply[i]; } valid_supply = (sum == 0); @@ -879,8 +954,8 @@ _node_id[n] = i; _supply[i] = 0; } - _supply[_node_id[_orig_source]] = _orig_flow_value; - _supply[_node_id[_orig_target]] = -_orig_flow_value; + _supply[_node_id[_psource]] = _pstflow; + _supply[_node_id[_ptarget]] = -_pstflow; } if (!valid_supply) return false; @@ -904,18 +979,41 @@ } // Initialize arc maps - for (int i = 0; i != _arc_num; ++i) { - Arc e = _arc_ref[i]; - _source[i] = _node_id[_graph.source(e)]; - _target[i] = _node_id[_graph.target(e)]; - _cost[i] = _orig_cost[e]; - _cap[i] = _orig_cap[e]; + if (_pupper && _pcost) { + for (int i = 0; i != _arc_num; ++i) { + Arc e = _arc_ref[i]; + _source[i] = _node_id[_graph.source(e)]; + _target[i] = _node_id[_graph.target(e)]; + _cap[i] = (*_pupper)[e]; + _cost[i] = (*_pcost)[e]; + } + } else { + for (int i = 0; i != _arc_num; ++i) { + Arc e = _arc_ref[i]; + _source[i] = _node_id[_graph.source(e)]; + _target[i] = _node_id[_graph.target(e)]; + } + if (_pupper) { + for (int i = 0; i != _arc_num; ++i) + _cap[i] = (*_pupper)[_arc_ref[i]]; + } else { + Value val = std::numeric_limits::max(); + for (int i = 0; i != _arc_num; ++i) + _cap[i] = val; + } + if (_pcost) { + for (int i = 0; i != _arc_num; ++i) + _cost[i] = (*_pcost)[_arc_ref[i]]; + } else { + for (int i = 0; i != _arc_num; ++i) + _cost[i] = 1; + } } // Remove non-zero lower bounds - if (_orig_lower) { + if (_plower) { for (int i = 0; i != _arc_num; ++i) { - Capacity c = (*_orig_lower)[_arc_ref[i]]; + Value c = (*_plower)[_arc_ref[i]]; if (c != 0) { _cap[i] -= c; _supply[_source[i]] -= c; @@ -925,8 +1023,8 @@ } // Add artificial arcs and initialize the spanning tree data structure - Cost max_cost = std::numeric_limits::max() / 4; - Capacity max_cap = std::numeric_limits::max(); + Value max_cap = std::numeric_limits::max(); + Value max_cost = std::numeric_limits::max() / 4; for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) { _thread[u] = u + 1; _rev_thread[u + 1] = u; @@ -979,7 +1077,7 @@ } delta = _cap[in_arc]; int result = 0; - Capacity d; + Value d; int e; // Search the cycle along the path form the first node to the root @@ -1017,7 +1115,7 @@ void changeFlow(bool change) { // Augment along the cycle if (delta > 0) { - Capacity val = _state[in_arc] * delta; + Value val = _state[in_arc] * delta; _flow[in_arc] += val; for (int u = _source[in_arc]; u != join; u = _parent[u]) { _flow[_pred[u]] += _forward[u] ? -val : val; @@ -1158,7 +1256,7 @@ // Update potentials void updatePotential() { - Cost sigma = _forward[u_in] ? + Value sigma = _forward[u_in] ? _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] : _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]]; if (_succ_num[u_in] > _node_num / 2) { @@ -1181,28 +1279,28 @@ } // Execute the algorithm - bool start(PivotRuleEnum pivot_rule) { + bool start(PivotRule pivot_rule) { // Select the pivot rule implementation switch (pivot_rule) { - case FIRST_ELIGIBLE_PIVOT: + case FIRST_ELIGIBLE: return start(); - case BEST_ELIGIBLE_PIVOT: + case BEST_ELIGIBLE: return start(); - case BLOCK_SEARCH_PIVOT: + case BLOCK_SEARCH: return start(); - case CANDIDATE_LIST_PIVOT: + case CANDIDATE_LIST: return start(); - case ALTERING_LIST_PIVOT: + case ALTERING_LIST: return start(); } return false; } - template + template bool start() { - PivotRuleImplementation pivot(*this); + PivotRuleImpl pivot(*this); - // Execute the network simplex algorithm + // Execute the Network Simplex algorithm while (pivot.findEnteringArc()) { findJoinNode(); bool change = findLeavingArc(); @@ -1219,10 +1317,10 @@ } // Copy flow values to _flow_map - if (_orig_lower) { + if (_plower) { for (int i = 0; i != _arc_num; ++i) { Arc e = _arc_ref[i]; - _flow_map->set(e, (*_orig_lower)[e] + _flow[i]); + _flow_map->set(e, (*_plower)[e] + _flow[i]); } } else { for (int i = 0; i != _arc_num; ++i) { diff --git a/test/min_cost_flow_test.cc b/test/min_cost_flow_test.cc --- a/test/min_cost_flow_test.cc +++ b/test/min_cost_flow_test.cc @@ -20,15 +20,9 @@ #include #include -#include #include -//#include -//#include -//#include #include -//#include -//#include #include #include @@ -93,36 +87,30 @@ void constraints() { checkConcept(); - MCF mcf_test1(g, lower, upper, cost, sup); - MCF mcf_test2(g, upper, cost, sup); - MCF mcf_test3(g, lower, upper, cost, n, n, k); - MCF mcf_test4(g, upper, cost, n, n, k); + MCF mcf(g); - // TODO: This part should be enabled and the next part - // should be removed if map copying is supported -/* - flow = mcf_test1.flowMap(); - mcf_test1.flowMap(flow); + b = mcf.lowerMap(lower) + .upperMap(upper) + .capacityMap(upper) + .boundMaps(lower, upper) + .costMap(cost) + .supplyMap(sup) + .stSupply(n, n, k) + .run(); - pot = mcf_test1.potentialMap(); - mcf_test1.potentialMap(pot); -*/ -/**/ - const typename MCF::FlowMap &fm = - mcf_test1.flowMap(); - mcf_test1.flowMap(flow); - const typename MCF::PotentialMap &pm = - mcf_test1.potentialMap(); - mcf_test1.potentialMap(pot); + const typename MCF::FlowMap &fm = mcf.flowMap(); + const typename MCF::PotentialMap &pm = mcf.potentialMap(); + + v = mcf.totalCost(); + double x = mcf.template totalCost(); + v = mcf.flow(a); + v = mcf.potential(n); + mcf.flowMap(flow); + mcf.potentialMap(pot); + ignore_unused_variable_warning(fm); ignore_unused_variable_warning(pm); -/**/ - - mcf_test1.run(); - - v = mcf_test1.totalCost(); - v = mcf_test1.flow(a); - v = mcf_test1.potential(n); + ignore_unused_variable_warning(x); } typedef typename GR::Node Node; @@ -139,6 +127,7 @@ const Arc &a; const Value &k; Value v; + bool b; typename MCF::FlowMap &flow; typename MCF::PotentialMap &pot; @@ -172,7 +161,7 @@ } // Check the feasibility of the given potentials (dual soluiton) -// using the Complementary Slackness optimality condition +// using the "Complementary Slackness" optimality condition template < typename GR, typename LM, typename UM, typename CM, typename FM, typename PM > bool checkPotential( const GR& gr, const LM& lower, const UM& upper, @@ -217,23 +206,14 @@ // Check the interfaces { typedef int Value; - // This typedef should be enabled if the standard maps are - // reference maps in the graph concepts + // TODO: This typedef should be enabled if the standard maps are + // reference maps in the graph concepts (See #190). +/**/ //typedef concepts::Digraph GR; typedef ListDigraph GR; - typedef concepts::ReadMap NM; - typedef concepts::ReadMap AM; - - //checkConcept< McfClassConcept, - // CycleCanceling >(); - //checkConcept< McfClassConcept, - // CapacityScaling >(); - //checkConcept< McfClassConcept, - // CostScaling >(); +/**/ checkConcept< McfClassConcept, - NetworkSimplex >(); - //checkConcept< MinCostFlow, - // NetworkSimplex >(); + NetworkSimplex >(); } // Run various MCF tests @@ -244,6 +224,7 @@ Digraph gr; Digraph::ArcMap c(gr), l1(gr), l2(gr), u(gr); Digraph::NodeMap s1(gr), s2(gr), s3(gr); + ConstMap cc(1), cu(std::numeric_limits::max()); Node v, w; std::istringstream input(test_lgf); @@ -259,197 +240,50 @@ .node("target", w) .run(); -/* - // A. Test CapacityScaling with scaling + // A. Test NetworkSimplex with the default pivot rule { - CapacityScaling mcf1(gr, u, c, s1); - CapacityScaling mcf2(gr, u, c, v, w, 27); - CapacityScaling mcf3(gr, u, c, s3); - CapacityScaling mcf4(gr, l2, u, c, s1); - CapacityScaling mcf5(gr, l2, u, c, v, w, 27); - CapacityScaling mcf6(gr, l2, u, c, s3); + NetworkSimplex mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), + mcf5(gr), mcf6(gr), mcf7(gr), mcf8(gr); - checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#A1"); - checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#A2"); - checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#A3"); - checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#A4"); - checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#A5"); - checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#A6"); + checkMcf(mcf1, mcf1.upperMap(u).costMap(c).supplyMap(s1).run(), + gr, l1, u, c, s1, true, 5240, "#A1"); + checkMcf(mcf2, mcf2.upperMap(u).costMap(c).stSupply(v, w, 27).run(), + gr, l1, u, c, s2, true, 7620, "#A2"); + checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(), + gr, l2, u, c, s1, true, 5970, "#A3"); + checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).stSupply(v, w, 27).run(), + gr, l2, u, c, s2, true, 8010, "#A4"); + checkMcf(mcf5, mcf5.supplyMap(s1).run(), + gr, l1, cu, cc, s1, true, 74, "#A5"); + checkMcf(mcf6, mcf6.stSupply(v, w, 27).lowerMap(l2).run(), + gr, l2, cu, cc, s2, true, 94, "#A6"); + checkMcf(mcf7, mcf7.run(), + gr, l1, cu, cc, s3, true, 0, "#A7"); + checkMcf(mcf8, mcf8.boundMaps(l2, u).run(), + gr, l2, u, cc, s3, false, 0, "#A8"); } - // B. Test CapacityScaling without scaling + // B. Test NetworkSimplex with each pivot rule { - CapacityScaling mcf1(gr, u, c, s1); - CapacityScaling mcf2(gr, u, c, v, w, 27); - CapacityScaling mcf3(gr, u, c, s3); - CapacityScaling mcf4(gr, l2, u, c, s1); - CapacityScaling mcf5(gr, l2, u, c, v, w, 27); - CapacityScaling mcf6(gr, l2, u, c, s3); + NetworkSimplex mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr); + NetworkSimplex::PivotRule pr; - checkMcf(mcf1, mcf1.run(false), gr, l1, u, c, s1, true, 5240, "#B1"); - checkMcf(mcf2, mcf2.run(false), gr, l1, u, c, s2, true, 7620, "#B2"); - checkMcf(mcf3, mcf3.run(false), gr, l1, u, c, s3, true, 0, "#B3"); - checkMcf(mcf4, mcf4.run(false), gr, l2, u, c, s1, true, 5970, "#B4"); - checkMcf(mcf5, mcf5.run(false), gr, l2, u, c, s2, true, 8010, "#B5"); - checkMcf(mcf6, mcf6.run(false), gr, l2, u, c, s3, false, 0, "#B6"); + pr = NetworkSimplex::FIRST_ELIGIBLE; + checkMcf(mcf1, mcf1.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), + gr, l2, u, c, s1, true, 5970, "#B1"); + pr = NetworkSimplex::BEST_ELIGIBLE; + checkMcf(mcf2, mcf2.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), + gr, l2, u, c, s1, true, 5970, "#B2"); + pr = NetworkSimplex::BLOCK_SEARCH; + checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), + gr, l2, u, c, s1, true, 5970, "#B3"); + pr = NetworkSimplex::CANDIDATE_LIST; + checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), + gr, l2, u, c, s1, true, 5970, "#B4"); + pr = NetworkSimplex::ALTERING_LIST; + checkMcf(mcf5, mcf5.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr), + gr, l2, u, c, s1, true, 5970, "#B5"); } - // C. Test CostScaling using partial augment-relabel method - { - CostScaling mcf1(gr, u, c, s1); - CostScaling mcf2(gr, u, c, v, w, 27); - CostScaling mcf3(gr, u, c, s3); - CostScaling mcf4(gr, l2, u, c, s1); - CostScaling mcf5(gr, l2, u, c, v, w, 27); - CostScaling mcf6(gr, l2, u, c, s3); - - checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#C1"); - checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#C2"); - checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#C3"); - checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#C4"); - checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#C5"); - checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#C6"); - } - - // D. Test CostScaling using push-relabel method - { - CostScaling mcf1(gr, u, c, s1); - CostScaling mcf2(gr, u, c, v, w, 27); - CostScaling mcf3(gr, u, c, s3); - CostScaling mcf4(gr, l2, u, c, s1); - CostScaling mcf5(gr, l2, u, c, v, w, 27); - CostScaling mcf6(gr, l2, u, c, s3); - - checkMcf(mcf1, mcf1.run(false), gr, l1, u, c, s1, true, 5240, "#D1"); - checkMcf(mcf2, mcf2.run(false), gr, l1, u, c, s2, true, 7620, "#D2"); - checkMcf(mcf3, mcf3.run(false), gr, l1, u, c, s3, true, 0, "#D3"); - checkMcf(mcf4, mcf4.run(false), gr, l2, u, c, s1, true, 5970, "#D4"); - checkMcf(mcf5, mcf5.run(false), gr, l2, u, c, s2, true, 8010, "#D5"); - checkMcf(mcf6, mcf6.run(false), gr, l2, u, c, s3, false, 0, "#D6"); - } -*/ - - // E. Test NetworkSimplex with FIRST_ELIGIBLE_PIVOT - { - NetworkSimplex::PivotRuleEnum pr = - NetworkSimplex::FIRST_ELIGIBLE_PIVOT; - NetworkSimplex mcf1(gr, u, c, s1); - NetworkSimplex mcf2(gr, u, c, v, w, 27); - NetworkSimplex mcf3(gr, u, c, s3); - NetworkSimplex mcf4(gr, l2, u, c, s1); - NetworkSimplex mcf5(gr, l2, u, c, v, w, 27); - NetworkSimplex mcf6(gr, l2, u, c, s3); - - checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#E1"); - checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#E2"); - checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#E3"); - checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#E4"); - checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#E5"); - checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#E6"); - } - - // F. Test NetworkSimplex with BEST_ELIGIBLE_PIVOT - { - NetworkSimplex::PivotRuleEnum pr = - NetworkSimplex::BEST_ELIGIBLE_PIVOT; - NetworkSimplex mcf1(gr, u, c, s1); - NetworkSimplex mcf2(gr, u, c, v, w, 27); - NetworkSimplex mcf3(gr, u, c, s3); - NetworkSimplex mcf4(gr, l2, u, c, s1); - NetworkSimplex mcf5(gr, l2, u, c, v, w, 27); - NetworkSimplex mcf6(gr, l2, u, c, s3); - - checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#F1"); - checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#F2"); - checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#F3"); - checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#F4"); - checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#F5"); - checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#F6"); - } - - // G. Test NetworkSimplex with BLOCK_SEARCH_PIVOT - { - NetworkSimplex::PivotRuleEnum pr = - NetworkSimplex::BLOCK_SEARCH_PIVOT; - NetworkSimplex mcf1(gr, u, c, s1); - NetworkSimplex mcf2(gr, u, c, v, w, 27); - NetworkSimplex mcf3(gr, u, c, s3); - NetworkSimplex mcf4(gr, l2, u, c, s1); - NetworkSimplex mcf5(gr, l2, u, c, v, w, 27); - NetworkSimplex mcf6(gr, l2, u, c, s3); - - checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#G1"); - checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#G2"); - checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#G3"); - checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#G4"); - checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#G5"); - checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#G6"); - } - - // H. Test NetworkSimplex with CANDIDATE_LIST_PIVOT - { - NetworkSimplex::PivotRuleEnum pr = - NetworkSimplex::CANDIDATE_LIST_PIVOT; - NetworkSimplex mcf1(gr, u, c, s1); - NetworkSimplex mcf2(gr, u, c, v, w, 27); - NetworkSimplex mcf3(gr, u, c, s3); - NetworkSimplex mcf4(gr, l2, u, c, s1); - NetworkSimplex mcf5(gr, l2, u, c, v, w, 27); - NetworkSimplex mcf6(gr, l2, u, c, s3); - - checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#H1"); - checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#H2"); - checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#H3"); - checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#H4"); - checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#H5"); - checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#H6"); - } - - // I. Test NetworkSimplex with ALTERING_LIST_PIVOT - { - NetworkSimplex::PivotRuleEnum pr = - NetworkSimplex::ALTERING_LIST_PIVOT; - NetworkSimplex mcf1(gr, u, c, s1); - NetworkSimplex mcf2(gr, u, c, v, w, 27); - NetworkSimplex mcf3(gr, u, c, s3); - NetworkSimplex mcf4(gr, l2, u, c, s1); - NetworkSimplex mcf5(gr, l2, u, c, v, w, 27); - NetworkSimplex mcf6(gr, l2, u, c, s3); - - checkMcf(mcf1, mcf1.run(pr), gr, l1, u, c, s1, true, 5240, "#I1"); - checkMcf(mcf2, mcf2.run(pr), gr, l1, u, c, s2, true, 7620, "#I2"); - checkMcf(mcf3, mcf3.run(pr), gr, l1, u, c, s3, true, 0, "#I3"); - checkMcf(mcf4, mcf4.run(pr), gr, l2, u, c, s1, true, 5970, "#I4"); - checkMcf(mcf5, mcf5.run(pr), gr, l2, u, c, s2, true, 8010, "#I5"); - checkMcf(mcf6, mcf6.run(pr), gr, l2, u, c, s3, false, 0, "#I6"); - } - -/* - // J. Test MinCostFlow - { - MinCostFlow mcf1(gr, u, c, s1); - MinCostFlow mcf2(gr, u, c, v, w, 27); - MinCostFlow mcf3(gr, u, c, s3); - MinCostFlow mcf4(gr, l2, u, c, s1); - MinCostFlow mcf5(gr, l2, u, c, v, w, 27); - MinCostFlow mcf6(gr, l2, u, c, s3); - - checkMcf(mcf1, mcf1.run(), gr, l1, u, c, s1, true, 5240, "#J1"); - checkMcf(mcf2, mcf2.run(), gr, l1, u, c, s2, true, 7620, "#J2"); - checkMcf(mcf3, mcf3.run(), gr, l1, u, c, s3, true, 0, "#J3"); - checkMcf(mcf4, mcf4.run(), gr, l2, u, c, s1, true, 5970, "#J4"); - checkMcf(mcf5, mcf5.run(), gr, l2, u, c, s2, true, 8010, "#J5"); - checkMcf(mcf6, mcf6.run(), gr, l2, u, c, s3, false, 0, "#J6"); - } -*/ -/* - // K. Test MinCostMaxFlow - { - MinCostMaxFlow mcmf(gr, u, c, v, w); - mcmf.run(); - checkMcf(mcmf, true, gr, l1, u, c, s3, true, 7620, "#K1"); - } -*/ - return 0; } diff --git a/tools/dimacs-solver.cc b/tools/dimacs-solver.cc --- a/tools/dimacs-solver.cc +++ b/tools/dimacs-solver.cc @@ -105,9 +105,8 @@ readDimacsMin(is, g, lower, cap, cost, sup, desc); if (report) std::cerr << "Read the file: " << ti << '\n'; ti.restart(); - NetworkSimplex< Digraph, Digraph::ArcMap, Digraph::ArcMap, - Digraph::ArcMap, Digraph::NodeMap > - ns(g, lower, cap, cost, sup); + NetworkSimplex ns(g); + ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup); if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n'; ti.restart(); ns.run();