# HG changeset patch
# User Peter Kovacs <kpeter@inf.elte.hu>
# Date 1237993124 -3600
# Node ID 5232721b3f1430a5035eed7913c9024a4c24ed8c
# Parent 8c3112a66878ea474302c98be9cb538208f4866f
Rework the interface of NetworkSimplex (#234)
The parameters of the problem can be set with separate functions
instead of different constructors.
diff -r 8c3112a66878 -r 5232721b3f14 lemon/network_simplex.h
--- a/lemon/network_simplex.h Tue Mar 24 00:18:25 2009 +0100
+++ b/lemon/network_simplex.h Wed Mar 25 15:58:44 2009 +0100
@@ -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 <vector>
#include <limits>
@@ -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<int>,
- typename CapacityMap = typename Digraph::template ArcMap<int>,
- typename CostMap = typename Digraph::template ArcMap<int>,
- typename SupplyMap = typename Digraph::template NodeMap<int> >
-#endif
+ /// \note %NetworkSimplex provides five different pivot rule
+ /// implementations. For more information see \ref PivotRule.
+ template <typename GR, typename V = int>
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<Value> FlowMap;
+ /// The type of the potential map
+ typedef typename GR::template NodeMap<Value> 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<Value> ValueArcMap;
+ typedef typename GR::template NodeMap<Value> ValueNodeMap;
typedef std::vector<Arc> ArcVector;
typedef std::vector<Node> NodeVector;
typedef std::vector<int> IntVector;
typedef std::vector<bool> BoolVector;
- typedef std::vector<Capacity> CapacityVector;
- typedef std::vector<Cost> CostVector;
- typedef std::vector<Supply> SupplyVector;
-
- public:
-
- /// The type of the flow map
- typedef typename Digraph::template ArcMap<Capacity> FlowMap;
- /// The type of the potential map
- typedef typename Digraph::template NodeMap<Cost> 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<Value> 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<Value>::is_integer &&
+ std::numeric_limits<Value>::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 <tt>(*this)</tt>
+ template <typename LOWER>
+ 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<Value>::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 <tt>(*this)</tt>
+ template<typename UPPER>
+ 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 <tt>(*this)</tt>
+ template<typename CAP>
+ 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<Value>::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 <tt>(*this)</tt>
+ template <typename LOWER, typename UPPER>
+ 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 <tt>(*this)</tt>
+ template<typename COST>
+ 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 <tt>(*this)</tt>
+ template<typename SUP>
+ 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 <tt>(*this)</tt>
+ 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 <tt>(*this)</tt>
- 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 <tt>(*this)</tt>
- 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<ListDigraph> 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<double>();
+ /// \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 <typename Num>
+ 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<Value>();
+ }
+#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<Value>::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<Cost>::max() / 4;
- Capacity max_cap = std::numeric_limits<Capacity>::max();
+ Value max_cap = std::numeric_limits<Value>::max();
+ Value max_cost = std::numeric_limits<Value>::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<FirstEligiblePivotRule>();
- case BEST_ELIGIBLE_PIVOT:
+ case BEST_ELIGIBLE:
return start<BestEligiblePivotRule>();
- case BLOCK_SEARCH_PIVOT:
+ case BLOCK_SEARCH:
return start<BlockSearchPivotRule>();
- case CANDIDATE_LIST_PIVOT:
+ case CANDIDATE_LIST:
return start<CandidateListPivotRule>();
- case ALTERING_LIST_PIVOT:
+ case ALTERING_LIST:
return start<AlteringListPivotRule>();
}
return false;
}
- template<class PivotRuleImplementation>
+ template <typename PivotRuleImpl>
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 -r 8c3112a66878 -r 5232721b3f14 test/min_cost_flow_test.cc
--- a/test/min_cost_flow_test.cc Tue Mar 24 00:18:25 2009 +0100
+++ b/test/min_cost_flow_test.cc Wed Mar 25 15:58:44 2009 +0100
@@ -20,15 +20,9 @@
#include <fstream>
#include <lemon/list_graph.h>
-#include <lemon/smart_graph.h>
#include <lemon/lgf_reader.h>
-//#include <lemon/cycle_canceling.h>
-//#include <lemon/capacity_scaling.h>
-//#include <lemon/cost_scaling.h>
#include <lemon/network_simplex.h>
-//#include <lemon/min_cost_flow.h>
-//#include <lemon/min_cost_max_flow.h>
#include <lemon/concepts/digraph.h>
#include <lemon/concept_check.h>
@@ -93,36 +87,30 @@
void constraints() {
checkConcept<concepts::Digraph, GR>();
- 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<double>();
+ 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<GR::Node, Value> NM;
- typedef concepts::ReadMap<GR::Arc, Value> AM;
-
- //checkConcept< McfClassConcept<GR, Value>,
- // CycleCanceling<GR, AM, AM, AM, NM> >();
- //checkConcept< McfClassConcept<GR, Value>,
- // CapacityScaling<GR, AM, AM, AM, NM> >();
- //checkConcept< McfClassConcept<GR, Value>,
- // CostScaling<GR, AM, AM, AM, NM> >();
+/**/
checkConcept< McfClassConcept<GR, Value>,
- NetworkSimplex<GR, AM, AM, AM, NM> >();
- //checkConcept< MinCostFlow<GR, Value>,
- // NetworkSimplex<GR, AM, AM, AM, NM> >();
+ NetworkSimplex<GR, Value> >();
}
// Run various MCF tests
@@ -244,6 +224,7 @@
Digraph gr;
Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr);
+ ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::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<Digraph> mcf1(gr, u, c, s1);
- CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27);
- CapacityScaling<Digraph> mcf3(gr, u, c, s3);
- CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1);
- CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27);
- CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3);
+ NetworkSimplex<Digraph> 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<Digraph> mcf1(gr, u, c, s1);
- CapacityScaling<Digraph> mcf2(gr, u, c, v, w, 27);
- CapacityScaling<Digraph> mcf3(gr, u, c, s3);
- CapacityScaling<Digraph> mcf4(gr, l2, u, c, s1);
- CapacityScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27);
- CapacityScaling<Digraph> mcf6(gr, l2, u, c, s3);
+ NetworkSimplex<Digraph> mcf1(gr), mcf2(gr), mcf3(gr), mcf4(gr), mcf5(gr);
+ NetworkSimplex<Digraph>::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<Digraph>::FIRST_ELIGIBLE;
+ checkMcf(mcf1, mcf1.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
+ gr, l2, u, c, s1, true, 5970, "#B1");
+ pr = NetworkSimplex<Digraph>::BEST_ELIGIBLE;
+ checkMcf(mcf2, mcf2.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
+ gr, l2, u, c, s1, true, 5970, "#B2");
+ pr = NetworkSimplex<Digraph>::BLOCK_SEARCH;
+ checkMcf(mcf3, mcf3.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
+ gr, l2, u, c, s1, true, 5970, "#B3");
+ pr = NetworkSimplex<Digraph>::CANDIDATE_LIST;
+ checkMcf(mcf4, mcf4.boundMaps(l2, u).costMap(c).supplyMap(s1).run(pr),
+ gr, l2, u, c, s1, true, 5970, "#B4");
+ pr = NetworkSimplex<Digraph>::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<Digraph> mcf1(gr, u, c, s1);
- CostScaling<Digraph> mcf2(gr, u, c, v, w, 27);
- CostScaling<Digraph> mcf3(gr, u, c, s3);
- CostScaling<Digraph> mcf4(gr, l2, u, c, s1);
- CostScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27);
- CostScaling<Digraph> 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<Digraph> mcf1(gr, u, c, s1);
- CostScaling<Digraph> mcf2(gr, u, c, v, w, 27);
- CostScaling<Digraph> mcf3(gr, u, c, s3);
- CostScaling<Digraph> mcf4(gr, l2, u, c, s1);
- CostScaling<Digraph> mcf5(gr, l2, u, c, v, w, 27);
- CostScaling<Digraph> 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<Digraph>::PivotRuleEnum pr =
- NetworkSimplex<Digraph>::FIRST_ELIGIBLE_PIVOT;
- NetworkSimplex<Digraph> mcf1(gr, u, c, s1);
- NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27);
- NetworkSimplex<Digraph> mcf3(gr, u, c, s3);
- NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1);
- NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27);
- NetworkSimplex<Digraph> 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<Digraph>::PivotRuleEnum pr =
- NetworkSimplex<Digraph>::BEST_ELIGIBLE_PIVOT;
- NetworkSimplex<Digraph> mcf1(gr, u, c, s1);
- NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27);
- NetworkSimplex<Digraph> mcf3(gr, u, c, s3);
- NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1);
- NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27);
- NetworkSimplex<Digraph> 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<Digraph>::PivotRuleEnum pr =
- NetworkSimplex<Digraph>::BLOCK_SEARCH_PIVOT;
- NetworkSimplex<Digraph> mcf1(gr, u, c, s1);
- NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27);
- NetworkSimplex<Digraph> mcf3(gr, u, c, s3);
- NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1);
- NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27);
- NetworkSimplex<Digraph> 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<Digraph>::PivotRuleEnum pr =
- NetworkSimplex<Digraph>::CANDIDATE_LIST_PIVOT;
- NetworkSimplex<Digraph> mcf1(gr, u, c, s1);
- NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27);
- NetworkSimplex<Digraph> mcf3(gr, u, c, s3);
- NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1);
- NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27);
- NetworkSimplex<Digraph> 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<Digraph>::PivotRuleEnum pr =
- NetworkSimplex<Digraph>::ALTERING_LIST_PIVOT;
- NetworkSimplex<Digraph> mcf1(gr, u, c, s1);
- NetworkSimplex<Digraph> mcf2(gr, u, c, v, w, 27);
- NetworkSimplex<Digraph> mcf3(gr, u, c, s3);
- NetworkSimplex<Digraph> mcf4(gr, l2, u, c, s1);
- NetworkSimplex<Digraph> mcf5(gr, l2, u, c, v, w, 27);
- NetworkSimplex<Digraph> 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<Digraph> mcf1(gr, u, c, s1);
- MinCostFlow<Digraph> mcf2(gr, u, c, v, w, 27);
- MinCostFlow<Digraph> mcf3(gr, u, c, s3);
- MinCostFlow<Digraph> mcf4(gr, l2, u, c, s1);
- MinCostFlow<Digraph> mcf5(gr, l2, u, c, v, w, 27);
- MinCostFlow<Digraph> 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<Digraph> mcmf(gr, u, c, v, w);
- mcmf.run();
- checkMcf(mcmf, true, gr, l1, u, c, s3, true, 7620, "#K1");
- }
-*/
-
return 0;
}
diff -r 8c3112a66878 -r 5232721b3f14 tools/dimacs-solver.cc
--- a/tools/dimacs-solver.cc Tue Mar 24 00:18:25 2009 +0100
+++ b/tools/dimacs-solver.cc Wed Mar 25 15:58:44 2009 +0100
@@ -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<Value>, Digraph::ArcMap<Value>,
- Digraph::ArcMap<Value>, Digraph::NodeMap<Value> >
- ns(g, lower, cap, cost, sup);
+ NetworkSimplex<Digraph, Value> ns(g);
+ ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
ti.restart();
ns.run();