# HG changeset patch # User Alpar Juttner # Date 2009-04-21 16:18:54 # Node ID 85cb3aa71cced72f8915b8abf50f705037a76bb1 # Parent 0ba8dfce725936da00a99430fb96aa971f5ecb8c # Parent dacc2cee2b4c4ec7481d3edec47aaf834b5db47c Merge and fix diff --git a/doc/groups.dox b/doc/groups.dox --- a/doc/groups.dox +++ b/doc/groups.dox @@ -317,15 +317,15 @@ The \e maximum \e flow \e problem is to find a flow of maximum value between a single source and a single target. Formally, there is a \f$G=(V,A)\f$ -digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and +digraph, a \f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function and \f$s, t \in V\f$ source and target nodes. -A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the +A maximum flow is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ solution of the following optimization problem. -\f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f] -\f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a) - \qquad \forall v\in V\setminus\{s,t\} \f] -\f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f] +\f[ \max\sum_{sv\in A} f(sv) - \sum_{vs\in A} f(vs) \f] +\f[ \sum_{uv\in A} f(uv) = \sum_{vu\in A} f(vu) + \quad \forall u\in V\setminus\{s,t\} \f] +\f[ 0 \leq f(uv) \leq cap(uv) \quad \forall uv\in A \f] LEMON contains several algorithms for solving maximum flow problems: - \ref EdmondsKarp Edmonds-Karp algorithm. @@ -350,30 +350,98 @@ The \e minimum \e cost \e flow \e problem is to find a feasible flow of minimum total cost from a set of supply nodes to a set of demand nodes -in a network with capacity constraints and arc costs. +in a network with capacity constraints (lower and upper bounds) +and arc costs. Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and -upper bounds for the flow values on the arcs, +upper bounds for the flow values on the arcs, for which +\f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$. \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow -on the arcs, and -\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values -of the nodes. -A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of -the following optimization problem. +on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the +signed supply values of the nodes. +If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ +supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with +\f$-sup(u)\f$ demand. +A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution +of the following optimization problem. -\f[ \min\sum_{a\in A} f(a) cost(a) \f] -\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) = - supply(v) \qquad \forall v\in V \f] -\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f] +\f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq + sup(u) \quad \forall u\in V \f] +\f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] -LEMON contains several algorithms for solving minimum cost flow problems: - - \ref CycleCanceling Cycle-canceling algorithms. - - \ref CapacityScaling Successive shortest path algorithm with optional +The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be +zero or negative in order to have a feasible solution (since the sum +of the expressions on the left-hand side of the inequalities is zero). +It means that the total demand must be greater or equal to the total +supply and all the supplies have to be carried out from the supply nodes, +but there could be demands that are not satisfied. +If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand +constraints have to be satisfied with equality, i.e. all demands +have to be satisfied and all supplies have to be used. + +If you need the opposite inequalities in the supply/demand constraints +(i.e. the total demand is less than the total supply and all the demands +have to be satisfied while there could be supplies that are not used), +then you could easily transform the problem to the above form by reversing +the direction of the arcs and taking the negative of the supply values +(e.g. using \ref ReverseDigraph and \ref NegMap adaptors). +However \ref NetworkSimplex algorithm also supports this form directly +for the sake of convenience. + +A feasible solution for this problem can be found using \ref Circulation. + +Note that the above formulation is actually more general than the usual +definition of the minimum cost flow problem, in which strict equalities +are required in the supply/demand contraints, i.e. + +\f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) = + sup(u) \quad \forall u\in V. \f] + +However if the sum of the supply values is zero, then these two problems +are equivalent. So if you need the equality form, you have to ensure this +additional contraint for the algorithms. + +The dual solution of the minimum cost flow problem is represented by node +potentials \f$\pi: V\rightarrow\mathbf{Z}\f$. +An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem +is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$ +node potentials the following \e complementary \e slackness optimality +conditions hold. + + - For all \f$uv\in A\f$ arcs: + - if \f$cost^\pi(uv)>0\f$, then \f$f(uv)=lower(uv)\f$; + - if \f$lower(uv) + typename UM, typename SM> struct CirculationDefaultTraits { /// \brief The type of the digraph the algorithm runs on. typedef GR Digraph; - /// \brief The type of the map that stores the circulation lower - /// bound. + /// \brief The type of the lower bound map. /// - /// The type of the map that stores the circulation lower bound. - /// It must meet the \ref concepts::ReadMap "ReadMap" concept. - typedef LM LCapMap; + /// The type of the map that stores the lower bounds on the arcs. + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. + typedef LM LowerMap; - /// \brief The type of the map that stores the circulation upper - /// bound. + /// \brief The type of the upper bound (capacity) map. /// - /// The type of the map that stores the circulation upper bound. - /// It must meet the \ref concepts::ReadMap "ReadMap" concept. - typedef UM UCapMap; + /// The type of the map that stores the upper bounds (capacities) + /// on the arcs. + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. + typedef UM UpperMap; - /// \brief The type of the map that stores the lower bound for - /// the supply of the nodes. + /// \brief The type of supply map. /// - /// The type of the map that stores the lower bound for the supply - /// of the nodes. It must meet the \ref concepts::ReadMap "ReadMap" - /// concept. - typedef DM DeltaMap; + /// The type of the map that stores the signed supply values of the + /// nodes. + /// It must conform to the \ref concepts::ReadMap "ReadMap" concept. + typedef SM SupplyMap; /// \brief The type of the flow values. - typedef typename DeltaMap::Value Value; + typedef typename SupplyMap::Value Flow; /// \brief The type of the map that stores the flow values. /// /// The type of the map that stores the flow values. - /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. - typedef typename Digraph::template ArcMap FlowMap; + /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap" + /// concept. + typedef typename Digraph::template ArcMap FlowMap; /// \brief Instantiates a FlowMap. /// /// This function instantiates a \ref FlowMap. - /// \param digraph The digraph, to which we would like to define + /// \param digraph The digraph for which we would like to define /// the flow map. static FlowMap* createFlowMap(const Digraph& digraph) { return new FlowMap(digraph); @@ -93,7 +93,7 @@ /// \brief Instantiates an Elevator. /// /// This function instantiates an \ref Elevator. - /// \param digraph The digraph, to which we would like to define + /// \param digraph The digraph for which we would like to define /// the elevator. /// \param max_level The maximum level of the elevator. static Elevator* createElevator(const Digraph& digraph, int max_level) { @@ -103,7 +103,7 @@ /// \brief The tolerance used by the algorithm /// /// The tolerance used by the algorithm to handle inexact computation. - typedef lemon::Tolerance Tolerance; + typedef lemon::Tolerance Tolerance; }; @@ -111,53 +111,69 @@ \brief Push-relabel algorithm for the network circulation problem. \ingroup max_flow - This class implements a push-relabel algorithm for the network - circulation problem. + This class implements a push-relabel algorithm for the \e network + \e circulation problem. It is to find a feasible circulation when lower and upper bounds - are given for the flow values on the arcs and lower bounds - are given for the supply values of the nodes. + are given for the flow values on the arcs and lower bounds are + given for the difference between the outgoing and incoming flow + at the nodes. The exact formulation of this problem is the following. Let \f$G=(V,A)\f$ be a digraph, - \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$, - \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation - \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that - \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) - \geq delta(v) \quad \forall v\in V, \f] - \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f] - \note \f$delta(v)\f$ specifies a lower bound for the supply of node - \f$v\f$. It can be either positive or negative, however note that - \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to - have a feasible solution. + \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and + upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$ + holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$ + denotes the signed supply values of the nodes. + If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ + supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with + \f$-sup(u)\f$ demand. + A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ + solution of the following problem. - \note A special case of this problem is when - \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$ - will be \e equal \e to \f$delta(v)\f$, if a circulation can be found. - Thus a feasible solution for the - \ref min_cost_flow "minimum cost flow" problem can be calculated - in this way. + \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) + \geq sup(u) \quad \forall u\in V, \f] + \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A. \f] + + The sum of the supply values, i.e. \f$\sum_{u\in V} sup(u)\f$ must be + zero or negative in order to have a feasible solution (since the sum + of the expressions on the left-hand side of the inequalities is zero). + It means that the total demand must be greater or equal to the total + supply and all the supplies have to be carried out from the supply nodes, + but there could be demands that are not satisfied. + If \f$\sum_{u\in V} sup(u)\f$ is zero, then all the supply/demand + constraints have to be satisfied with equality, i.e. all demands + have to be satisfied and all supplies have to be used. + + If you need the opposite inequalities in the supply/demand constraints + (i.e. the total demand is less than the total supply and all the demands + have to be satisfied while there could be supplies that are not used), + then you could easily transform the problem to the above form by reversing + the direction of the arcs and taking the negative of the supply values + (e.g. using \ref ReverseDigraph and \ref NegMap adaptors). + + Note that this algorithm also provides a feasible solution for the + \ref min_cost_flow "minimum cost flow problem". \tparam GR The type of the digraph the algorithm runs on. - \tparam LM The type of the lower bound capacity map. The default + \tparam LM The type of the lower bound map. The default map type is \ref concepts::Digraph::ArcMap "GR::ArcMap". - \tparam UM The type of the upper bound capacity map. The default - map type is \c LM. - \tparam DM The type of the map that stores the lower bound - for the supply of the nodes. The default map type is + \tparam UM The type of the upper bound (capacity) map. + The default map type is \c LM. + \tparam SM The type of the supply map. The default map type is \ref concepts::Digraph::NodeMap "GR::NodeMap". */ #ifdef DOXYGEN template< typename GR, typename LM, typename UM, - typename DM, + typename SM, typename TR > #else template< typename GR, typename LM = typename GR::template ArcMap, typename UM = LM, - typename DM = typename GR::template NodeMap, - typename TR = CirculationDefaultTraits > + typename SM = typename GR::template NodeMap, + typename TR = CirculationDefaultTraits > #endif class Circulation { public: @@ -167,15 +183,14 @@ ///The type of the digraph the algorithm runs on. typedef typename Traits::Digraph Digraph; ///The type of the flow values. - typedef typename Traits::Value Value; + typedef typename Traits::Flow Flow; - /// The type of the lower bound capacity map. - typedef typename Traits::LCapMap LCapMap; - /// The type of the upper bound capacity map. - typedef typename Traits::UCapMap UCapMap; - /// \brief The type of the map that stores the lower bound for - /// the supply of the nodes. - typedef typename Traits::DeltaMap DeltaMap; + ///The type of the lower bound map. + typedef typename Traits::LowerMap LowerMap; + ///The type of the upper bound (capacity) map. + typedef typename Traits::UpperMap UpperMap; + ///The type of the supply map. + typedef typename Traits::SupplyMap SupplyMap; ///The type of the flow map. typedef typename Traits::FlowMap FlowMap; @@ -191,9 +206,9 @@ const Digraph &_g; int _node_num; - const LCapMap *_lo; - const UCapMap *_up; - const DeltaMap *_delta; + const LowerMap *_lo; + const UpperMap *_up; + const SupplyMap *_supply; FlowMap *_flow; bool _local_flow; @@ -201,7 +216,7 @@ Elevator* _level; bool _local_level; - typedef typename Digraph::template NodeMap ExcessMap; + typedef typename Digraph::template NodeMap ExcessMap; ExcessMap* _excess; Tolerance _tol; @@ -231,9 +246,9 @@ /// type. template struct SetFlowMap - : public Circulation > { - typedef Circulation > Create; }; @@ -257,9 +272,9 @@ /// \sa SetStandardElevator template struct SetElevator - : public Circulation > { - typedef Circulation > Create; }; @@ -285,9 +300,9 @@ /// \sa SetElevator template struct SetStandardElevator - : public Circulation > { - typedef Circulation > Create; }; @@ -299,18 +314,20 @@ public: - /// The constructor of the class. + /// Constructor. /// The constructor of the class. - /// \param g The digraph the algorithm runs on. - /// \param lo The lower bound capacity of the arcs. - /// \param up The upper bound capacity of the arcs. - /// \param delta The lower bound for the supply of the nodes. - Circulation(const Digraph &g,const LCapMap &lo, - const UCapMap &up,const DeltaMap &delta) - : _g(g), _node_num(), - _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false), - _level(0), _local_level(false), _excess(0), _el() {} + /// + /// \param graph The digraph the algorithm runs on. + /// \param lower The lower bounds for the flow values on the arcs. + /// \param upper The upper bounds (capacities) for the flow values + /// on the arcs. + /// \param supply The signed supply values of the nodes. + Circulation(const Digraph &graph, const LowerMap &lower, + const UpperMap &upper, const SupplyMap &supply) + : _g(graph), _lo(&lower), _up(&upper), _supply(&supply), + _flow(NULL), _local_flow(false), _level(NULL), _local_level(false), + _excess(NULL) {} /// Destructor. ~Circulation() { @@ -350,30 +367,30 @@ public: - /// Sets the lower bound capacity map. + /// Sets the lower bound map. - /// Sets the lower bound capacity map. + /// Sets the lower bound map. /// \return (*this) - Circulation& lowerCapMap(const LCapMap& map) { + Circulation& lowerMap(const LowerMap& map) { _lo = ↦ return *this; } - /// Sets the upper bound capacity map. + /// Sets the upper bound (capacity) map. - /// Sets the upper bound capacity map. + /// Sets the upper bound (capacity) map. /// \return (*this) - Circulation& upperCapMap(const LCapMap& map) { + Circulation& upperMap(const LowerMap& map) { _up = ↦ return *this; } - /// Sets the lower bound map for the supply of the nodes. + /// Sets the supply map. - /// Sets the lower bound map for the supply of the nodes. + /// Sets the supply map. /// \return (*this) - Circulation& deltaMap(const DeltaMap& map) { - _delta = ↦ + Circulation& supplyMap(const SupplyMap& map) { + _supply = ↦ return *this; } @@ -453,7 +470,7 @@ createStructures(); for(NodeIt n(_g);n!=INVALID;++n) { - (*_excess)[n] = (*_delta)[n]; + (*_excess)[n] = (*_supply)[n]; } for (ArcIt e(_g);e!=INVALID;++e) { @@ -482,7 +499,7 @@ createStructures(); for(NodeIt n(_g);n!=INVALID;++n) { - (*_excess)[n] = (*_delta)[n]; + (*_excess)[n] = (*_supply)[n]; } for (ArcIt e(_g);e!=INVALID;++e) { @@ -495,7 +512,7 @@ (*_excess)[_g.target(e)] += (*_lo)[e]; (*_excess)[_g.source(e)] -= (*_lo)[e]; } else { - Value fc = -(*_excess)[_g.target(e)]; + Flow fc = -(*_excess)[_g.target(e)]; _flow->set(e, fc); (*_excess)[_g.target(e)] = 0; (*_excess)[_g.source(e)] -= fc; @@ -528,11 +545,11 @@ while((act=_level->highestActive())!=INVALID) { int actlevel=(*_level)[act]; int mlevel=_node_num; - Value exc=(*_excess)[act]; + Flow exc=(*_excess)[act]; for(OutArcIt e(_g,act);e!=INVALID; ++e) { Node v = _g.target(e); - Value fc=(*_up)[e]-(*_flow)[e]; + Flow fc=(*_up)[e]-(*_flow)[e]; if(!_tol.positive(fc)) continue; if((*_level)[v](*_up)[e]) return false; for(NodeIt n(_g);n!=INVALID;++n) { - Value dif=-(*_delta)[n]; + Flow dif=-(*_supply)[n]; for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e]; for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e]; if(_tol.negative(dif)) return false; @@ -730,10 +747,10 @@ ///\sa barrierMap() bool checkBarrier() const { - Value delta=0; + Flow delta=0; for(NodeIt n(_g);n!=INVALID;++n) if(barrier(n)) - delta-=(*_delta)[n]; + delta-=(*_supply)[n]; for(ArcIt e(_g);e!=INVALID;++e) { Node s=_g.source(e); diff --git a/lemon/network_simplex.h b/lemon/network_simplex.h new file mode 100644 --- /dev/null +++ b/lemon/network_simplex.h @@ -0,0 +1,1582 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#ifndef LEMON_NETWORK_SIMPLEX_H +#define LEMON_NETWORK_SIMPLEX_H + +/// \ingroup min_cost_flow +/// +/// \file +/// \brief Network Simplex algorithm for finding a minimum cost flow. + +#include +#include +#include + +#include +#include +#include +#include +#include + +namespace lemon { + + /// \addtogroup min_cost_flow + /// @{ + + /// \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 + /// for finding a \ref min_cost_flow "minimum cost flow". + /// This algorithm is a specialized version of the linear programming + /// simplex method directly for the minimum cost flow problem. + /// It is one of the most efficient solution methods. + /// + /// In general this class is the fastest implementation available + /// in LEMON for the minimum cost flow problem. + /// Moreover it supports both direction of the supply/demand inequality + /// constraints. For more information see \ref ProblemType. + /// + /// \tparam GR The digraph type the algorithm runs on. + /// \tparam F The value type used for flow amounts, capacity bounds + /// and supply values in the algorithm. By default it is \c int. + /// \tparam C The value type used for costs and potentials in the + /// algorithm. By default it is the same as \c F. + /// + /// \warning Both value types must be signed and all input data must + /// be integer. + /// + /// \note %NetworkSimplex provides five different pivot rule + /// implementations, from which the most efficient one is used + /// by default. For more information see \ref PivotRule. + template + class NetworkSimplex + { + public: + + /// The flow type of the algorithm + typedef F Flow; + /// The cost type of the algorithm + typedef C Cost; +#ifdef DOXYGEN + /// The type of the flow map + typedef GR::ArcMap FlowMap; + /// The type of the potential map + typedef GR::NodeMap PotentialMap; +#else + /// The type of the flow map + typedef typename GR::template ArcMap FlowMap; + /// The type of the potential map + typedef typename GR::template NodeMap PotentialMap; +#endif + + 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 + }; + + /// \brief Enum type for selecting the problem type. + /// + /// Enum type for selecting the problem type, i.e. the direction of + /// the inequalities in the supply/demand constraints of the + /// \ref min_cost_flow "minimum cost flow problem". + /// + /// The default problem type is \c GEQ, since this form is supported + /// by other minimum cost flow algorithms and the \ref Circulation + /// algorithm as well. + /// The \c LEQ problem type can be selected using the \ref problemType() + /// function. + /// + /// Note that the equality form is a special case of both problem type. + enum ProblemType { + + /// This option means that there are "greater or equal" + /// constraints in the defintion, i.e. the exact formulation of the + /// problem is the following. + /** + \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] + \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \geq + sup(u) \quad \forall u\in V \f] + \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] + */ + /// It means that the total demand must be greater or equal to the + /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or + /// negative) and all the supplies have to be carried out from + /// the supply nodes, but there could be demands that are not + /// satisfied. + GEQ, + /// It is just an alias for the \c GEQ option. + CARRY_SUPPLIES = GEQ, + + /// This option means that there are "less or equal" + /// constraints in the defintion, i.e. the exact formulation of the + /// problem is the following. + /** + \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f] + \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \leq + sup(u) \quad \forall u\in V \f] + \f[ lower(uv) \leq f(uv) \leq upper(uv) \quad \forall uv\in A \f] + */ + /// It means that the total demand must be less or equal to the + /// total supply (i.e. \f$\sum_{u\in V} sup(u)\f$ must be zero or + /// positive) and all the demands have to be satisfied, but there + /// could be supplies that are not carried out from the supply + /// nodes. + LEQ, + /// It is just an alias for the \c LEQ option. + SATISFY_DEMANDS = LEQ + }; + + private: + + TEMPLATE_DIGRAPH_TYPEDEFS(GR); + + typedef typename GR::template ArcMap FlowArcMap; + typedef typename GR::template ArcMap CostArcMap; + typedef typename GR::template NodeMap FlowNodeMap; + + typedef std::vector ArcVector; + typedef std::vector NodeVector; + typedef std::vector IntVector; + typedef std::vector BoolVector; + typedef std::vector FlowVector; + typedef std::vector CostVector; + + // State constants for arcs + enum ArcStateEnum { + STATE_UPPER = -1, + STATE_TREE = 0, + STATE_LOWER = 1 + }; + + private: + + // Data related to the underlying digraph + const GR &_graph; + int _node_num; + int _arc_num; + + // Parameters of the problem + FlowArcMap *_plower; + FlowArcMap *_pupper; + CostArcMap *_pcost; + FlowNodeMap *_psupply; + bool _pstsup; + Node _psource, _ptarget; + Flow _pstflow; + ProblemType _ptype; + + // Result maps + FlowMap *_flow_map; + PotentialMap *_potential_map; + bool _local_flow; + bool _local_potential; + + // Data structures for storing the digraph + IntNodeMap _node_id; + ArcVector _arc_ref; + IntVector _source; + IntVector _target; + + // Node and arc data + FlowVector _cap; + CostVector _cost; + FlowVector _supply; + FlowVector _flow; + CostVector _pi; + + // Data for storing the spanning tree structure + IntVector _parent; + IntVector _pred; + IntVector _thread; + IntVector _rev_thread; + IntVector _succ_num; + IntVector _last_succ; + IntVector _dirty_revs; + BoolVector _forward; + IntVector _state; + int _root; + + // Temporary data used in the current pivot iteration + int in_arc, join, u_in, v_in, u_out, v_out; + int first, second, right, last; + int stem, par_stem, new_stem; + Flow delta; + + private: + + // Implementation of the First Eligible pivot rule + class FirstEligiblePivotRule + { + private: + + // References to the NetworkSimplex class + const IntVector &_source; + const IntVector &_target; + const CostVector &_cost; + const IntVector &_state; + const CostVector &_pi; + int &_in_arc; + int _arc_num; + + // Pivot rule data + int _next_arc; + + public: + + // 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 + bool findEnteringArc() { + Cost c; + for (int e = _next_arc; e < _arc_num; ++e) { + c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); + if (c < 0) { + _in_arc = e; + _next_arc = e + 1; + return true; + } + } + for (int e = 0; e < _next_arc; ++e) { + c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); + if (c < 0) { + _in_arc = e; + _next_arc = e + 1; + return true; + } + } + return false; + } + + }; //class FirstEligiblePivotRule + + + // Implementation of the Best Eligible pivot rule + class BestEligiblePivotRule + { + private: + + // References to the NetworkSimplex class + const IntVector &_source; + const IntVector &_target; + const CostVector &_cost; + const IntVector &_state; + const CostVector &_pi; + int &_in_arc; + int _arc_num; + + public: + + // 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 + bool findEnteringArc() { + Cost 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) { + min = c; + _in_arc = e; + } + } + return min < 0; + } + + }; //class BestEligiblePivotRule + + + // Implementation of the Block Search pivot rule + class BlockSearchPivotRule + { + private: + + // References to the NetworkSimplex class + const IntVector &_source; + const IntVector &_target; + const CostVector &_cost; + const IntVector &_state; + const CostVector &_pi; + int &_in_arc; + int _arc_num; + + // Pivot rule data + int _block_size; + int _next_arc; + + public: + + // Constructor + BlockSearchPivotRule(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) + { + // The main parameters of the pivot rule + const double BLOCK_SIZE_FACTOR = 2.0; + const int MIN_BLOCK_SIZE = 10; + + _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_arc_num)), + MIN_BLOCK_SIZE ); + } + + // Find next entering arc + bool findEnteringArc() { + Cost c, min = 0; + int cnt = _block_size; + int e, min_arc = _next_arc; + for (e = _next_arc; e < _arc_num; ++e) { + c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); + if (c < min) { + min = c; + min_arc = e; + } + if (--cnt == 0) { + if (min < 0) break; + cnt = _block_size; + } + } + if (min == 0 || cnt > 0) { + for (e = 0; e < _next_arc; ++e) { + c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); + if (c < min) { + min = c; + min_arc = e; + } + if (--cnt == 0) { + if (min < 0) break; + cnt = _block_size; + } + } + } + if (min >= 0) return false; + _in_arc = min_arc; + _next_arc = e; + return true; + } + + }; //class BlockSearchPivotRule + + + // Implementation of the Candidate List pivot rule + class CandidateListPivotRule + { + private: + + // References to the NetworkSimplex class + const IntVector &_source; + const IntVector &_target; + const CostVector &_cost; + const IntVector &_state; + const CostVector &_pi; + int &_in_arc; + int _arc_num; + + // Pivot rule data + IntVector _candidates; + int _list_length, _minor_limit; + int _curr_length, _minor_count; + int _next_arc; + + public: + + /// Constructor + CandidateListPivotRule(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) + { + // The main parameters of the pivot rule + const double LIST_LENGTH_FACTOR = 1.0; + const int MIN_LIST_LENGTH = 10; + const double MINOR_LIMIT_FACTOR = 0.1; + const int MIN_MINOR_LIMIT = 3; + + _list_length = std::max( int(LIST_LENGTH_FACTOR * sqrt(_arc_num)), + MIN_LIST_LENGTH ); + _minor_limit = std::max( int(MINOR_LIMIT_FACTOR * _list_length), + MIN_MINOR_LIMIT ); + _curr_length = _minor_count = 0; + _candidates.resize(_list_length); + } + + /// Find next entering arc + bool findEnteringArc() { + Cost 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 + // current candidate list + ++_minor_count; + min = 0; + for (int i = 0; i < _curr_length; ++i) { + e = _candidates[i]; + c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); + if (c < min) { + min = c; + min_arc = e; + } + if (c >= 0) { + _candidates[i--] = _candidates[--_curr_length]; + } + } + if (min < 0) { + _in_arc = min_arc; + return true; + } + } + + // Major iteration: build a new candidate list + min = 0; + _curr_length = 0; + for (e = _next_arc; e < _arc_num; ++e) { + c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); + if (c < 0) { + _candidates[_curr_length++] = e; + if (c < min) { + min = c; + min_arc = e; + } + if (_curr_length == _list_length) break; + } + } + if (_curr_length < _list_length) { + for (e = 0; e < _next_arc; ++e) { + c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); + if (c < 0) { + _candidates[_curr_length++] = e; + if (c < min) { + min = c; + min_arc = e; + } + if (_curr_length == _list_length) break; + } + } + } + if (_curr_length == 0) return false; + _minor_count = 1; + _in_arc = min_arc; + _next_arc = e; + return true; + } + + }; //class CandidateListPivotRule + + + // Implementation of the Altering Candidate List pivot rule + class AlteringListPivotRule + { + private: + + // References to the NetworkSimplex class + const IntVector &_source; + const IntVector &_target; + const CostVector &_cost; + const IntVector &_state; + const CostVector &_pi; + int &_in_arc; + int _arc_num; + + // Pivot rule data + int _block_size, _head_length, _curr_length; + int _next_arc; + IntVector _candidates; + CostVector _cand_cost; + + // Functor class to compare arcs during sort of the candidate list + class SortFunc + { + private: + const CostVector &_map; + public: + SortFunc(const CostVector &map) : _map(map) {} + bool operator()(int left, int right) { + return _map[left] > _map[right]; + } + }; + + SortFunc _sort_func; + + public: + + // Constructor + AlteringListPivotRule(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), _cand_cost(ns._arc_num), _sort_func(_cand_cost) + { + // The main parameters of the pivot rule + const double BLOCK_SIZE_FACTOR = 1.5; + const int MIN_BLOCK_SIZE = 10; + const double HEAD_LENGTH_FACTOR = 0.1; + const int MIN_HEAD_LENGTH = 3; + + _block_size = std::max( int(BLOCK_SIZE_FACTOR * sqrt(_arc_num)), + MIN_BLOCK_SIZE ); + _head_length = std::max( int(HEAD_LENGTH_FACTOR * _block_size), + MIN_HEAD_LENGTH ); + _candidates.resize(_head_length + _block_size); + _curr_length = 0; + } + + // Find next entering arc + bool findEnteringArc() { + // Check the current candidate list + int e; + for (int i = 0; i < _curr_length; ++i) { + e = _candidates[i]; + _cand_cost[e] = _state[e] * + (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); + if (_cand_cost[e] >= 0) { + _candidates[i--] = _candidates[--_curr_length]; + } + } + + // Extend the list + int cnt = _block_size; + int last_arc = 0; + int limit = _head_length; + + for (int e = _next_arc; e < _arc_num; ++e) { + _cand_cost[e] = _state[e] * + (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); + if (_cand_cost[e] < 0) { + _candidates[_curr_length++] = e; + last_arc = e; + } + if (--cnt == 0) { + if (_curr_length > limit) break; + limit = 0; + cnt = _block_size; + } + } + if (_curr_length <= limit) { + for (int e = 0; e < _next_arc; ++e) { + _cand_cost[e] = _state[e] * + (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); + if (_cand_cost[e] < 0) { + _candidates[_curr_length++] = e; + last_arc = e; + } + if (--cnt == 0) { + if (_curr_length > limit) break; + limit = 0; + cnt = _block_size; + } + } + } + if (_curr_length == 0) return false; + _next_arc = last_arc + 1; + + // Make heap of the candidate list (approximating a partial sort) + make_heap( _candidates.begin(), _candidates.begin() + _curr_length, + _sort_func ); + + // Pop the first element of the heap + _in_arc = _candidates[0]; + pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, + _sort_func ); + _curr_length = std::min(_head_length, _curr_length - 1); + return true; + } + + }; //class AlteringListPivotRule + + public: + + /// \brief Constructor. + /// + /// The constructor of the class. + /// + /// \param graph The digraph the algorithm runs on. + NetworkSimplex(const GR& graph) : + _graph(graph), + _plower(NULL), _pupper(NULL), _pcost(NULL), + _psupply(NULL), _pstsup(false), _ptype(GEQ), + _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 flow type of NetworkSimplex must be signed integer"); + LEMON_ASSERT(std::numeric_limits::is_integer && + std::numeric_limits::is_signed, + "The cost type of NetworkSimplex must be signed integer"); + } + + /// Destructor. + ~NetworkSimplex() { + if (_local_flow) delete _flow_map; + if (_local_potential) delete _potential_map; + } + + /// \name Parameters + /// The parameters of the algorithm can be specified using these + /// functions. + + /// @{ + + /// \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 Flow type + /// of the algorithm. + /// + /// \return (*this) + template + NetworkSimplex& lowerMap(const LOWER& map) { + delete _plower; + _plower = new FlowArcMap(_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 Flow type + /// of the algorithm. + /// + /// \return (*this) + template + NetworkSimplex& upperMap(const UPPER& map) { + delete _pupper; + _pupper = new FlowArcMap(_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 Flow 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 Cost type + /// of the algorithm. + /// + /// \return (*this) + template + NetworkSimplex& costMap(const COST& map) { + delete _pcost; + _pcost = new CostArcMap(_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 Flow type + /// of the algorithm. + /// + /// \return (*this) + template + NetworkSimplex& supplyMap(const SUP& map) { + delete _psupply; + _pstsup = false; + _psupply = new FlowNodeMap(_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, Flow k) { + delete _psupply; + _psupply = NULL; + _pstsup = true; + _psource = s; + _ptarget = t; + _pstflow = k; + return *this; + } + + /// \brief Set the problem type. + /// + /// This function sets the problem type for the algorithm. + /// If it is not used before calling \ref run(), the \ref GEQ problem + /// type will be used. + /// + /// For more information see \ref ProblemType. + /// + /// \return (*this) + NetworkSimplex& problemType(ProblemType problem_type) { + _ptype = problem_type; + 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) { + if (_local_flow) { + delete _flow_map; + _local_flow = false; + } + _flow_map = ↦ + return *this; + } + + /// \brief Set 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) { + if (_local_potential) { + delete _potential_map; + _local_potential = false; + } + _potential_map = ↦ + return *this; + } + + /// @} + + /// \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 functions \ref lowerMap(), + /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(), + /// \ref costMap(), \ref supplyMap(), \ref stSupply(), + /// \ref problemType(), \ref flowMap() and \ref potentialMap(). + /// For example, + /// \code + /// NetworkSimplex ns(graph); + /// ns.boundMaps(lower, upper).costMap(cost) + /// .supplyMap(sup).run(); + /// \endcode + /// + /// This function can be called more than once. All the parameters + /// that have been given are kept for the next call, unless + /// \ref reset() is called, thus only the modified parameters + /// have to be set again. See \ref reset() for examples. + /// + /// \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(PivotRule pivot_rule = BLOCK_SEARCH) { + return init() && start(pivot_rule); + } + + /// \brief Reset all the parameters that have been given before. + /// + /// This function resets all the paramaters that have been given + /// before using functions \ref lowerMap(), \ref upperMap(), + /// \ref capacityMap(), \ref boundMaps(), \ref costMap(), + /// \ref supplyMap(), \ref stSupply(), \ref problemType(), + /// \ref flowMap() and \ref potentialMap(). + /// + /// It is useful for multiple run() calls. If this function is not + /// used, all the parameters given before are kept for the next + /// \ref run() call. + /// + /// For example, + /// \code + /// NetworkSimplex ns(graph); + /// + /// // First run + /// ns.lowerMap(lower).capacityMap(cap).costMap(cost) + /// .supplyMap(sup).run(); + /// + /// // Run again with modified cost map (reset() is not called, + /// // so only the cost map have to be set again) + /// cost[e] += 100; + /// ns.costMap(cost).run(); + /// + /// // Run again from scratch using reset() + /// // (the lower bounds will be set to zero on all arcs) + /// ns.reset(); + /// ns.capacityMap(cap).costMap(cost) + /// .supplyMap(sup).run(); + /// \endcode + /// + /// \return (*this) + NetworkSimplex& reset() { + delete _plower; + delete _pupper; + delete _pcost; + delete _psupply; + _plower = NULL; + _pupper = NULL; + _pcost = NULL; + _psupply = NULL; + _pstsup = false; + _ptype = GEQ; + if (_local_flow) delete _flow_map; + if (_local_potential) delete _potential_map; + _flow_map = NULL; + _potential_map = NULL; + _local_flow = false; + _local_potential = false; + + return *this; + } + + /// @} + + /// \name Query Functions + /// The results of the algorithm can be obtained using these + /// functions.\n + /// 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 O(e). + /// + /// \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 Cost + /// 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 + Cost 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. + Flow 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 + /// the found flow. + /// + /// \pre \ref run() must be called before using this function. + const FlowMap& flowMap() const { + 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. + Cost 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, 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; + } + + /// @} + + private: + + // Initialize internal data structures + bool init() { + // Initialize result maps + if (!_flow_map) { + _flow_map = new FlowMap(_graph); + _local_flow = true; + } + if (!_potential_map) { + _potential_map = new PotentialMap(_graph); + _local_potential = true; + } + + // Initialize vectors + _node_num = countNodes(_graph); + _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); + _target.resize(all_arc_num); + + _cap.resize(all_arc_num); + _cost.resize(all_arc_num); + _supply.resize(all_node_num); + _flow.resize(all_arc_num); + _pi.resize(all_node_num); + + _parent.resize(all_node_num); + _pred.resize(all_node_num); + _forward.resize(all_node_num); + _thread.resize(all_node_num); + _rev_thread.resize(all_node_num); + _succ_num.resize(all_node_num); + _last_succ.resize(all_node_num); + _state.resize(all_arc_num); + + // Initialize node related data + bool valid_supply = true; + Flow sum_supply = 0; + if (!_pstsup && !_psupply) { + _pstsup = true; + _psource = _ptarget = NodeIt(_graph); + _pstflow = 0; + } + if (_psupply) { + int i = 0; + for (NodeIt n(_graph); n != INVALID; ++n, ++i) { + _node_id[n] = i; + _supply[i] = (*_psupply)[n]; + sum_supply += _supply[i]; + } + valid_supply = (_ptype == GEQ && sum_supply <= 0) || + (_ptype == LEQ && sum_supply >= 0); + } else { + int i = 0; + for (NodeIt n(_graph); n != INVALID; ++n, ++i) { + _node_id[n] = i; + _supply[i] = 0; + } + _supply[_node_id[_psource]] = _pstflow; + _supply[_node_id[_ptarget]] = -_pstflow; + } + if (!valid_supply) return false; + + // Infinite capacity value + Flow inf_cap = + std::numeric_limits::has_infinity ? + std::numeric_limits::infinity() : + std::numeric_limits::max(); + + // Initialize artifical cost + Cost art_cost; + if (std::numeric_limits::is_exact) { + art_cost = std::numeric_limits::max() / 4 + 1; + } else { + art_cost = std::numeric_limits::min(); + for (int i = 0; i != _arc_num; ++i) { + if (_cost[i] > art_cost) art_cost = _cost[i]; + } + art_cost = (art_cost + 1) * _node_num; + } + + // Run Circulation to check if a feasible solution exists + typedef ConstMap ConstArcMap; + FlowNodeMap *csup = NULL; + bool local_csup = false; + if (_psupply) { + csup = _psupply; + } else { + csup = new FlowNodeMap(_graph, 0); + (*csup)[_psource] = _pstflow; + (*csup)[_ptarget] = -_pstflow; + local_csup = true; + } + bool circ_result = false; + if (_ptype == GEQ || (_ptype == LEQ && sum_supply == 0)) { + // GEQ problem type + if (_plower) { + if (_pupper) { + Circulation + circ(_graph, *_plower, *_pupper, *csup); + circ_result = circ.run(); + } else { + Circulation + circ(_graph, *_plower, ConstArcMap(inf_cap), *csup); + circ_result = circ.run(); + } + } else { + if (_pupper) { + Circulation + circ(_graph, ConstArcMap(0), *_pupper, *csup); + circ_result = circ.run(); + } else { + Circulation + circ(_graph, ConstArcMap(0), ConstArcMap(inf_cap), *csup); + circ_result = circ.run(); + } + } + } else { + // LEQ problem type + typedef ReverseDigraph RevGraph; + typedef NegMap NegNodeMap; + RevGraph rgraph(_graph); + NegNodeMap neg_csup(*csup); + if (_plower) { + if (_pupper) { + Circulation + circ(rgraph, *_plower, *_pupper, neg_csup); + circ_result = circ.run(); + } else { + Circulation + circ(rgraph, *_plower, ConstArcMap(inf_cap), neg_csup); + circ_result = circ.run(); + } + } else { + if (_pupper) { + Circulation + circ(rgraph, ConstArcMap(0), *_pupper, neg_csup); + circ_result = circ.run(); + } else { + Circulation + circ(rgraph, ConstArcMap(0), ConstArcMap(inf_cap), neg_csup); + circ_result = circ.run(); + } + } + } + if (local_csup) delete csup; + if (!circ_result) return false; + + // Set data for the artificial root node + _root = _node_num; + _parent[_root] = -1; + _pred[_root] = -1; + _thread[_root] = 0; + _rev_thread[0] = _root; + _succ_num[_root] = all_node_num; + _last_succ[_root] = _root - 1; + _supply[_root] = -sum_supply; + if (sum_supply < 0) { + _pi[_root] = -art_cost; + } else { + _pi[_root] = art_cost; + } + + // Store the arcs in a mixed order + int k = std::max(int(sqrt(_arc_num)), 10); + int i = 0; + for (ArcIt e(_graph); e != INVALID; ++e) { + _arc_ref[i] = e; + if ((i += k) >= _arc_num) i = (i % k) + 1; + } + + // Initialize arc maps + 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]; + _flow[i] = 0; + _state[i] = STATE_LOWER; + } + } 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)]; + _flow[i] = 0; + _state[i] = STATE_LOWER; + } + if (_pupper) { + for (int i = 0; i != _arc_num; ++i) + _cap[i] = (*_pupper)[_arc_ref[i]]; + } else { + for (int i = 0; i != _arc_num; ++i) + _cap[i] = inf_cap; + } + 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 (_plower) { + for (int i = 0; i != _arc_num; ++i) { + Flow c = (*_plower)[_arc_ref[i]]; + if (c != 0) { + _cap[i] -= c; + _supply[_source[i]] -= c; + _supply[_target[i]] += c; + } + } + } + + // Add artificial arcs and initialize the spanning tree data structure + for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) { + _thread[u] = u + 1; + _rev_thread[u + 1] = u; + _succ_num[u] = 1; + _last_succ[u] = u; + _parent[u] = _root; + _pred[u] = e; + _cost[e] = art_cost; + _cap[e] = inf_cap; + _state[e] = STATE_TREE; + if (_supply[u] > 0 || (_supply[u] == 0 && sum_supply <= 0)) { + _flow[e] = _supply[u]; + _forward[u] = true; + _pi[u] = -art_cost + _pi[_root]; + } else { + _flow[e] = -_supply[u]; + _forward[u] = false; + _pi[u] = art_cost + _pi[_root]; + } + } + + return true; + } + + // Find the join node + void findJoinNode() { + int u = _source[in_arc]; + int v = _target[in_arc]; + while (u != v) { + if (_succ_num[u] < _succ_num[v]) { + u = _parent[u]; + } else { + v = _parent[v]; + } + } + join = u; + } + + // Find the leaving arc of the cycle and returns true if the + // leaving arc is not the same as the entering arc + bool findLeavingArc() { + // Initialize first and second nodes according to the direction + // of the cycle + if (_state[in_arc] == STATE_LOWER) { + first = _source[in_arc]; + second = _target[in_arc]; + } else { + first = _target[in_arc]; + second = _source[in_arc]; + } + delta = _cap[in_arc]; + int result = 0; + Flow d; + int e; + + // Search the cycle along the path form the first node to the root + for (int u = first; u != join; u = _parent[u]) { + e = _pred[u]; + d = _forward[u] ? _flow[e] : _cap[e] - _flow[e]; + if (d < delta) { + delta = d; + u_out = u; + result = 1; + } + } + // Search the cycle along the path form the second node to the root + for (int u = second; u != join; u = _parent[u]) { + e = _pred[u]; + d = _forward[u] ? _cap[e] - _flow[e] : _flow[e]; + if (d <= delta) { + delta = d; + u_out = u; + result = 2; + } + } + + if (result == 1) { + u_in = first; + v_in = second; + } else { + u_in = second; + v_in = first; + } + return result != 0; + } + + // Change _flow and _state vectors + void changeFlow(bool change) { + // Augment along the cycle + if (delta > 0) { + Flow 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; + } + for (int u = _target[in_arc]; u != join; u = _parent[u]) { + _flow[_pred[u]] += _forward[u] ? val : -val; + } + } + // Update the state of the entering and leaving arcs + if (change) { + _state[in_arc] = STATE_TREE; + _state[_pred[u_out]] = + (_flow[_pred[u_out]] == 0) ? STATE_LOWER : STATE_UPPER; + } else { + _state[in_arc] = -_state[in_arc]; + } + } + + // Update the tree structure + void updateTreeStructure() { + int u, w; + int old_rev_thread = _rev_thread[u_out]; + int old_succ_num = _succ_num[u_out]; + int old_last_succ = _last_succ[u_out]; + v_out = _parent[u_out]; + + u = _last_succ[u_in]; // the last successor of u_in + right = _thread[u]; // the node after it + + // Handle the case when old_rev_thread equals to v_in + // (it also means that join and v_out coincide) + if (old_rev_thread == v_in) { + last = _thread[_last_succ[u_out]]; + } else { + last = _thread[v_in]; + } + + // Update _thread and _parent along the stem nodes (i.e. the nodes + // between u_in and u_out, whose parent have to be changed) + _thread[v_in] = stem = u_in; + _dirty_revs.clear(); + _dirty_revs.push_back(v_in); + par_stem = v_in; + while (stem != u_out) { + // Insert the next stem node into the thread list + new_stem = _parent[stem]; + _thread[u] = new_stem; + _dirty_revs.push_back(u); + + // Remove the subtree of stem from the thread list + w = _rev_thread[stem]; + _thread[w] = right; + _rev_thread[right] = w; + + // Change the parent node and shift stem nodes + _parent[stem] = par_stem; + par_stem = stem; + stem = new_stem; + + // Update u and right + u = _last_succ[stem] == _last_succ[par_stem] ? + _rev_thread[par_stem] : _last_succ[stem]; + right = _thread[u]; + } + _parent[u_out] = par_stem; + _thread[u] = last; + _rev_thread[last] = u; + _last_succ[u_out] = u; + + // Remove the subtree of u_out from the thread list except for + // the case when old_rev_thread equals to v_in + // (it also means that join and v_out coincide) + if (old_rev_thread != v_in) { + _thread[old_rev_thread] = right; + _rev_thread[right] = old_rev_thread; + } + + // Update _rev_thread using the new _thread values + for (int i = 0; i < int(_dirty_revs.size()); ++i) { + u = _dirty_revs[i]; + _rev_thread[_thread[u]] = u; + } + + // Update _pred, _forward, _last_succ and _succ_num for the + // stem nodes from u_out to u_in + int tmp_sc = 0, tmp_ls = _last_succ[u_out]; + u = u_out; + while (u != u_in) { + w = _parent[u]; + _pred[u] = _pred[w]; + _forward[u] = !_forward[w]; + tmp_sc += _succ_num[u] - _succ_num[w]; + _succ_num[u] = tmp_sc; + _last_succ[w] = tmp_ls; + u = w; + } + _pred[u_in] = in_arc; + _forward[u_in] = (u_in == _source[in_arc]); + _succ_num[u_in] = old_succ_num; + + // Set limits for updating _last_succ form v_in and v_out + // towards the root + int up_limit_in = -1; + int up_limit_out = -1; + if (_last_succ[join] == v_in) { + up_limit_out = join; + } else { + up_limit_in = join; + } + + // Update _last_succ from v_in towards the root + for (u = v_in; u != up_limit_in && _last_succ[u] == v_in; + u = _parent[u]) { + _last_succ[u] = _last_succ[u_out]; + } + // Update _last_succ from v_out towards the root + if (join != old_rev_thread && v_in != old_rev_thread) { + for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; + u = _parent[u]) { + _last_succ[u] = old_rev_thread; + } + } else { + for (u = v_out; u != up_limit_out && _last_succ[u] == old_last_succ; + u = _parent[u]) { + _last_succ[u] = _last_succ[u_out]; + } + } + + // Update _succ_num from v_in to join + for (u = v_in; u != join; u = _parent[u]) { + _succ_num[u] += old_succ_num; + } + // Update _succ_num from v_out to join + for (u = v_out; u != join; u = _parent[u]) { + _succ_num[u] -= old_succ_num; + } + } + + // Update potentials + void updatePotential() { + Cost sigma = _forward[u_in] ? + _pi[v_in] - _pi[u_in] - _cost[_pred[u_in]] : + _pi[v_in] - _pi[u_in] + _cost[_pred[u_in]]; + // Update potentials in the subtree, which has been moved + int end = _thread[_last_succ[u_in]]; + for (int u = u_in; u != end; u = _thread[u]) { + _pi[u] += sigma; + } + } + + // Execute the algorithm + bool start(PivotRule pivot_rule) { + // Select the pivot rule implementation + switch (pivot_rule) { + case FIRST_ELIGIBLE: + return start(); + case BEST_ELIGIBLE: + return start(); + case BLOCK_SEARCH: + return start(); + case CANDIDATE_LIST: + return start(); + case ALTERING_LIST: + return start(); + } + return false; + } + + template + bool start() { + PivotRuleImpl pivot(*this); + + // Execute the Network Simplex algorithm + while (pivot.findEnteringArc()) { + findJoinNode(); + bool change = findLeavingArc(); + changeFlow(change); + if (change) { + updateTreeStructure(); + updatePotential(); + } + } + + // Copy flow values to _flow_map + if (_plower) { + for (int i = 0; i != _arc_num; ++i) { + Arc e = _arc_ref[i]; + _flow_map->set(e, (*_plower)[e] + _flow[i]); + } + } else { + for (int i = 0; i != _arc_num; ++i) { + _flow_map->set(_arc_ref[i], _flow[i]); + } + } + // Copy potential values to _potential_map + for (NodeIt n(_graph); n != INVALID; ++n) { + _potential_map->set(n, _pi[_node_id[n]]); + } + + return true; + } + + }; //class NetworkSimplex + + ///@} + +} //namespace lemon + +#endif //LEMON_NETWORK_SIMPLEX_H diff --git a/lemon/preflow.h b/lemon/preflow.h --- a/lemon/preflow.h +++ b/lemon/preflow.h @@ -46,18 +46,18 @@ typedef CAP CapacityMap; /// \brief The type of the flow values. - typedef typename CapacityMap::Value Value; + typedef typename CapacityMap::Value Flow; /// \brief The type of the map that stores the flow values. /// /// The type of the map that stores the flow values. /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. - typedef typename Digraph::template ArcMap FlowMap; + typedef typename Digraph::template ArcMap FlowMap; /// \brief Instantiates a FlowMap. /// /// This function instantiates a \ref FlowMap. - /// \param digraph The digraph, to which we would like to define + /// \param digraph The digraph for which we would like to define /// the flow map. static FlowMap* createFlowMap(const Digraph& digraph) { return new FlowMap(digraph); @@ -74,7 +74,7 @@ /// \brief Instantiates an Elevator. /// /// This function instantiates an \ref Elevator. - /// \param digraph The digraph, to which we would like to define + /// \param digraph The digraph for which we would like to define /// the elevator. /// \param max_level The maximum level of the elevator. static Elevator* createElevator(const Digraph& digraph, int max_level) { @@ -84,7 +84,7 @@ /// \brief The tolerance used by the algorithm /// /// The tolerance used by the algorithm to handle inexact computation. - typedef lemon::Tolerance Tolerance; + typedef lemon::Tolerance Tolerance; }; @@ -125,7 +125,7 @@ ///The type of the capacity map. typedef typename Traits::CapacityMap CapacityMap; ///The type of the flow values. - typedef typename Traits::Value Value; + typedef typename Traits::Flow Flow; ///The type of the flow map. typedef typename Traits::FlowMap FlowMap; @@ -151,7 +151,7 @@ Elevator* _level; bool _local_level; - typedef typename Digraph::template NodeMap ExcessMap; + typedef typename Digraph::template NodeMap ExcessMap; ExcessMap* _excess; Tolerance _tolerance; @@ -470,7 +470,7 @@ } for (NodeIt n(_graph); n != INVALID; ++n) { - Value excess = 0; + Flow excess = 0; for (InArcIt e(_graph, n); e != INVALID; ++e) { excess += (*_flow)[e]; } @@ -519,7 +519,7 @@ _level->initFinish(); for (OutArcIt e(_graph, _source); e != INVALID; ++e) { - Value rem = (*_capacity)[e] - (*_flow)[e]; + Flow rem = (*_capacity)[e] - (*_flow)[e]; if (_tolerance.positive(rem)) { Node u = _graph.target(e); if ((*_level)[u] == _level->maxLevel()) continue; @@ -531,7 +531,7 @@ } } for (InArcIt e(_graph, _source); e != INVALID; ++e) { - Value rem = (*_flow)[e]; + Flow rem = (*_flow)[e]; if (_tolerance.positive(rem)) { Node v = _graph.source(e); if ((*_level)[v] == _level->maxLevel()) continue; @@ -564,11 +564,11 @@ int num = _node_num; while (num > 0 && n != INVALID) { - Value excess = (*_excess)[n]; + Flow excess = (*_excess)[n]; int new_level = _level->maxLevel(); for (OutArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_capacity)[e] - (*_flow)[e]; + Flow rem = (*_capacity)[e] - (*_flow)[e]; if (!_tolerance.positive(rem)) continue; Node v = _graph.target(e); if ((*_level)[v] < level) { @@ -591,7 +591,7 @@ } for (InArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_flow)[e]; + Flow rem = (*_flow)[e]; if (!_tolerance.positive(rem)) continue; Node v = _graph.source(e); if ((*_level)[v] < level) { @@ -637,11 +637,11 @@ num = _node_num * 20; while (num > 0 && n != INVALID) { - Value excess = (*_excess)[n]; + Flow excess = (*_excess)[n]; int new_level = _level->maxLevel(); for (OutArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_capacity)[e] - (*_flow)[e]; + Flow rem = (*_capacity)[e] - (*_flow)[e]; if (!_tolerance.positive(rem)) continue; Node v = _graph.target(e); if ((*_level)[v] < level) { @@ -664,7 +664,7 @@ } for (InArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_flow)[e]; + Flow rem = (*_flow)[e]; if (!_tolerance.positive(rem)) continue; Node v = _graph.source(e); if ((*_level)[v] < level) { @@ -778,12 +778,12 @@ Node n; while ((n = _level->highestActive()) != INVALID) { - Value excess = (*_excess)[n]; + Flow excess = (*_excess)[n]; int level = _level->highestActiveLevel(); int new_level = _level->maxLevel(); for (OutArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_capacity)[e] - (*_flow)[e]; + Flow rem = (*_capacity)[e] - (*_flow)[e]; if (!_tolerance.positive(rem)) continue; Node v = _graph.target(e); if ((*_level)[v] < level) { @@ -806,7 +806,7 @@ } for (InArcIt e(_graph, n); e != INVALID; ++e) { - Value rem = (*_flow)[e]; + Flow rem = (*_flow)[e]; if (!_tolerance.positive(rem)) continue; Node v = _graph.source(e); if ((*_level)[v] < level) { @@ -897,7 +897,7 @@ /// /// \pre Either \ref run() or \ref init() must be called before /// using this function. - Value flowValue() const { + Flow flowValue() const { return (*_excess)[_target]; } @@ -908,7 +908,7 @@ /// /// \pre Either \ref run() or \ref init() must be called before /// using this function. - Value flow(const Arc& arc) const { + Flow flow(const Arc& arc) const { return (*_flow)[arc]; } diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt --- a/test/CMakeLists.txt +++ b/test/CMakeLists.txt @@ -31,6 +31,7 @@ maps_test matching_test min_cost_arborescence_test + min_cost_flow_test path_test preflow_test radix_sort_test diff --git a/test/Makefile.am b/test/Makefile.am --- a/test/Makefile.am +++ b/test/Makefile.am @@ -27,6 +27,7 @@ test/maps_test \ test/matching_test \ test/min_cost_arborescence_test \ + test/min_cost_flow_test \ test/path_test \ test/preflow_test \ test/radix_sort_test \ @@ -72,6 +73,7 @@ test_mip_test_SOURCES = test/mip_test.cc test_matching_test_SOURCES = test/matching_test.cc test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc +test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc test_path_test_SOURCES = test/path_test.cc test_preflow_test_SOURCES = test/preflow_test.cc test_radix_sort_test_SOURCES = test/radix_sort_test.cc diff --git a/test/circulation_test.cc b/test/circulation_test.cc --- a/test/circulation_test.cc +++ b/test/circulation_test.cc @@ -57,7 +57,7 @@ typedef Digraph::Node Node; typedef Digraph::Arc Arc; typedef concepts::ReadMap CapMap; - typedef concepts::ReadMap DeltaMap; + typedef concepts::ReadMap SupplyMap; typedef concepts::ReadWriteMap FlowMap; typedef concepts::WriteMap BarrierMap; @@ -68,24 +68,24 @@ Node n; Arc a; CapMap lcap, ucap; - DeltaMap delta; + SupplyMap supply; FlowMap flow; BarrierMap bar; VType v; bool b; - typedef Circulation + typedef Circulation ::SetFlowMap ::SetElevator ::SetStandardElevator ::Create CirculationType; - CirculationType circ_test(g, lcap, ucap, delta); + CirculationType circ_test(g, lcap, ucap, supply); const CirculationType& const_circ_test = circ_test; circ_test - .lowerCapMap(lcap) - .upperCapMap(ucap) - .deltaMap(delta) + .lowerMap(lcap) + .upperMap(ucap) + .supplyMap(supply) .flowMap(flow); circ_test.init(); diff --git a/test/min_cost_flow_test.cc b/test/min_cost_flow_test.cc new file mode 100644 --- /dev/null +++ b/test/min_cost_flow_test.cc @@ -0,0 +1,339 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2009 + * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport + * (Egervary Research Group on Combinatorial Optimization, EGRES). + * + * Permission to use, modify and distribute this software is granted + * provided that this copyright notice appears in all copies. For + * precise terms see the accompanying LICENSE file. + * + * This software is provided "AS IS" with no warranty of any kind, + * express or implied, and with no claim as to its suitability for any + * purpose. + * + */ + +#include +#include + +#include +#include + +#include + +#include +#include + +#include "test_tools.h" + +using namespace lemon; + +char test_lgf[] = + "@nodes\n" + "label sup1 sup2 sup3 sup4 sup5\n" + " 1 20 27 0 20 30\n" + " 2 -4 0 0 -8 -3\n" + " 3 0 0 0 0 0\n" + " 4 0 0 0 0 0\n" + " 5 9 0 0 6 11\n" + " 6 -6 0 0 -5 -6\n" + " 7 0 0 0 0 0\n" + " 8 0 0 0 0 3\n" + " 9 3 0 0 0 0\n" + " 10 -2 0 0 -7 -2\n" + " 11 0 0 0 -10 0\n" + " 12 -20 -27 0 -30 -20\n" + "\n" + "@arcs\n" + " cost cap low1 low2\n" + " 1 2 70 11 0 8\n" + " 1 3 150 3 0 1\n" + " 1 4 80 15 0 2\n" + " 2 8 80 12 0 0\n" + " 3 5 140 5 0 3\n" + " 4 6 60 10 0 1\n" + " 4 7 80 2 0 0\n" + " 4 8 110 3 0 0\n" + " 5 7 60 14 0 0\n" + " 5 11 120 12 0 0\n" + " 6 3 0 3 0 0\n" + " 6 9 140 4 0 0\n" + " 6 10 90 8 0 0\n" + " 7 1 30 5 0 0\n" + " 8 12 60 16 0 4\n" + " 9 12 50 6 0 0\n" + "10 12 70 13 0 5\n" + "10 2 100 7 0 0\n" + "10 7 60 10 0 0\n" + "11 10 20 14 0 6\n" + "12 11 30 10 0 0\n" + "\n" + "@attributes\n" + "source 1\n" + "target 12\n"; + + +enum ProblemType { + EQ, + GEQ, + LEQ +}; + +// Check the interface of an MCF algorithm +template +class McfClassConcept +{ +public: + + template + struct Constraints { + void constraints() { + checkConcept(); + + MCF mcf(g); + + b = mcf.reset() + .lowerMap(lower) + .upperMap(upper) + .capacityMap(upper) + .boundMaps(lower, upper) + .costMap(cost) + .supplyMap(sup) + .stSupply(n, n, k) + .flowMap(flow) + .potentialMap(pot) + .run(); + + const MCF& const_mcf = mcf; + + const typename MCF::FlowMap &fm = const_mcf.flowMap(); + const typename MCF::PotentialMap &pm = const_mcf.potentialMap(); + + v = const_mcf.totalCost(); + double x = const_mcf.template totalCost(); + v = const_mcf.flow(a); + v = const_mcf.potential(n); + + ignore_unused_variable_warning(fm); + ignore_unused_variable_warning(pm); + ignore_unused_variable_warning(x); + } + + typedef typename GR::Node Node; + typedef typename GR::Arc Arc; + typedef concepts::ReadMap NM; + typedef concepts::ReadMap FAM; + typedef concepts::ReadMap CAM; + + const GR &g; + const FAM &lower; + const FAM &upper; + const CAM &cost; + const NM ⊃ + const Node &n; + const Arc &a; + const Flow &k; + Flow v; + bool b; + + typename MCF::FlowMap &flow; + typename MCF::PotentialMap &pot; + }; + +}; + + +// Check the feasibility of the given flow (primal soluiton) +template < typename GR, typename LM, typename UM, + typename SM, typename FM > +bool checkFlow( const GR& gr, const LM& lower, const UM& upper, + const SM& supply, const FM& flow, + ProblemType type = EQ ) +{ + TEMPLATE_DIGRAPH_TYPEDEFS(GR); + + for (ArcIt e(gr); e != INVALID; ++e) { + if (flow[e] < lower[e] || flow[e] > upper[e]) return false; + } + + for (NodeIt n(gr); n != INVALID; ++n) { + typename SM::Value sum = 0; + for (OutArcIt e(gr, n); e != INVALID; ++e) + sum += flow[e]; + for (InArcIt e(gr, n); e != INVALID; ++e) + sum -= flow[e]; + bool b = (type == EQ && sum == supply[n]) || + (type == GEQ && sum >= supply[n]) || + (type == LEQ && sum <= supply[n]); + if (!b) return false; + } + + return true; +} + +// Check the feasibility of the given potentials (dual soluiton) +// using the "Complementary Slackness" optimality condition +template < typename GR, typename LM, typename UM, + typename CM, typename SM, typename FM, typename PM > +bool checkPotential( const GR& gr, const LM& lower, const UM& upper, + const CM& cost, const SM& supply, const FM& flow, + const PM& pi ) +{ + TEMPLATE_DIGRAPH_TYPEDEFS(GR); + + bool opt = true; + for (ArcIt e(gr); opt && e != INVALID; ++e) { + typename CM::Value red_cost = + cost[e] + pi[gr.source(e)] - pi[gr.target(e)]; + opt = red_cost == 0 || + (red_cost > 0 && flow[e] == lower[e]) || + (red_cost < 0 && flow[e] == upper[e]); + } + + for (NodeIt n(gr); opt && n != INVALID; ++n) { + typename SM::Value sum = 0; + for (OutArcIt e(gr, n); e != INVALID; ++e) + sum += flow[e]; + for (InArcIt e(gr, n); e != INVALID; ++e) + sum -= flow[e]; + opt = (sum == supply[n]) || (pi[n] == 0); + } + + return opt; +} + +// Run a minimum cost flow algorithm and check the results +template < typename MCF, typename GR, + typename LM, typename UM, + typename CM, typename SM > +void checkMcf( const MCF& mcf, bool mcf_result, + const GR& gr, const LM& lower, const UM& upper, + const CM& cost, const SM& supply, + bool result, typename CM::Value total, + const std::string &test_id = "", + ProblemType type = EQ ) +{ + check(mcf_result == result, "Wrong result " + test_id); + if (result) { + check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type), + "The flow is not feasible " + test_id); + check(mcf.totalCost() == total, "The flow is not optimal " + test_id); + check(checkPotential(gr, lower, upper, cost, supply, mcf.flowMap(), + mcf.potentialMap()), + "Wrong potentials " + test_id); + } +} + +int main() +{ + // Check the interfaces + { + typedef int Flow; + typedef int Cost; + // 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; +/**/ + checkConcept< McfClassConcept, + NetworkSimplex >(); + } + + // Run various MCF tests + typedef ListDigraph Digraph; + DIGRAPH_TYPEDEFS(ListDigraph); + + // Read the test digraph + Digraph gr; + Digraph::ArcMap c(gr), l1(gr), l2(gr), u(gr); + Digraph::NodeMap s1(gr), s2(gr), s3(gr), s4(gr), s5(gr); + ConstMap cc(1), cu(std::numeric_limits::max()); + Node v, w; + + std::istringstream input(test_lgf); + DigraphReader(gr, input) + .arcMap("cost", c) + .arcMap("cap", u) + .arcMap("low1", l1) + .arcMap("low2", l2) + .nodeMap("sup1", s1) + .nodeMap("sup2", s2) + .nodeMap("sup3", s3) + .nodeMap("sup4", s4) + .nodeMap("sup5", s5) + .node("source", v) + .node("target", w) + .run(); + + // A. Test NetworkSimplex with the default pivot rule + { + NetworkSimplex mcf(gr); + + // Check the equality form + mcf.upperMap(u).costMap(c); + checkMcf(mcf, mcf.supplyMap(s1).run(), + gr, l1, u, c, s1, true, 5240, "#A1"); + checkMcf(mcf, mcf.stSupply(v, w, 27).run(), + gr, l1, u, c, s2, true, 7620, "#A2"); + mcf.lowerMap(l2); + checkMcf(mcf, mcf.supplyMap(s1).run(), + gr, l2, u, c, s1, true, 5970, "#A3"); + checkMcf(mcf, mcf.stSupply(v, w, 27).run(), + gr, l2, u, c, s2, true, 8010, "#A4"); + mcf.reset(); + checkMcf(mcf, mcf.supplyMap(s1).run(), + gr, l1, cu, cc, s1, true, 74, "#A5"); + checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(), + gr, l2, cu, cc, s2, true, 94, "#A6"); + mcf.reset(); + checkMcf(mcf, mcf.run(), + gr, l1, cu, cc, s3, true, 0, "#A7"); + checkMcf(mcf, mcf.boundMaps(l2, u).run(), + gr, l2, u, cc, s3, false, 0, "#A8"); + + // Check the GEQ form + mcf.reset().upperMap(u).costMap(c).supplyMap(s4); + checkMcf(mcf, mcf.run(), + gr, l1, u, c, s4, true, 3530, "#A9", GEQ); + mcf.problemType(mcf.GEQ); + checkMcf(mcf, mcf.lowerMap(l2).run(), + gr, l2, u, c, s4, true, 4540, "#A10", GEQ); + mcf.problemType(mcf.CARRY_SUPPLIES).supplyMap(s5); + checkMcf(mcf, mcf.run(), + gr, l2, u, c, s5, false, 0, "#A11", GEQ); + + // Check the LEQ form + mcf.reset().problemType(mcf.LEQ); + mcf.upperMap(u).costMap(c).supplyMap(s5); + checkMcf(mcf, mcf.run(), + gr, l1, u, c, s5, true, 5080, "#A12", LEQ); + checkMcf(mcf, mcf.lowerMap(l2).run(), + gr, l2, u, c, s5, true, 5930, "#A13", LEQ); + mcf.problemType(mcf.SATISFY_DEMANDS).supplyMap(s4); + checkMcf(mcf, mcf.run(), + gr, l2, u, c, s4, false, 0, "#A14", LEQ); + } + + // B. Test NetworkSimplex with each pivot rule + { + NetworkSimplex mcf(gr); + mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2); + + checkMcf(mcf, mcf.run(NetworkSimplex::FIRST_ELIGIBLE), + gr, l2, u, c, s1, true, 5970, "#B1"); + checkMcf(mcf, mcf.run(NetworkSimplex::BEST_ELIGIBLE), + gr, l2, u, c, s1, true, 5970, "#B2"); + checkMcf(mcf, mcf.run(NetworkSimplex::BLOCK_SEARCH), + gr, l2, u, c, s1, true, 5970, "#B3"); + checkMcf(mcf, mcf.run(NetworkSimplex::CANDIDATE_LIST), + gr, l2, u, c, s1, true, 5970, "#B4"); + checkMcf(mcf, mcf.run(NetworkSimplex::ALTERING_LIST), + gr, l2, u, c, s1, true, 5970, "#B5"); + } + + return 0; +} diff --git a/tools/dimacs-solver.cc b/tools/dimacs-solver.cc --- a/tools/dimacs-solver.cc +++ b/tools/dimacs-solver.cc @@ -43,6 +43,7 @@ #include #include #include +#include using namespace lemon; typedef SmartDigraph Digraph; @@ -90,6 +91,28 @@ if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; } +template +void solve_min(ArgParser &ap, std::istream &is, std::ostream &, + DimacsDescriptor &desc) +{ + bool report = !ap.given("q"); + Digraph g; + Digraph::ArcMap lower(g), cap(g), cost(g); + Digraph::NodeMap sup(g); + Timer ti; + ti.restart(); + readDimacsMin(is, g, lower, cap, cost, sup, 0, desc); + if (report) std::cerr << "Read the file: " << ti << '\n'; + ti.restart(); + 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(); + if (report) std::cerr << "Run NetworkSimplex: " << ti << '\n'; + if (report) std::cerr << "\nMin flow cost: " << ns.totalCost() << '\n'; +} + void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, DimacsDescriptor &desc) { @@ -128,8 +151,7 @@ switch(desc.type) { case DimacsDescriptor::MIN: - std::cerr << - "\n\n Sorry, the min. cost flow solver is not yet available.\n"; + solve_min(ap,is,os,desc); break; case DimacsDescriptor::MAX: solve_max(ap,is,os,infty,desc);