COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changes in / [645:cb8270a98660:646:e01957e96c67] in lemon-main


Ignore:
Files:
15 edited

Legend:

Unmodified
Added
Removed

  • CMakeLists.txt

    r627 r631  
    1818FIND_PACKAGE(COIN)
    1919
    20 ADD_DEFINITIONS(-DHAVE_CONFIG_H)
    21 
    2220IF(MSVC)
    2321  SET(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} /wd4250 /wd4355 /wd4800 /wd4996")
    … …  
    2826# C4996: 'function': was declared deprecated
    2927ENDIF(MSVC)
    30 
    31 ADD_DEFINITIONS(-DHAVE_CONFIG_H)
    3228
    3329INCLUDE(CheckTypeSize)

  • Makefile.am

    r567 r629  
    1212        m4/lx_check_glpk.m4 \
    1313        m4/lx_check_soplex.m4 \
    14         m4/lx_check_clp.m4 \
    15         m4/lx_check_cbc.m4 \
     14        m4/lx_check_coin.m4 \
    1615        CMakeLists.txt \
    1716        cmake/FindGhostscript.cmake \
     17        cmake/FindCPLEX.cmake \
    1818        cmake/FindGLPK.cmake \
     19        cmake/FindCOIN.cmake \
    1920        cmake/version.cmake.in \
    2021        cmake/version.cmake \

  • cmake/FindCOIN.cmake

    r627 r634  
    22
    33FIND_PATH(COIN_INCLUDE_DIR coin/CoinUtilsConfig.h
    4   PATHS ${COIN_ROOT_DIR}/include)
    5 
    6 FIND_LIBRARY(COIN_CBC_LIBRARY libCbc
    7   PATHS ${COIN_ROOT_DIR}/lib)
    8 FIND_LIBRARY(COIN_CBC_SOLVER_LIBRARY libCbcSolver
    9   PATHS ${COIN_ROOT_DIR}/lib)
    10 FIND_LIBRARY(COIN_CGL_LIBRARY libCgl
    11   PATHS ${COIN_ROOT_DIR}/lib)
    12 FIND_LIBRARY(COIN_CLP_LIBRARY libClp
    13   PATHS ${COIN_ROOT_DIR}/lib)
    14 FIND_LIBRARY(COIN_COIN_UTILS_LIBRARY libCoinUtils
    15   PATHS ${COIN_ROOT_DIR}/lib)
    16 FIND_LIBRARY(COIN_OSI_LIBRARY libOsi
    17   PATHS ${COIN_ROOT_DIR}/lib)
    18 FIND_LIBRARY(COIN_OSI_CBC_LIBRARY libOsiCbc
    19   PATHS ${COIN_ROOT_DIR}/lib)
    20 FIND_LIBRARY(COIN_OSI_CLP_LIBRARY libOsiClp
    21   PATHS ${COIN_ROOT_DIR}/lib)
    22 FIND_LIBRARY(COIN_OSI_VOL_LIBRARY libOsiVol
    23   PATHS ${COIN_ROOT_DIR}/lib)
    24 FIND_LIBRARY(COIN_VOL_LIBRARY libVol
    25   PATHS ${COIN_ROOT_DIR}/lib)
     4  HINTS ${COIN_ROOT_DIR}/include
     5)
     6FIND_LIBRARY(COIN_CBC_LIBRARY
     7  NAMES Cbc libCbc
     8  HINTS ${COIN_ROOT_DIR}/lib
     9)
     10FIND_LIBRARY(COIN_CBC_SOLVER_LIBRARY
     11  NAMES CbcSolver libCbcSolver
     12  HINTS ${COIN_ROOT_DIR}/lib
     13)
     14FIND_LIBRARY(COIN_CGL_LIBRARY
     15  NAMES Cgl libCgl
     16  HINTS ${COIN_ROOT_DIR}/lib
     17)
     18FIND_LIBRARY(COIN_CLP_LIBRARY
     19  NAMES Clp libClp
     20  HINTS ${COIN_ROOT_DIR}/lib
     21)
     22FIND_LIBRARY(COIN_COIN_UTILS_LIBRARY
     23  NAMES CoinUtils libCoinUtils
     24  HINTS ${COIN_ROOT_DIR}/lib
     25)
     26FIND_LIBRARY(COIN_OSI_LIBRARY
     27  NAMES Osi libOsi
     28  HINTS ${COIN_ROOT_DIR}/lib
     29)
     30FIND_LIBRARY(COIN_OSI_CBC_LIBRARY
     31  NAMES OsiCbc libOsiCbc
     32  HINTS ${COIN_ROOT_DIR}/lib
     33)
     34FIND_LIBRARY(COIN_OSI_CLP_LIBRARY
     35  NAMES OsiClp libOsiClp
     36  HINTS ${COIN_ROOT_DIR}/lib
     37)
     38FIND_LIBRARY(COIN_OSI_VOL_LIBRARY
     39  NAMES OsiVol libOsiVol
     40  HINTS ${COIN_ROOT_DIR}/lib
     41)
     42FIND_LIBRARY(COIN_VOL_LIBRARY
     43  NAMES Vol libVol
     44  HINTS ${COIN_ROOT_DIR}/lib
     45)
    2646
    2747INCLUDE(FindPackageHandleStandardArgs)

  • cmake/FindCPLEX.cmake

    r627 r636  
     1SET(CPLEX_ROOT_DIR "" CACHE PATH "CPLEX root directory")
     2
    13FIND_PATH(CPLEX_INCLUDE_DIR
    24  ilcplex/cplex.h
    3   PATHS "C:/ILOG/CPLEX91/include")
    4 
     5  PATHS "C:/ILOG/CPLEX91/include"
     6  PATHS "/opt/ilog/cplex91/include"
     7  HINTS ${CPLEX_ROOT_DIR}/include
     8)
    59FIND_LIBRARY(CPLEX_LIBRARY
    6   NAMES cplex91
    7   PATHS "C:/ILOG/CPLEX91/lib/msvc7/stat_mda")
     10  cplex91
     11  PATHS "C:/ILOG/CPLEX91/lib/msvc7/stat_mda"
     12  PATHS "/opt/ilog/cplex91/bin"
     13  HINTS ${CPLEX_ROOT_DIR}/bin
     14)
    815
    916INCLUDE(FindPackageHandleStandardArgs)
    … …  
    1219FIND_PATH(CPLEX_BIN_DIR
    1320  cplex91.dll
    14   PATHS "C:/ILOG/CPLEX91/bin/x86_win32")
     21  PATHS "C:/ILOG/CPLEX91/bin/x86_win32"
     22)
    1523
    1624IF(CPLEX_FOUND)
    1725  SET(CPLEX_INCLUDE_DIRS ${CPLEX_INCLUDE_DIR})
    1826  SET(CPLEX_LIBRARIES ${CPLEX_LIBRARY})
     27  IF(CMAKE_SYSTEM_NAME STREQUAL "Linux")
     28    SET(CPLEX_LIBRARIES "${CPLEX_LIBRARIES};m;pthread")
     29  ENDIF(CMAKE_SYSTEM_NAME STREQUAL "Linux")
    1930ENDIF(CPLEX_FOUND)
    2031

  • cmake/FindGLPK.cmake

    r627 r638  
     1SET(GLPK_ROOT_DIR "" CACHE PATH "GLPK root directory")
     2
    13SET(GLPK_REGKEY "[HKEY_LOCAL_MACHINE\\SOFTWARE\\GnuWin32\\Glpk;InstallPath]")
    24GET_FILENAME_COMPONENT(GLPK_ROOT_PATH ${GLPK_REGKEY} ABSOLUTE)
    … …  
    46FIND_PATH(GLPK_INCLUDE_DIR
    57  glpk.h
    6   PATHS ${GLPK_REGKEY}/include)
     8  PATHS ${GLPK_REGKEY}/include
     9  HINTS ${GLPK_ROOT_DIR}/include
     10)
     11FIND_LIBRARY(GLPK_LIBRARY
     12  glpk
     13  PATHS ${GLPK_REGKEY}/lib
     14  HINTS ${GLPK_ROOT_DIR}/lib
     15)
    716
    8 FIND_LIBRARY(GLPK_LIBRARY
    9   NAMES glpk
    10   PATHS ${GLPK_REGKEY}/lib)
     17IF(GLPK_INCLUDE_DIR AND GLPK_LIBRARY)
     18  FILE(READ ${GLPK_INCLUDE_DIR}/glpk.h GLPK_GLPK_H)
     19
     20  STRING(REGEX MATCH "define[ ]+GLP_MAJOR_VERSION[ ]+[0-9]+" GLPK_MAJOR_VERSION_LINE "${GLPK_GLPK_H}")
     21  STRING(REGEX REPLACE "define[ ]+GLP_MAJOR_VERSION[ ]+([0-9]+)" "\\1" GLPK_VERSION_MAJOR "${GLPK_MAJOR_VERSION_LINE}")
     22
     23  STRING(REGEX MATCH "define[ ]+GLP_MINOR_VERSION[ ]+[0-9]+" GLPK_MINOR_VERSION_LINE "${GLPK_GLPK_H}")
     24  STRING(REGEX REPLACE "define[ ]+GLP_MINOR_VERSION[ ]+([0-9]+)" "\\1" GLPK_VERSION_MINOR "${GLPK_MINOR_VERSION_LINE}")
     25
     26  SET(GLPK_VERSION_STRING "${GLPK_VERSION_MAJOR}.${GLPK_VERSION_MINOR}")
     27
     28  IF(GLPK_FIND_VERSION)
     29    IF(GLPK_FIND_VERSION_COUNT GREATER 2)
     30      MESSAGE(SEND_ERROR "unexpected version string")
     31    ENDIF(GLPK_FIND_VERSION_COUNT GREATER 2)
     32
     33    MATH(EXPR GLPK_REQUESTED_VERSION "${GLPK_FIND_VERSION_MAJOR}*100 + ${GLPK_FIND_VERSION_MINOR}")
     34    MATH(EXPR GLPK_FOUND_VERSION "${GLPK_VERSION_MAJOR}*100 + ${GLPK_VERSION_MINOR}")
     35
     36    IF(GLPK_FOUND_VERSION LESS GLPK_REQUESTED_VERSION)
     37      SET(GLPK_PROPER_VERSION_FOUND FALSE)
     38    ELSE(GLPK_FOUND_VERSION LESS GLPK_REQUESTED_VERSION)
     39      SET(GLPK_PROPER_VERSION_FOUND TRUE)
     40    ENDIF(GLPK_FOUND_VERSION LESS GLPK_REQUESTED_VERSION)
     41  ELSE(GLPK_FIND_VERSION)
     42    SET(GLPK_PROPER_VERSION_FOUND TRUE)
     43  ENDIF(GLPK_FIND_VERSION)
     44ENDIF(GLPK_INCLUDE_DIR AND GLPK_LIBRARY)
    1145
    1246INCLUDE(FindPackageHandleStandardArgs)
    13 FIND_PACKAGE_HANDLE_STANDARD_ARGS(GLPK DEFAULT_MSG GLPK_LIBRARY GLPK_INCLUDE_DIR)
     47FIND_PACKAGE_HANDLE_STANDARD_ARGS(GLPK DEFAULT_MSG GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_PROPER_VERSION_FOUND)
    1448
    1549IF(GLPK_FOUND)

  • doc/groups.dox

    r611 r640  
    353353in a network with capacity constraints (lower and upper bounds)
    354354and arc costs.
    355 Formally, let \f$G=(V,A)\f$ be a digraph,
    356 \f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
     355Formally, let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{Z}\f$,
     356\f$upper: A\rightarrow\mathbf{Z}\cup\{+\infty\}\f$ denote the lower and
    357357upper bounds for the flow values on the arcs, for which
    358 \f$0 \leq lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$.
    359 \f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
    360 on the arcs, and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
     358\f$lower(uv) \leq upper(uv)\f$ must hold for all \f$uv\in A\f$,
     359\f$cost: A\rightarrow\mathbf{Z}\f$ denotes the cost per unit flow
     360on the arcs and \f$sup: V\rightarrow\mathbf{Z}\f$ denotes the
    361361signed supply values of the nodes.
    362362If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
    363363supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
    364364\f$-sup(u)\f$ demand.
    365 A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}^+_0\f$ solution
     365A minimum cost flow is an \f$f: A\rightarrow\mathbf{Z}\f$ solution
    366366of the following optimization problem.
    367367
    … …  
    405405The dual solution of the minimum cost flow problem is represented by node
    406406potentials \f$\pi: V\rightarrow\mathbf{Z}\f$.
    407 An \f$f: A\rightarrow\mathbf{Z}^+_0\f$ feasible solution of the problem
     407An \f$f: A\rightarrow\mathbf{Z}\f$ feasible solution of the problem
    408408is optimal if and only if for some \f$\pi: V\rightarrow\mathbf{Z}\f$
    409409node potentials the following \e complementary \e slackness optimality
    … …  
    414414   - if \f$lower(uv)<f(uv)<upper(uv)\f$, then \f$cost^\pi(uv)=0\f$;
    415415   - if \f$cost^\pi(uv)<0\f$, then \f$f(uv)=upper(uv)\f$.
    416  - For all \f$u\in V\f$:
     416 - For all \f$u\in V\f$ nodes:
    417417   - if \f$\sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) \neq sup(u)\f$,
    418418     then \f$\pi(u)=0\f$.
    419419 
    420420Here \f$cost^\pi(uv)\f$ denotes the \e reduced \e cost of the arc
    421 \f$uv\in A\f$ with respect to the node potentials \f$\pi\f$, i.e.
     421\f$uv\in A\f$ with respect to the potential function \f$\pi\f$, i.e.
    422422\f[ cost^\pi(uv) = cost(uv) + \pi(u) - \pi(v).\f]
    423423
    424 All algorithms provide dual solution (node potentials) as well
     424All algorithms provide dual solution (node potentials) as well,
    425425if an optimal flow is found.
    426426

  • lemon/Makefile.am

    r627 r639  
    1616        lemon/bits/windows.cc
    1717
    18 
     18nodist_lemon_HEADERS = lemon/config.h   
     19       
    1920lemon_libemon_la_CXXFLAGS = \
    2021        $(AM_CXXFLAGS) \
    … …  
    5859        lemon/bfs.h \
    5960        lemon/bin_heap.h \
     61        lemon/cbc.h \
    6062        lemon/circulation.h \
    6163        lemon/clp.h \
    6264        lemon/color.h \
    6365        lemon/concept_check.h \
    64         lemon/config.h \
    6566        lemon/connectivity.h \
    6667        lemon/counter.h \

  • lemon/circulation.h

    r622 r641  
    6565    typedef SM SupplyMap;
    6666
    67     /// \brief The type of the flow values.
    68     typedef typename SupplyMap::Value Flow;
     67    /// \brief The type of the flow and supply values.
     68    typedef typename SupplyMap::Value Value;
    6969
    7070    /// \brief The type of the map that stores the flow values.
    … …  
    7373    /// It must conform to the \ref concepts::ReadWriteMap "ReadWriteMap"
    7474    /// concept.
    75     typedef typename Digraph::template ArcMap<Flow> FlowMap;
     75    typedef typename Digraph::template ArcMap<Value> FlowMap;
    7676
    7777    /// \brief Instantiates a FlowMap.
    … …  
    105105    ///
    106106    /// The tolerance used by the algorithm to handle inexact computation.
    107     typedef lemon::Tolerance<Flow> Tolerance;
     107    typedef lemon::Tolerance<Value> Tolerance;
    108108
    109109  };
    … …  
    188188    ///The type of the digraph the algorithm runs on.
    189189    typedef typename Traits::Digraph Digraph;
    190     ///The type of the flow values.
    191     typedef typename Traits::Flow Flow;
     190    ///The type of the flow and supply values.
     191    typedef typename Traits::Value Value;
    192192
    193193    ///The type of the lower bound map.
    … …  
    222222    bool _local_level;
    223223
    224     typedef typename Digraph::template NodeMap<Flow> ExcessMap;
     224    typedef typename Digraph::template NodeMap<Value> ExcessMap;
    225225    ExcessMap* _excess;
    226226
    … …  
    531531          (*_excess)[_g.source(e)] -= (*_lo)[e];
    532532        } else {
    533           Flow fc = -(*_excess)[_g.target(e)];
     533          Value fc = -(*_excess)[_g.target(e)];
    534534          _flow->set(e, fc);
    535535          (*_excess)[_g.target(e)] = 0;
    … …  
    564564        int actlevel=(*_level)[act];
    565565        int mlevel=_node_num;
    566         Flow exc=(*_excess)[act];
     566        Value exc=(*_excess)[act];
    567567
    568568        for(OutArcIt e(_g,act);e!=INVALID; ++e) {
    569569          Node v = _g.target(e);
    570           Flow fc=(*_up)[e]-(*_flow)[e];
     570          Value fc=(*_up)[e]-(*_flow)[e];
    571571          if(!_tol.positive(fc)) continue;
    572572          if((*_level)[v]<actlevel) {
    … …  
    592592        for(InArcIt e(_g,act);e!=INVALID; ++e) {
    593593          Node v = _g.source(e);
    594           Flow fc=(*_flow)[e]-(*_lo)[e];
     594          Value fc=(*_flow)[e]-(*_lo)[e];
    595595          if(!_tol.positive(fc)) continue;
    596596          if((*_level)[v]<actlevel) {
    … …  
    662662    ///@{
    663663
    664     /// \brief Returns the flow on the given arc.
    665     ///
    666     /// Returns the flow on the given arc.
     664    /// \brief Returns the flow value on the given arc.
     665    ///
     666    /// Returns the flow value on the given arc.
    667667    ///
    668668    /// \pre Either \ref run() or \ref init() must be called before
    669669    /// using this function.
    670     Flow flow(const Arc& arc) const {
     670    Value flow(const Arc& arc) const {
    671671      return (*_flow)[arc];
    672672    }
    … …  
    751751      for(NodeIt n(_g);n!=INVALID;++n)
    752752        {
    753           Flow dif=-(*_supply)[n];
     753          Value dif=-(*_supply)[n];
    754754          for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
    755755          for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
    … …  
    766766    bool checkBarrier() const
    767767    {
    768       Flow delta=0;
    769       Flow inf_cap = std::numeric_limits<Flow>::has_infinity ?
    770         std::numeric_limits<Flow>::infinity() :
    771         std::numeric_limits<Flow>::max();
     768      Value delta=0;
     769      Value inf_cap = std::numeric_limits<Value>::has_infinity ?
     770        std::numeric_limits<Value>::infinity() :
     771        std::numeric_limits<Value>::max();
    772772      for(NodeIt n(_g);n!=INVALID;++n)
    773773        if(barrier(n))

  • lemon/core.h

    r617 r639  
    2323#include <algorithm>
    2424
    25 #include <lemon/core.h>
     25#include <lemon/config.h>
    2626#include <lemon/bits/enable_if.h>
    2727#include <lemon/bits/traits.h>

  • lemon/network_simplex.h

    r618 r643  
    3131#include <lemon/core.h>
    3232#include <lemon/math.h>
    33 #include <lemon/maps.h>
    34 #include <lemon/circulation.h>
    35 #include <lemon/adaptors.h>
    3633
    3734namespace lemon {
    … …  
    5148  /// In general this class is the fastest implementation available
    5249  /// in LEMON for the minimum cost flow problem.
    53   /// Moreover it supports both direction of the supply/demand inequality
    54   /// constraints. For more information see \ref ProblemType.
     50  /// Moreover it supports both directions of the supply/demand inequality
     51  /// constraints. For more information see \ref SupplyType.
     52  ///
     53  /// Most of the parameters of the problem (except for the digraph)
     54  /// can be given using separate functions, and the algorithm can be
     55  /// executed using the \ref run() function. If some parameters are not
     56  /// specified, then default values will be used.
    5557  ///
    5658  /// \tparam GR The digraph type the algorithm runs on.
    57   /// \tparam F The value type used for flow amounts, capacity bounds
     59  /// \tparam V The value type used for flow amounts, capacity bounds
    5860  /// and supply values in the algorithm. By default it is \c int.
    5961  /// \tparam C The value type used for costs and potentials in the
    60   /// algorithm. By default it is the same as \c F.
     62  /// algorithm. By default it is the same as \c V.
    6163  ///
    6264  /// \warning Both value types must be signed and all input data must
    … …  
    6668  /// implementations, from which the most efficient one is used
    6769  /// by default. For more information see \ref PivotRule.
    68   template <typename GR, typename F = int, typename C = F>
     70  template <typename GR, typename V = int, typename C = V>
    6971  class NetworkSimplex
    7072  {
    7173  public:
    7274
    73     /// The flow type of the algorithm
    74     typedef F Flow;
    75     /// The cost type of the algorithm
     75    /// The type of the flow amounts, capacity bounds and supply values
     76    typedef V Value;
     77    /// The type of the arc costs
    7678    typedef C Cost;
    77 #ifdef DOXYGEN
    78     /// The type of the flow map
    79     typedef GR::ArcMap<Flow> FlowMap;
    80     /// The type of the potential map
    81     typedef GR::NodeMap<Cost> PotentialMap;
    82 #else
    83     /// The type of the flow map
    84     typedef typename GR::template ArcMap<Flow> FlowMap;
    85     /// The type of the potential map
    86     typedef typename GR::template NodeMap<Cost> PotentialMap;
    87 #endif
    8879
    8980  public:
    9081
    91     /// \brief Enum type for selecting the pivot rule.
    92     ///
    93     /// Enum type for selecting the pivot rule for the \ref run()
    94     /// function.
    95     ///
    96     /// \ref NetworkSimplex provides five different pivot rule
    97     /// implementations that significantly affect the running time
    98     /// of the algorithm.
    99     /// By default \ref BLOCK_SEARCH "Block Search" is used, which
    100     /// proved to be the most efficient and the most robust on various
    101     /// test inputs according to our benchmark tests.
    102     /// However another pivot rule can be selected using the \ref run()
    103     /// function with the proper parameter.
    104     enum PivotRule {
    105 
    106       /// The First Eligible pivot rule.
    107       /// The next eligible arc is selected in a wraparound fashion
    108       /// in every iteration.
    109       FIRST_ELIGIBLE,
    110 
    111       /// The Best Eligible pivot rule.
    112       /// The best eligible arc is selected in every iteration.
    113       BEST_ELIGIBLE,
    114 
    115       /// The Block Search pivot rule.
    116       /// A specified number of arcs are examined in every iteration
    117       /// in a wraparound fashion and the best eligible arc is selected
    118       /// from this block.
    119       BLOCK_SEARCH,
    120 
    121       /// The Candidate List pivot rule.
    122       /// In a major iteration a candidate list is built from eligible arcs
    123       /// in a wraparound fashion and in the following minor iterations
    124       /// the best eligible arc is selected from this list.
    125       CANDIDATE_LIST,
    126 
    127       /// The Altering Candidate List pivot rule.
    128       /// It is a modified version of the Candidate List method.
    129       /// It keeps only the several best eligible arcs from the former
    130       /// candidate list and extends this list in every iteration.
    131       ALTERING_LIST
     82    /// \brief Problem type constants for the \c run() function.
     83    ///
     84    /// Enum type containing the problem type constants that can be
     85    /// returned by the \ref run() function of the algorithm.
     86    enum ProblemType {
     87      /// The problem has no feasible solution (flow).
     88      INFEASIBLE,
     89      /// The problem has optimal solution (i.e. it is feasible and
     90      /// bounded), and the algorithm has found optimal flow and node
     91      /// potentials (primal and dual solutions).
     92      OPTIMAL,
     93      /// The objective function of the problem is unbounded, i.e.
     94      /// there is a directed cycle having negative total cost and
     95      /// infinite upper bound.
     96      UNBOUNDED
    13297    };
    13398   
    134     /// \brief Enum type for selecting the problem type.
    135     ///
    136     /// Enum type for selecting the problem type, i.e. the direction of
    137     /// the inequalities in the supply/demand constraints of the
    138     /// \ref min_cost_flow "minimum cost flow problem".
    139     ///
    140     /// The default problem type is \c GEQ, since this form is supported
     99    /// \brief Constants for selecting the type of the supply constraints.
     100    ///
     101    /// Enum type containing constants for selecting the supply type,
     102    /// i.e. the direction of the inequalities in the supply/demand
     103    /// constraints of the \ref min_cost_flow "minimum cost flow problem".
     104    ///
     105    /// The default supply type is \c GEQ, since this form is supported
    141106    /// by other minimum cost flow algorithms and the \ref Circulation
    142     /// algorithm as well.
    143     /// The \c LEQ problem type can be selected using the \ref problemType()
     107    /// algorithm, as well.
     108    /// The \c LEQ problem type can be selected using the \ref supplyType()
    144109    /// function.
    145110    ///
    146     /// Note that the equality form is a special case of both problem type.
    147     enum ProblemType {
    148 
    149       /// This option means that there are "<em>greater or equal</em>"
    150       /// constraints in the defintion, i.e. the exact formulation of the
    151       /// problem is the following.
     111    /// Note that the equality form is a special case of both supply types.
     112    enum SupplyType {
     113
     114      /// This option means that there are <em>"greater or equal"</em>
     115      /// supply/demand constraints in the definition, i.e. the exact
     116      /// formulation of the problem is the following.
    152117      /**
    153118          \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
    … …  
    165130      CARRY_SUPPLIES = GEQ,
    166131
    167       /// This option means that there are "<em>less or equal</em>"
    168       /// constraints in the defintion, i.e. the exact formulation of the
    169       /// problem is the following.
     132      /// This option means that there are <em>"less or equal"</em>
     133      /// supply/demand constraints in the definition, i.e. the exact
     134      /// formulation of the problem is the following.
    170135      /**
    171136          \f[ \min\sum_{uv\in A} f(uv) \cdot cost(uv) \f]
    … …  
    183148      SATISFY_DEMANDS = LEQ
    184149    };
    185 
     150   
     151    /// \brief Constants for selecting the pivot rule.
     152    ///
     153    /// Enum type containing constants for selecting the pivot rule for
     154    /// the \ref run() function.
     155    ///
     156    /// \ref NetworkSimplex provides five different pivot rule
     157    /// implementations that significantly affect the running time
     158    /// of the algorithm.
     159    /// By default \ref BLOCK_SEARCH "Block Search" is used, which
     160    /// proved to be the most efficient and the most robust on various
     161    /// test inputs according to our benchmark tests.
     162    /// However another pivot rule can be selected using the \ref run()
     163    /// function with the proper parameter.
     164    enum PivotRule {
     165
     166      /// The First Eligible pivot rule.
     167      /// The next eligible arc is selected in a wraparound fashion
     168      /// in every iteration.
     169      FIRST_ELIGIBLE,
     170
     171      /// The Best Eligible pivot rule.
     172      /// The best eligible arc is selected in every iteration.
     173      BEST_ELIGIBLE,
     174
     175      /// The Block Search pivot rule.
     176      /// A specified number of arcs are examined in every iteration
     177      /// in a wraparound fashion and the best eligible arc is selected
     178      /// from this block.
     179      BLOCK_SEARCH,
     180
     181      /// The Candidate List pivot rule.
     182      /// In a major iteration a candidate list is built from eligible arcs
     183      /// in a wraparound fashion and in the following minor iterations
     184      /// the best eligible arc is selected from this list.
     185      CANDIDATE_LIST,
     186
     187      /// The Altering Candidate List pivot rule.
     188      /// It is a modified version of the Candidate List method.
     189      /// It keeps only the several best eligible arcs from the former
     190      /// candidate list and extends this list in every iteration.
     191      ALTERING_LIST
     192    };
     193   
    186194  private:
    187195
    188196    TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    189 
    190     typedef typename GR::template ArcMap<Flow> FlowArcMap;
    191     typedef typename GR::template ArcMap<Cost> CostArcMap;
    192     typedef typename GR::template NodeMap<Flow> FlowNodeMap;
    193197
    194198    typedef std::vector<Arc> ArcVector;
    … …  
    196200    typedef std::vector<int> IntVector;
    197201    typedef std::vector<bool> BoolVector;
    198     typedef std::vector<Flow> FlowVector;
     202    typedef std::vector<Value> ValueVector;
    199203    typedef std::vector<Cost> CostVector;
    200204
    … …  
    214218
    215219    // Parameters of the problem
    216     FlowArcMap *_plower;
    217     FlowArcMap *_pupper;
    218     CostArcMap *_pcost;
    219     FlowNodeMap *_psupply;
    220     bool _pstsup;
    221     Node _psource, _ptarget;
    222     Flow _pstflow;
    223     ProblemType _ptype;
    224 
    225     // Result maps
    226     FlowMap *_flow_map;
    227     PotentialMap *_potential_map;
    228     bool _local_flow;
    229     bool _local_potential;
     220    bool _have_lower;
     221    SupplyType _stype;
     222    Value _sum_supply;
    230223
    231224    // Data structures for storing the digraph
    232225    IntNodeMap _node_id;
    233     ArcVector _arc_ref;
     226    IntArcMap _arc_id;
    234227    IntVector _source;
    235228    IntVector _target;
    236229
    237230    // Node and arc data
    238     FlowVector _cap;
     231    ValueVector _lower;
     232    ValueVector _upper;
     233    ValueVector _cap;
    239234    CostVector _cost;
    240     FlowVector _supply;
    241     FlowVector _flow;
     235    ValueVector _supply;
     236    ValueVector _flow;
    242237    CostVector _pi;
    243238
    … …  
    258253    int first, second, right, last;
    259254    int stem, par_stem, new_stem;
    260     Flow delta;
     255    Value delta;
     256
     257  public:
     258 
     259    /// \brief Constant for infinite upper bounds (capacities).
     260    ///
     261    /// Constant for infinite upper bounds (capacities).
     262    /// It is \c std::numeric_limits<Value>::infinity() if available,
     263    /// \c std::numeric_limits<Value>::max() otherwise.
     264    const Value INF;
    261265
    262266  private:
    … …  
    660664    /// \param graph The digraph the algorithm runs on.
    661665    NetworkSimplex(const GR& graph) :
    662       _graph(graph),
    663       _plower(NULL), _pupper(NULL), _pcost(NULL),
    664       _psupply(NULL), _pstsup(false), _ptype(GEQ),
    665       _flow_map(NULL), _potential_map(NULL),
    666       _local_flow(false), _local_potential(false),
    667       _node_id(graph)
     666      _graph(graph), _node_id(graph), _arc_id(graph),
     667      INF(std::numeric_limits<Value>::has_infinity ?
     668          std::numeric_limits<Value>::infinity() :
     669          std::numeric_limits<Value>::max())
    668670    {
    669       LEMON_ASSERT(std::numeric_limits<Flow>::is_integer &&
    670                    std::numeric_limits<Flow>::is_signed,
    671         "The flow type of NetworkSimplex must be signed integer");
    672       LEMON_ASSERT(std::numeric_limits<Cost>::is_integer &&
    673                    std::numeric_limits<Cost>::is_signed,
    674         "The cost type of NetworkSimplex must be signed integer");
    675     }
    676 
    677     /// Destructor.
    678     ~NetworkSimplex() {
    679       if (_local_flow) delete _flow_map;
    680       if (_local_potential) delete _potential_map;
     671      // Check the value types
     672      LEMON_ASSERT(std::numeric_limits<Value>::is_signed,
     673        "The flow type of NetworkSimplex must be signed");
     674      LEMON_ASSERT(std::numeric_limits<Cost>::is_signed,
     675        "The cost type of NetworkSimplex must be signed");
     676       
     677      // Resize vectors
     678      _node_num = countNodes(_graph);
     679      _arc_num = countArcs(_graph);
     680      int all_node_num = _node_num + 1;
     681      int all_arc_num = _arc_num + _node_num;
     682
     683      _source.resize(all_arc_num);
     684      _target.resize(all_arc_num);
     685
     686      _lower.resize(all_arc_num);
     687      _upper.resize(all_arc_num);
     688      _cap.resize(all_arc_num);
     689      _cost.resize(all_arc_num);
     690      _supply.resize(all_node_num);
     691      _flow.resize(all_arc_num);
     692      _pi.resize(all_node_num);
     693
     694      _parent.resize(all_node_num);
     695      _pred.resize(all_node_num);
     696      _forward.resize(all_node_num);
     697      _thread.resize(all_node_num);
     698      _rev_thread.resize(all_node_num);
     699      _succ_num.resize(all_node_num);
     700      _last_succ.resize(all_node_num);
     701      _state.resize(all_arc_num);
     702
     703      // Copy the graph (store the arcs in a mixed order)
     704      int i = 0;
     705      for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
     706        _node_id[n] = i;
     707      }
     708      int k = std::max(int(std::sqrt(double(_arc_num))), 10);
     709      i = 0;
     710      for (ArcIt a(_graph); a != INVALID; ++a) {
     711        _arc_id[a] = i;
     712        _source[i] = _node_id[_graph.source(a)];
     713        _target[i] = _node_id[_graph.target(a)];
     714        if ((i += k) >= _arc_num) i = (i % k) + 1;
     715      }
     716     
     717      // Initialize maps
     718      for (int i = 0; i != _node_num; ++i) {
     719        _supply[i] = 0;
     720      }
     721      for (int i = 0; i != _arc_num; ++i) {
     722        _lower[i] = 0;
     723        _upper[i] = INF;
     724        _cost[i] = 1;
     725      }
     726      _have_lower = false;
     727      _stype = GEQ;
    681728    }
    682729
    … …  
    690737    ///
    691738    /// This function sets the lower bounds on the arcs.
    692     /// If neither this function nor \ref boundMaps() is used before
    693     /// calling \ref run(), the lower bounds will be set to zero
    694     /// on all arcs.
     739    /// If it is not used before calling \ref run(), the lower bounds
     740    /// will be set to zero on all arcs.
    695741    ///
    696742    /// \param map An arc map storing the lower bounds.
    697     /// Its \c Value type must be convertible to the \c Flow type
     743    /// Its \c Value type must be convertible to the \c Value type
    698744    /// of the algorithm.
    699745    ///
    700746    /// \return <tt>(*this)</tt>
    701     template <typename LOWER>
    702     NetworkSimplex& lowerMap(const LOWER& map) {
    703       delete _plower;
    704       _plower = new FlowArcMap(_graph);
     747    template <typename LowerMap>
     748    NetworkSimplex& lowerMap(const LowerMap& map) {
     749      _have_lower = true;
    705750      for (ArcIt a(_graph); a != INVALID; ++a) {
    706         (*_plower)[a] = map[a];
     751        _lower[_arc_id[a]] = map[a];
    707752      }
    708753      return *this;
    … …  
    712757    ///
    713758    /// This function sets the upper bounds (capacities) on the arcs.
    714     /// If none of the functions \ref upperMap(), \ref capacityMap()
    715     /// and \ref boundMaps() is used before calling \ref run(),
    716     /// the upper bounds (capacities) will be set to
    717     /// \c std::numeric_limits<Flow>::max() on all arcs.
     759    /// If it is not used before calling \ref run(), the upper bounds
     760    /// will be set to \ref INF on all arcs (i.e. the flow value will be
     761    /// unbounded from above on each arc).
    718762    ///
    719763    /// \param map An arc map storing the upper bounds.
    720     /// Its \c Value type must be convertible to the \c Flow type
     764    /// Its \c Value type must be convertible to the \c Value type
    721765    /// of the algorithm.
    722766    ///
    723767    /// \return <tt>(*this)</tt>
    724     template<typename UPPER>
    725     NetworkSimplex& upperMap(const UPPER& map) {
    726       delete _pupper;
    727       _pupper = new FlowArcMap(_graph);
     768    template<typename UpperMap>
     769    NetworkSimplex& upperMap(const UpperMap& map) {
    728770      for (ArcIt a(_graph); a != INVALID; ++a) {
    729         (*_pupper)[a] = map[a];
     771        _upper[_arc_id[a]] = map[a];
    730772      }
    731773      return *this;
    732     }
    733 
    734     /// \brief Set the upper bounds (capacities) on the arcs.
    735     ///
    736     /// This function sets the upper bounds (capacities) on the arcs.
    737     /// It is just an alias for \ref upperMap().
    738     ///
    739     /// \return <tt>(*this)</tt>
    740     template<typename CAP>
    741     NetworkSimplex& capacityMap(const CAP& map) {
    742       return upperMap(map);
    743     }
    744 
    745     /// \brief Set the lower and upper bounds on the arcs.
    746     ///
    747     /// This function sets the lower and upper bounds on the arcs.
    748     /// If neither this function nor \ref lowerMap() is used before
    749     /// calling \ref run(), the lower bounds will be set to zero
    750     /// on all arcs.
    751     /// If none of the functions \ref upperMap(), \ref capacityMap()
    752     /// and \ref boundMaps() is used before calling \ref run(),
    753     /// the upper bounds (capacities) will be set to
    754     /// \c std::numeric_limits<Flow>::max() on all arcs.
    755     ///
    756     /// \param lower An arc map storing the lower bounds.
    757     /// \param upper An arc map storing the upper bounds.
    758     ///
    759     /// The \c Value type of the maps must be convertible to the
    760     /// \c Flow type of the algorithm.
    761     ///
    762     /// \note This function is just a shortcut of calling \ref lowerMap()
    763     /// and \ref upperMap() separately.
    764     ///
    765     /// \return <tt>(*this)</tt>
    766     template <typename LOWER, typename UPPER>
    767     NetworkSimplex& boundMaps(const LOWER& lower, const UPPER& upper) {
    768       return lowerMap(lower).upperMap(upper);
    769774    }
    770775
    … …  
    780785    ///
    781786    /// \return <tt>(*this)</tt>
    782     template<typename COST>
    783     NetworkSimplex& costMap(const COST& map) {
    784       delete _pcost;
    785       _pcost = new CostArcMap(_graph);
     787    template<typename CostMap>
     788    NetworkSimplex& costMap(const CostMap& map) {
    786789      for (ArcIt a(_graph); a != INVALID; ++a) {
    787         (*_pcost)[a] = map[a];
     790        _cost[_arc_id[a]] = map[a];
    788791      }
    789792      return *this;
    … …  
    798801    ///
    799802    /// \param map A node map storing the supply values.
    800     /// Its \c Value type must be convertible to the \c Flow type
     803    /// Its \c Value type must be convertible to the \c Value type
    801804    /// of the algorithm.
    802805    ///
    803806    /// \return <tt>(*this)</tt>
    804     template<typename SUP>
    805     NetworkSimplex& supplyMap(const SUP& map) {
    806       delete _psupply;
    807       _pstsup = false;
    808       _psupply = new FlowNodeMap(_graph);
     807    template<typename SupplyMap>
     808    NetworkSimplex& supplyMap(const SupplyMap& map) {
    809809      for (NodeIt n(_graph); n != INVALID; ++n) {
    810         (*_psupply)[n] = map[n];
     810        _supply[_node_id[n]] = map[n];
    811811      }
    812812      return *this;
    … …  
    821821    /// (It makes sense only if non-zero lower bounds are given.)
    822822    ///
     823    /// Using this function has the same effect as using \ref supplyMap()
     824    /// with such a map in which \c k is assigned to \c s, \c -k is
     825    /// assigned to \c t and all other nodes have zero supply value.
     826    ///
    823827    /// \param s The source node.
    824828    /// \param t The target node.
    … …  
    827831    ///
    828832    /// \return <tt>(*this)</tt>
    829     NetworkSimplex& stSupply(const Node& s, const Node& t, Flow k) {
    830       delete _psupply;
    831       _psupply = NULL;
    832       _pstsup = true;
    833       _psource = s;
    834       _ptarget = t;
    835       _pstflow = k;
     833    NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) {
     834      for (int i = 0; i != _node_num; ++i) {
     835        _supply[i] = 0;
     836      }
     837      _supply[_node_id[s]] =  k;
     838      _supply[_node_id[t]] = -k;
    836839      return *this;
    837840    }
    838841   
    839     /// \brief Set the problem type.
    840     ///
    841     /// This function sets the problem type for the algorithm.
    842     /// If it is not used before calling \ref run(), the \ref GEQ problem
     842    /// \brief Set the type of the supply constraints.
     843    ///
     844    /// This function sets the type of the supply/demand constraints.
     845    /// If it is not used before calling \ref run(), the \ref GEQ supply
    843846    /// type will be used.
    844847    ///
    845     /// For more information see \ref ProblemType.
     848    /// For more information see \ref SupplyType.
    846849    ///
    847850    /// \return <tt>(*this)</tt>
    848     NetworkSimplex& problemType(ProblemType problem_type) {
    849       _ptype = problem_type;
     851    NetworkSimplex& supplyType(SupplyType supply_type) {
     852      _stype = supply_type;
    850853      return *this;
    851854    }
    852855
    853     /// \brief Set the flow map.
    854     ///
    855     /// This function sets the flow map.
    856     /// If it is not used before calling \ref run(), an instance will
    857     /// be allocated automatically. The destructor deallocates this
    858     /// automatically allocated map, of course.
    859     ///
    860     /// \return <tt>(*this)</tt>
    861     NetworkSimplex& flowMap(FlowMap& map) {
    862       if (_local_flow) {
    863         delete _flow_map;
    864         _local_flow = false;
    865       }
    866       _flow_map = &map;
    867       return *this;
    868     }
    869 
    870     /// \brief Set the potential map.
    871     ///
    872     /// This function sets the potential map, which is used for storing
    873     /// the dual solution.
    874     /// If it is not used before calling \ref run(), an instance will
    875     /// be allocated automatically. The destructor deallocates this
    876     /// automatically allocated map, of course.
    877     ///
    878     /// \return <tt>(*this)</tt>
    879     NetworkSimplex& potentialMap(PotentialMap& map) {
    880       if (_local_potential) {
    881         delete _potential_map;
    882         _local_potential = false;
    883       }
    884       _potential_map = &map;
    885       return *this;
    886     }
    887    
    888856    /// @}
    889857
    … …  
    897865    /// This function runs the algorithm.
    898866    /// The paramters can be specified using functions \ref lowerMap(),
    899     /// \ref upperMap(), \ref capacityMap(), \ref boundMaps(),
    900     /// \ref costMap(), \ref supplyMap(), \ref stSupply(),
    901     /// \ref problemType(), \ref flowMap() and \ref potentialMap().
     867    /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),
     868    /// \ref supplyType().
    902869    /// For example,
    903870    /// \code
    904871    ///   NetworkSimplex<ListDigraph> ns(graph);
    905     ///   ns.boundMaps(lower, upper).costMap(cost)
     872    ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
    906873    ///     .supplyMap(sup).run();
    907874    /// \endcode
    … …  
    911878    /// \ref reset() is called, thus only the modified parameters
    912879    /// have to be set again. See \ref reset() for examples.
     880    /// However the underlying digraph must not be modified after this
     881    /// class have been constructed, since it copies and extends the graph.
    913882    ///
    914883    /// \param pivot_rule The pivot rule that will be used during the
    915884    /// algorithm. For more information see \ref PivotRule.
    916885    ///
    917     /// \return \c true if a feasible flow can be found.
    918     bool run(PivotRule pivot_rule = BLOCK_SEARCH) {
    919       return init() && start(pivot_rule);
     886    /// \return \c INFEASIBLE if no feasible flow exists,
     887    /// \n \c OPTIMAL if the problem has optimal solution
     888    /// (i.e. it is feasible and bounded), and the algorithm has found
     889    /// optimal flow and node potentials (primal and dual solutions),
     890    /// \n \c UNBOUNDED if the objective function of the problem is
     891    /// unbounded, i.e. there is a directed cycle having negative total
     892    /// cost and infinite upper bound.
     893    ///
     894    /// \see ProblemType, PivotRule
     895    ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) {
     896      if (!init()) return INFEASIBLE;
     897      return start(pivot_rule);
    920898    }
    921899
    … …  
    924902    /// This function resets all the paramaters that have been given
    925903    /// before using functions \ref lowerMap(), \ref upperMap(),
    926     /// \ref capacityMap(), \ref boundMaps(), \ref costMap(),
    927     /// \ref supplyMap(), \ref stSupply(), \ref problemType(),
    928     /// \ref flowMap() and \ref potentialMap().
     904    /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType().
    929905    ///
    930906    /// It is useful for multiple run() calls. If this function is not
    931907    /// used, all the parameters given before are kept for the next
    932908    /// \ref run() call.
     909    /// However the underlying digraph must not be modified after this
     910    /// class have been constructed, since it copies and extends the graph.
    933911    ///
    934912    /// For example,
    … …  
    937915    ///
    938916    ///   // First run
    939     ///   ns.lowerMap(lower).capacityMap(cap).costMap(cost)
     917    ///   ns.lowerMap(lower).upperMap(upper).costMap(cost)
    940918    ///     .supplyMap(sup).run();
    941919    ///
    … …  
    948926    ///   // (the lower bounds will be set to zero on all arcs)
    949927    ///   ns.reset();
    950     ///   ns.capacityMap(cap).costMap(cost)
     928    ///   ns.upperMap(capacity).costMap(cost)
    951929    ///     .supplyMap(sup).run();
    952930    /// \endcode
    … …  
    954932    /// \return <tt>(*this)</tt>
    955933    NetworkSimplex& reset() {
    956       delete _plower;
    957       delete _pupper;
    958       delete _pcost;
    959       delete _psupply;
    960       _plower = NULL;
    961       _pupper = NULL;
    962       _pcost = NULL;
    963       _psupply = NULL;
    964       _pstsup = false;
    965       _ptype = GEQ;
    966       if (_local_flow) delete _flow_map;
    967       if (_local_potential) delete _potential_map;
    968       _flow_map = NULL;
    969       _potential_map = NULL;
    970       _local_flow = false;
    971       _local_potential = false;
    972 
     934      for (int i = 0; i != _node_num; ++i) {
     935        _supply[i] = 0;
     936      }
     937      for (int i = 0; i != _arc_num; ++i) {
     938        _lower[i] = 0;
     939        _upper[i] = INF;
     940        _cost[i] = 1;
     941      }
     942      _have_lower = false;
     943      _stype = GEQ;
    973944      return *this;
    974945    }
    … …  
    986957    ///
    987958    /// This function returns the total cost of the found flow.
    988     /// The complexity of the function is O(e).
     959    /// Its complexity is O(e).
    989960    ///
    990961    /// \note The return type of the function can be specified as a
    … …  
    998969    ///
    999970    /// \pre \ref run() must be called before using this function.
    1000     template <typename Num>
    1001     Num totalCost() const {
    1002       Num c = 0;
    1003       if (_pcost) {
    1004         for (ArcIt e(_graph); e != INVALID; ++e)
    1005           c += (*_flow_map)[e] * (*_pcost)[e];
    1006       } else {
    1007         for (ArcIt e(_graph); e != INVALID; ++e)
    1008           c += (*_flow_map)[e];
     971    template <typename Number>
     972    Number totalCost() const {
     973      Number c = 0;
     974      for (ArcIt a(_graph); a != INVALID; ++a) {
     975        int i = _arc_id[a];
     976        c += Number(_flow[i]) * Number(_cost[i]);
    1009977      }
    1010978      return c;
    … …  
    1022990    ///
    1023991    /// \pre \ref run() must be called before using this function.
    1024     Flow flow(const Arc& a) const {
    1025       return (*_flow_map)[a];
    1026     }
    1027 
    1028     /// \brief Return a const reference to the flow map.
    1029     ///
    1030     /// This function returns a const reference to an arc map storing
    1031     /// the found flow.
     992    Value flow(const Arc& a) const {
     993      return _flow[_arc_id[a]];
     994    }
     995
     996    /// \brief Return the flow map (the primal solution).
     997    ///
     998    /// This function copies the flow value on each arc into the given
     999    /// map. The \c Value type of the algorithm must be convertible to
     1000    /// the \c Value type of the map.
    10321001    ///
    10331002    /// \pre \ref run() must be called before using this function.
    1034     const FlowMap& flowMap() const {
    1035       return *_flow_map;
     1003    template <typename FlowMap>
     1004    void flowMap(FlowMap &map) const {
     1005      for (ArcIt a(_graph); a != INVALID; ++a) {
     1006        map.set(a, _flow[_arc_id[a]]);
     1007      }
    10361008    }
    10371009
    … …  
    10431015    /// \pre \ref run() must be called before using this function.
    10441016    Cost potential(const Node& n) const {
    1045       return (*_potential_map)[n];
    1046     }
    1047 
    1048     /// \brief Return a const reference to the potential map
    1049     /// (the dual solution).
    1050     ///
    1051     /// This function returns a const reference to a node map storing
    1052     /// the found potentials, which form the dual solution of the
    1053     /// \ref min_cost_flow "minimum cost flow" problem.
     1017      return _pi[_node_id[n]];
     1018    }
     1019
     1020    /// \brief Return the potential map (the dual solution).
     1021    ///
     1022    /// This function copies the potential (dual value) of each node
     1023    /// into the given map.
     1024    /// The \c Cost type of the algorithm must be convertible to the
     1025    /// \c Value type of the map.
    10541026    ///
    10551027    /// \pre \ref run() must be called before using this function.
    1056     const PotentialMap& potentialMap() const {
    1057       return *_potential_map;
     1028    template <typename PotentialMap>
     1029    void potentialMap(PotentialMap &map) const {
     1030      for (NodeIt n(_graph); n != INVALID; ++n) {
     1031        map.set(n, _pi[_node_id[n]]);
     1032      }
    10581033    }
    10591034
    … …  
    10641039    // Initialize internal data structures
    10651040    bool init() {
    1066       // Initialize result maps
    1067       if (!_flow_map) {
    1068         _flow_map = new FlowMap(_graph);
    1069         _local_flow = true;
    1070       }
    1071       if (!_potential_map) {
    1072         _potential_map = new PotentialMap(_graph);
    1073         _local_potential = true;
    1074       }
    1075 
    1076       // Initialize vectors
    1077       _node_num = countNodes(_graph);
    1078       _arc_num = countArcs(_graph);
    1079       int all_node_num = _node_num + 1;
    1080       int all_arc_num = _arc_num + _node_num;
    10811041      if (_node_num == 0) return false;
    10821042
    1083       _arc_ref.resize(_arc_num);
    1084       _source.resize(all_arc_num);
    1085       _target.resize(all_arc_num);
    1086 
    1087       _cap.resize(all_arc_num);
    1088       _cost.resize(all_arc_num);
    1089       _supply.resize(all_node_num);
    1090       _flow.resize(all_arc_num);
    1091       _pi.resize(all_node_num);
    1092 
    1093       _parent.resize(all_node_num);
    1094       _pred.resize(all_node_num);
    1095       _forward.resize(all_node_num);
    1096       _thread.resize(all_node_num);
    1097       _rev_thread.resize(all_node_num);
    1098       _succ_num.resize(all_node_num);
    1099       _last_succ.resize(all_node_num);
    1100       _state.resize(all_arc_num);
    1101 
    1102       // Initialize node related data
    1103       bool valid_supply = true;
    1104       Flow sum_supply = 0;
    1105       if (!_pstsup && !_psupply) {
    1106         _pstsup = true;
    1107         _psource = _ptarget = NodeIt(_graph);
    1108         _pstflow = 0;
    1109       }
    1110       if (_psupply) {
    1111         int i = 0;
    1112         for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    1113           _node_id[n] = i;
    1114           _supply[i] = (*_psupply)[n];
    1115           sum_supply += _supply[i];
    1116         }
    1117         valid_supply = (_ptype == GEQ && sum_supply <= 0) ||
    1118                        (_ptype == LEQ && sum_supply >= 0);
     1043      // Check the sum of supply values
     1044      _sum_supply = 0;
     1045      for (int i = 0; i != _node_num; ++i) {
     1046        _sum_supply += _supply[i];
     1047      }
     1048      if ( !((_stype == GEQ && _sum_supply <= 0) ||
     1049             (_stype == LEQ && _sum_supply >= 0)) ) return false;
     1050
     1051      // Remove non-zero lower bounds
     1052      if (_have_lower) {
     1053        for (int i = 0; i != _arc_num; ++i) {
     1054          Value c = _lower[i];
     1055          if (c >= 0) {
     1056            _cap[i] = _upper[i] < INF ? _upper[i] - c : INF;
     1057          } else {
     1058            _cap[i] = _upper[i] < INF + c ? _upper[i] - c : INF;
     1059          }
     1060          _supply[_source[i]] -= c;
     1061          _supply[_target[i]] += c;
     1062        }
    11191063      } else {
    1120         int i = 0;
    1121         for (NodeIt n(_graph); n != INVALID; ++n, ++i) {
    1122           _node_id[n] = i;
    1123           _supply[i] = 0;
    1124         }
    1125         _supply[_node_id[_psource]] =  _pstflow;
    1126         _supply[_node_id[_ptarget]] = -_pstflow;
    1127       }
    1128       if (!valid_supply) return false;
    1129 
    1130       // Infinite capacity value
    1131       Flow inf_cap =
    1132         std::numeric_limits<Flow>::has_infinity ?
    1133         std::numeric_limits<Flow>::infinity() :
    1134         std::numeric_limits<Flow>::max();
     1064        for (int i = 0; i != _arc_num; ++i) {
     1065          _cap[i] = _upper[i];
     1066        }
     1067      }
    11351068
    11361069      // Initialize artifical cost
    1137       Cost art_cost;
     1070      Cost ART_COST;
    11381071      if (std::numeric_limits<Cost>::is_exact) {
    1139         art_cost = std::numeric_limits<Cost>::max() / 4 + 1;
     1072        ART_COST = std::numeric_limits<Cost>::max() / 4 + 1;
    11401073      } else {
    1141         art_cost = std::numeric_limits<Cost>::min();
     1074        ART_COST = std::numeric_limits<Cost>::min();
    11421075        for (int i = 0; i != _arc_num; ++i) {
    1143           if (_cost[i] > art_cost) art_cost = _cost[i];
    1144         }
    1145         art_cost = (art_cost + 1) * _node_num;
    1146       }
    1147 
    1148       // Run Circulation to check if a feasible solution exists
    1149       typedef ConstMap<Arc, Flow> ConstArcMap;
    1150       ConstArcMap zero_arc_map(0), inf_arc_map(inf_cap);
    1151       FlowNodeMap *csup = NULL;
    1152       bool local_csup = false;
    1153       if (_psupply) {
    1154         csup = _psupply;
    1155       } else {
    1156         csup = new FlowNodeMap(_graph, 0);
    1157         (*csup)[_psource] =  _pstflow;
    1158         (*csup)[_ptarget] = -_pstflow;
    1159         local_csup = true;
    1160       }
    1161       bool circ_result = false;
    1162       if (_ptype == GEQ || (_ptype == LEQ && sum_supply == 0)) {
    1163         // GEQ problem type
    1164         if (_plower) {
    1165           if (_pupper) {
    1166             Circulation<GR, FlowArcMap, FlowArcMap, FlowNodeMap>
    1167               circ(_graph, *_plower, *_pupper, *csup);
    1168             circ_result = circ.run();
    1169           } else {
    1170             Circulation<GR, FlowArcMap, ConstArcMap, FlowNodeMap>
    1171               circ(_graph, *_plower, inf_arc_map, *csup);
    1172             circ_result = circ.run();
    1173           }
    1174         } else {
    1175           if (_pupper) {
    1176             Circulation<GR, ConstArcMap, FlowArcMap, FlowNodeMap>
    1177               circ(_graph, zero_arc_map, *_pupper, *csup);
    1178             circ_result = circ.run();
    1179           } else {
    1180             Circulation<GR, ConstArcMap, ConstArcMap, FlowNodeMap>
    1181               circ(_graph, zero_arc_map, inf_arc_map, *csup);
    1182             circ_result = circ.run();
    1183           }
    1184         }
    1185       } else {
    1186         // LEQ problem type
    1187         typedef ReverseDigraph<const GR> RevGraph;
    1188         typedef NegMap<FlowNodeMap> NegNodeMap;
    1189         RevGraph rgraph(_graph);
    1190         NegNodeMap neg_csup(*csup);
    1191         if (_plower) {
    1192           if (_pupper) {
    1193             Circulation<RevGraph, FlowArcMap, FlowArcMap, NegNodeMap>
    1194               circ(rgraph, *_plower, *_pupper, neg_csup);
    1195             circ_result = circ.run();
    1196           } else {
    1197             Circulation<RevGraph, FlowArcMap, ConstArcMap, NegNodeMap>
    1198               circ(rgraph, *_plower, inf_arc_map, neg_csup);
    1199             circ_result = circ.run();
    1200           }
    1201         } else {
    1202           if (_pupper) {
    1203             Circulation<RevGraph, ConstArcMap, FlowArcMap, NegNodeMap>
    1204               circ(rgraph, zero_arc_map, *_pupper, neg_csup);
    1205             circ_result = circ.run();
    1206           } else {
    1207             Circulation<RevGraph, ConstArcMap, ConstArcMap, NegNodeMap>
    1208               circ(rgraph, zero_arc_map, inf_arc_map, neg_csup);
    1209             circ_result = circ.run();
    1210           }
    1211         }
    1212       }
    1213       if (local_csup) delete csup;
    1214       if (!circ_result) return false;
    1215 
     1076          if (_cost[i] > ART_COST) ART_COST = _cost[i];
     1077        }
     1078        ART_COST = (ART_COST + 1) * _node_num;
     1079      }
     1080
     1081      // Initialize arc maps
     1082      for (int i = 0; i != _arc_num; ++i) {
     1083        _flow[i] = 0;
     1084        _state[i] = STATE_LOWER;
     1085      }
     1086     
    12161087      // Set data for the artificial root node
    12171088      _root = _node_num;
    … …  
    12201091      _thread[_root] = 0;
    12211092      _rev_thread[0] = _root;
    1222       _succ_num[_root] = all_node_num;
     1093      _succ_num[_root] = _node_num + 1;
    12231094      _last_succ[_root] = _root - 1;
    1224       _supply[_root] = -sum_supply;
    1225       if (sum_supply < 0) {
    1226         _pi[_root] = -art_cost;
    1227       } else {
    1228         _pi[_root] = art_cost;
    1229       }
    1230 
    1231       // Store the arcs in a mixed order
    1232       int k = std::max(int(std::sqrt(double(_arc_num))), 10);
    1233       int i = 0;
    1234       for (ArcIt e(_graph); e != INVALID; ++e) {
    1235         _arc_ref[i] = e;
    1236         if ((i += k) >= _arc_num) i = (i % k) + 1;
    1237       }
    1238 
    1239       // Initialize arc maps
    1240       if (_pupper && _pcost) {
    1241         for (int i = 0; i != _arc_num; ++i) {
    1242           Arc e = _arc_ref[i];
    1243           _source[i] = _node_id[_graph.source(e)];
    1244           _target[i] = _node_id[_graph.target(e)];
    1245           _cap[i] = (*_pupper)[e];
    1246           _cost[i] = (*_pcost)[e];
    1247           _flow[i] = 0;
    1248           _state[i] = STATE_LOWER;
    1249         }
    1250       } else {
    1251         for (int i = 0; i != _arc_num; ++i) {
    1252           Arc e = _arc_ref[i];
    1253           _source[i] = _node_id[_graph.source(e)];
    1254           _target[i] = _node_id[_graph.target(e)];
    1255           _flow[i] = 0;
    1256           _state[i] = STATE_LOWER;
    1257         }
    1258         if (_pupper) {
    1259           for (int i = 0; i != _arc_num; ++i)
    1260             _cap[i] = (*_pupper)[_arc_ref[i]];
    1261         } else {
    1262           for (int i = 0; i != _arc_num; ++i)
    1263             _cap[i] = inf_cap;
    1264         }
    1265         if (_pcost) {
    1266           for (int i = 0; i != _arc_num; ++i)
    1267             _cost[i] = (*_pcost)[_arc_ref[i]];
    1268         } else {
    1269           for (int i = 0; i != _arc_num; ++i)
    1270             _cost[i] = 1;
    1271         }
    1272       }
    1273      
    1274       // Remove non-zero lower bounds
    1275       if (_plower) {
    1276         for (int i = 0; i != _arc_num; ++i) {
    1277           Flow c = (*_plower)[_arc_ref[i]];
    1278           if (c != 0) {
    1279             _cap[i] -= c;
    1280             _supply[_source[i]] -= c;
    1281             _supply[_target[i]] += c;
    1282           }
    1283         }
    1284       }
     1095      _supply[_root] = -_sum_supply;
     1096      _pi[_root] = _sum_supply < 0 ? -ART_COST : ART_COST;
    12851097
    12861098      // Add artificial arcs and initialize the spanning tree data structure
    12871099      for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
     1100        _parent[u] = _root;
     1101        _pred[u] = e;
    12881102        _thread[u] = u + 1;
    12891103        _rev_thread[u + 1] = u;
    12901104        _succ_num[u] = 1;
    12911105        _last_succ[u] = u;
    1292         _parent[u] = _root;
    1293         _pred[u] = e;
    1294         _cost[e] = art_cost;
    1295         _cap[e] = inf_cap;
     1106        _cost[e] = ART_COST;
     1107        _cap[e] = INF;
    12961108        _state[e] = STATE_TREE;
    1297         if (_supply[u] > 0 || (_supply[u] == 0 && sum_supply <= 0)) {
     1109        if (_supply[u] > 0 || (_supply[u] == 0 && _sum_supply <= 0)) {
    12981110          _flow[e] = _supply[u];
    12991111          _forward[u] = true;
    1300           _pi[u] = -art_cost + _pi[_root];
     1112          _pi[u] = -ART_COST + _pi[_root];
    13011113        } else {
    13021114          _flow[e] = -_supply[u];
    13031115          _forward[u] = false;
    1304           _pi[u] = art_cost + _pi[_root];
     1116          _pi[u] = ART_COST + _pi[_root];
    13051117        }
    13061118      }
    … …  
    13371149      delta = _cap[in_arc];
    13381150      int result = 0;
    1339       Flow d;
     1151      Value d;
    13401152      int e;
    13411153
    … …  
    13431155      for (int u = first; u != join; u = _parent[u]) {
    13441156        e = _pred[u];
    1345         d = _forward[u] ? _flow[e] : _cap[e] - _flow[e];
     1157        d = _forward[u] ?
     1158          _flow[e] : (_cap[e] == INF ? INF : _cap[e] - _flow[e]);
    13461159        if (d < delta) {
    13471160          delta = d;
    … …  
    13531166      for (int u = second; u != join; u = _parent[u]) {
    13541167        e = _pred[u];
    1355         d = _forward[u] ? _cap[e] - _flow[e] : _flow[e];
     1168        d = _forward[u] ?
     1169          (_cap[e] == INF ? INF : _cap[e] - _flow[e]) : _flow[e];
    13561170        if (d <= delta) {
    13571171          delta = d;
    … …  
    13751189      // Augment along the cycle
    13761190      if (delta > 0) {
    1377         Flow val = _state[in_arc] * delta;
     1191        Value val = _state[in_arc] * delta;
    13781192        _flow[in_arc] += val;
    13791193        for (int u = _source[in_arc]; u != join; u = _parent[u]) {
    … …  
    15271341
    15281342    // Execute the algorithm
    1529     bool start(PivotRule pivot_rule) {
     1343    ProblemType start(PivotRule pivot_rule) {
    15301344      // Select the pivot rule implementation
    15311345      switch (pivot_rule) {
    … …  
    15411355          return start<AlteringListPivotRule>();
    15421356      }
    1543       return false;
     1357      return INFEASIBLE; // avoid warning
    15441358    }
    15451359
    15461360    template <typename PivotRuleImpl>
    1547     bool start() {
     1361    ProblemType start() {
    15481362      PivotRuleImpl pivot(*this);
    15491363
    … …  
    15521366        findJoinNode();
    15531367        bool change = findLeavingArc();
     1368        if (delta >= INF) return UNBOUNDED;
    15541369        changeFlow(change);
    15551370        if (change) {
    … …  
    15581373        }
    15591374      }
    1560 
    1561       // Copy flow values to _flow_map
    1562       if (_plower) {
     1375     
     1376      // Check feasibility
     1377      if (_sum_supply < 0) {
     1378        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
     1379          if (_supply[u] >= 0 && _flow[e] != 0) return INFEASIBLE;
     1380        }
     1381      }
     1382      else if (_sum_supply > 0) {
     1383        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
     1384          if (_supply[u] <= 0 && _flow[e] != 0) return INFEASIBLE;
     1385        }
     1386      }
     1387      else {
     1388        for (int u = 0, e = _arc_num; u != _node_num; ++u, ++e) {
     1389          if (_flow[e] != 0) return INFEASIBLE;
     1390        }
     1391      }
     1392
     1393      // Transform the solution and the supply map to the original form
     1394      if (_have_lower) {
    15631395        for (int i = 0; i != _arc_num; ++i) {
    1564           Arc e = _arc_ref[i];
    1565           _flow_map->set(e, (*_plower)[e] + _flow[i]);
    1566         }
    1567       } else {
    1568         for (int i = 0; i != _arc_num; ++i) {
    1569           _flow_map->set(_arc_ref[i], _flow[i]);
    1570         }
    1571       }
    1572       // Copy potential values to _potential_map
    1573       for (NodeIt n(_graph); n != INVALID; ++n) {
    1574         _potential_map->set(n, _pi[_node_id[n]]);
    1575       }
    1576 
    1577       return true;
     1396          Value c = _lower[i];
     1397          if (c != 0) {
     1398            _flow[i] += c;
     1399            _supply[_source[i]] += c;
     1400            _supply[_target[i]] -= c;
     1401          }
     1402        }
     1403      }
     1404
     1405      return OPTIMAL;
    15781406    }
    15791407

  • lemon/preflow.h

    r611 r641  
    4747
    4848    /// \brief The type of the flow values.
    49     typedef typename CapacityMap::Value Flow;
     49    typedef typename CapacityMap::Value Value;
    5050
    5151    /// \brief The type of the map that stores the flow values.
    … …  
    5353    /// The type of the map that stores the flow values.
    5454    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    55     typedef typename Digraph::template ArcMap<Flow> FlowMap;
     55    typedef typename Digraph::template ArcMap<Value> FlowMap;
    5656
    5757    /// \brief Instantiates a FlowMap.
    … …  
    8585    ///
    8686    /// The tolerance used by the algorithm to handle inexact computation.
    87     typedef lemon::Tolerance<Flow> Tolerance;
     87    typedef lemon::Tolerance<Value> Tolerance;
    8888
    8989  };
    … …  
    126126    typedef typename Traits::CapacityMap CapacityMap;
    127127    ///The type of the flow values.
    128     typedef typename Traits::Flow Flow;
     128    typedef typename Traits::Value Value;
    129129
    130130    ///The type of the flow map.
    … …  
    152152    bool _local_level;
    153153
    154     typedef typename Digraph::template NodeMap<Flow> ExcessMap;
     154    typedef typename Digraph::template NodeMap<Value> ExcessMap;
    155155    ExcessMap* _excess;
    156156
    … …  
    471471
    472472      for (NodeIt n(_graph); n != INVALID; ++n) {
    473         Flow excess = 0;
     473        Value excess = 0;
    474474        for (InArcIt e(_graph, n); e != INVALID; ++e) {
    475475          excess += (*_flow)[e];
    … …  
    520520
    521521      for (OutArcIt e(_graph, _source); e != INVALID; ++e) {
    522         Flow rem = (*_capacity)[e] - (*_flow)[e];
     522        Value rem = (*_capacity)[e] - (*_flow)[e];
    523523        if (_tolerance.positive(rem)) {
    524524          Node u = _graph.target(e);
    … …  
    532532      }
    533533      for (InArcIt e(_graph, _source); e != INVALID; ++e) {
    534         Flow rem = (*_flow)[e];
     534        Value rem = (*_flow)[e];
    535535        if (_tolerance.positive(rem)) {
    536536          Node v = _graph.source(e);
    … …  
    565565
    566566        while (num > 0 && n != INVALID) {
    567           Flow excess = (*_excess)[n];
     567          Value excess = (*_excess)[n];
    568568          int new_level = _level->maxLevel();
    569569
    570570          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    571             Flow rem = (*_capacity)[e] - (*_flow)[e];
     571            Value rem = (*_capacity)[e] - (*_flow)[e];
    572572            if (!_tolerance.positive(rem)) continue;
    573573            Node v = _graph.target(e);
    … …  
    592592
    593593          for (InArcIt e(_graph, n); e != INVALID; ++e) {
    594             Flow rem = (*_flow)[e];
     594            Value rem = (*_flow)[e];
    595595            if (!_tolerance.positive(rem)) continue;
    596596            Node v = _graph.source(e);
    … …  
    638638        num = _node_num * 20;
    639639        while (num > 0 && n != INVALID) {
    640           Flow excess = (*_excess)[n];
     640          Value excess = (*_excess)[n];
    641641          int new_level = _level->maxLevel();
    642642
    643643          for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    644             Flow rem = (*_capacity)[e] - (*_flow)[e];
     644            Value rem = (*_capacity)[e] - (*_flow)[e];
    645645            if (!_tolerance.positive(rem)) continue;
    646646            Node v = _graph.target(e);
    … …  
    665665
    666666          for (InArcIt e(_graph, n); e != INVALID; ++e) {
    667             Flow rem = (*_flow)[e];
     667            Value rem = (*_flow)[e];
    668668            if (!_tolerance.positive(rem)) continue;
    669669            Node v = _graph.source(e);
    … …  
    779779      Node n;
    780780      while ((n = _level->highestActive()) != INVALID) {
    781         Flow excess = (*_excess)[n];
     781        Value excess = (*_excess)[n];
    782782        int level = _level->highestActiveLevel();
    783783        int new_level = _level->maxLevel();
    784784
    785785        for (OutArcIt e(_graph, n); e != INVALID; ++e) {
    786           Flow rem = (*_capacity)[e] - (*_flow)[e];
     786          Value rem = (*_capacity)[e] - (*_flow)[e];
    787787          if (!_tolerance.positive(rem)) continue;
    788788          Node v = _graph.target(e);
    … …  
    807807
    808808        for (InArcIt e(_graph, n); e != INVALID; ++e) {
    809           Flow rem = (*_flow)[e];
     809          Value rem = (*_flow)[e];
    810810          if (!_tolerance.positive(rem)) continue;
    811811          Node v = _graph.source(e);
    … …  
    898898    /// \pre Either \ref run() or \ref init() must be called before
    899899    /// using this function.
    900     Flow flowValue() const {
     900    Value flowValue() const {
    901901      return (*_excess)[_target];
    902902    }
    903903
    904     /// \brief Returns the flow on the given arc.
    905     ///
    906     /// Returns the flow on the given arc. This method can
     904    /// \brief Returns the flow value on the given arc.
     905    ///
     906    /// Returns the flow value on the given arc. This method can
    907907    /// be called after the second phase of the algorithm.
    908908    ///
    909909    /// \pre Either \ref run() or \ref init() must be called before
    910910    /// using this function.
    911     Flow flow(const Arc& arc) const {
     911    Value flow(const Arc& arc) const {
    912912      return (*_flow)[arc];
    913913    }

  • test/lp_test.cc

    r627 r631  
    2222#include <lemon/tolerance.h>
    2323
    24 #ifdef HAVE_CONFIG_H
    2524#include <lemon/config.h>
    26 #endif
    2725
    2826#ifdef LEMON_HAVE_GLPK

  • test/min_cost_flow_test.cc

    r615 r642  
    1919#include <iostream>
    2020#include <fstream>
     21#include <limits>
    2122
    2223#include <lemon/list_graph.h>
    … …  
    3435char test_lgf[] =
    3536  "@nodes\n"
    36   "label  sup1 sup2 sup3 sup4 sup5\n"
    37   "    1    20   27    0   20   30\n"
    38   "    2    -4    0    0   -8   -3\n"
    39   "    3     0    0    0    0    0\n"
    40   "    4     0    0    0    0    0\n"
    41   "    5     9    0    0    6   11\n"
    42   "    6    -6    0    0   -5   -6\n"
    43   "    7     0    0    0    0    0\n"
    44   "    8     0    0    0    0    3\n"
    45   "    9     3    0    0    0    0\n"
    46   "   10    -2    0    0   -7   -2\n"
    47   "   11     0    0    0  -10    0\n"
    48   "   12   -20  -27    0  -30  -20\n"
    49   "\n"
     37  "label  sup1 sup2 sup3 sup4 sup5 sup6\n"
     38  "    1    20   27    0   30   20   30\n"
     39  "    2    -4    0    0    0   -8   -3\n"
     40  "    3     0    0    0    0    0    0\n"
     41  "    4     0    0    0    0    0    0\n"
     42  "    5     9    0    0    0    6   11\n"
     43  "    6    -6    0    0    0   -5   -6\n"
     44  "    7     0    0    0    0    0    0\n"
     45  "    8     0    0    0    0    0    3\n"
     46  "    9     3    0    0    0    0    0\n"
     47  "   10    -2    0    0    0   -7   -2\n"
     48  "   11     0    0    0    0  -10    0\n"
     49  "   12   -20  -27    0  -30  -30  -20\n"
     50  "\n"               
    5051  "@arcs\n"
    51   "       cost  cap low1 low2\n"
    52   " 1  2    70   11    0    8\n"
    53   " 1  3   150    3    0    1\n"
    54   " 1  4    80   15    0    2\n"
    55   " 2  8    80   12    0    0\n"
    56   " 3  5   140    5    0    3\n"
    57   " 4  6    60   10    0    1\n"
    58   " 4  7    80    2    0    0\n"
    59   " 4  8   110    3    0    0\n"
    60   " 5  7    60   14    0    0\n"
    61   " 5 11   120   12    0    0\n"
    62   " 6  3     0    3    0    0\n"
    63   " 6  9   140    4    0    0\n"
    64   " 6 10    90    8    0    0\n"
    65   " 7  1    30    5    0    0\n"
    66   " 8 12    60   16    0    4\n"
    67   " 9 12    50    6    0    0\n"
    68   "10 12    70   13    0    5\n"
    69   "10  2   100    7    0    0\n"
    70   "10  7    60   10    0    0\n"
    71   "11 10    20   14    0    6\n"
    72   "12 11    30   10    0    0\n"
     52  "       cost  cap low1 low2 low3\n"
     53  " 1  2    70   11    0    8    8\n"
     54  " 1  3   150    3    0    1    0\n"
     55  " 1  4    80   15    0    2    2\n"
     56  " 2  8    80   12    0    0    0\n"
     57  " 3  5   140    5    0    3    1\n"
     58  " 4  6    60   10    0    1    0\n"
     59  " 4  7    80    2    0    0    0\n"
     60  " 4  8   110    3    0    0    0\n"
     61  " 5  7    60   14    0    0    0\n"
     62  " 5 11   120   12    0    0    0\n"
     63  " 6  3     0    3    0    0    0\n"
     64  " 6  9   140    4    0    0    0\n"
     65  " 6 10    90    8    0    0    0\n"
     66  " 7  1    30    5    0    0   -5\n"
     67  " 8 12    60   16    0    4    3\n"
     68  " 9 12    50    6    0    0    0\n"
     69  "10 12    70   13    0    5    2\n"
     70  "10  2   100    7    0    0    0\n"
     71  "10  7    60   10    0    0   -3\n"
     72  "11 10    20   14    0    6  -20\n"
     73  "12 11    30   10    0    0  -10\n"
    7374  "\n"
    7475  "@attributes\n"
    … …  
    7778
    7879
    79 enum ProblemType {
     80enum SupplyType {
    8081  EQ,
    8182  GEQ,
    … …  
    8485
    8586// Check the interface of an MCF algorithm
    86 template <typename GR, typename Flow, typename Cost>
     87template <typename GR, typename Value, typename Cost>
    8788class McfClassConcept
    8889{
    … …  
    9596
    9697      MCF mcf(g);
     98      const MCF& const_mcf = mcf;
    9799
    98100      b = mcf.reset()
    99101             .lowerMap(lower)
    100102             .upperMap(upper)
    101              .capacityMap(upper)
    102              .boundMaps(lower, upper)
    103103             .costMap(cost)
    104104             .supplyMap(sup)
    105105             .stSupply(n, n, k)
    106              .flowMap(flow)
    107              .potentialMap(pot)
    108106             .run();
    109      
    110       const MCF& const_mcf = mcf;
    111 
    112       const typename MCF::FlowMap &fm = const_mcf.flowMap();
    113       const typename MCF::PotentialMap &pm = const_mcf.potentialMap();
    114 
    115       v = const_mcf.totalCost();
    116       double x = const_mcf.template totalCost<double>();
     107
     108      c = const_mcf.totalCost();
     109      x = const_mcf.template totalCost<double>();
    117110      v = const_mcf.flow(a);
    118       v = const_mcf.potential(n);
    119 
    120       ignore_unused_variable_warning(fm);
    121       ignore_unused_variable_warning(pm);
    122       ignore_unused_variable_warning(x);
     111      c = const_mcf.potential(n);
     112      const_mcf.flowMap(fm);
     113      const_mcf.potentialMap(pm);
    123114    }
    124115
    125116    typedef typename GR::Node Node;
    126117    typedef typename GR::Arc Arc;
    127     typedef concepts::ReadMap<Node, Flow> NM;
    128     typedef concepts::ReadMap<Arc, Flow> FAM;
     118    typedef concepts::ReadMap<Node, Value> NM;
     119    typedef concepts::ReadMap<Arc, Value> VAM;
    129120    typedef concepts::ReadMap<Arc, Cost> CAM;
     121    typedef concepts::WriteMap<Arc, Value> FlowMap;
     122    typedef concepts::WriteMap<Node, Cost> PotMap;
    130123
    131124    const GR &g;
    132     const FAM &lower;
    133     const FAM &upper;
     125    const VAM &lower;
     126    const VAM &upper;
    134127    const CAM &cost;
    135128    const NM &sup;
    136129    const Node &n;
    137130    const Arc &a;
    138     const Flow &k;
    139     Flow v;
     131    const Value &k;
     132    FlowMap fm;
     133    PotMap pm;
    140134    bool b;
    141 
    142     typename MCF::FlowMap &flow;
    143     typename MCF::PotentialMap &pot;
     135    double x;
     136    typename MCF::Value v;
     137    typename MCF::Cost c;
    144138  };
    145139
    … …  
    152146bool checkFlow( const GR& gr, const LM& lower, const UM& upper,
    153147                const SM& supply, const FM& flow,
    154                 ProblemType type = EQ )
     148                SupplyType type = EQ )
    155149{
    156150  TEMPLATE_DIGRAPH_TYPEDEFS(GR);
    … …  
    209203template < typename MCF, typename GR,
    210204           typename LM, typename UM,
    211            typename CM, typename SM >
    212 void checkMcf( const MCF& mcf, bool mcf_result,
     205           typename CM, typename SM,
     206           typename PT >
     207void checkMcf( const MCF& mcf, PT mcf_result,
    213208               const GR& gr, const LM& lower, const UM& upper,
    214209               const CM& cost, const SM& supply,
    215                bool result, typename CM::Value total,
     210               PT result, bool optimal, typename CM::Value total,
    216211               const std::string &test_id = "",
    217                ProblemType type = EQ )
     212               SupplyType type = EQ )
    218213{
    219214  check(mcf_result == result, "Wrong result " + test_id);
    220   if (result) {
    221     check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type),
     215  if (optimal) {
     216    typename GR::template ArcMap<typename SM::Value> flow(gr);
     217    typename GR::template NodeMap<typename CM::Value> pi(gr);
     218    mcf.flowMap(flow);
     219    mcf.potentialMap(pi);
     220    check(checkFlow(gr, lower, upper, supply, flow, type),
    222221          "The flow is not feasible " + test_id);
    223222    check(mcf.totalCost() == total, "The flow is not optimal " + test_id);
    224     check(checkPotential(gr, lower, upper, cost, supply, mcf.flowMap(),
    225                          mcf.potentialMap()),
     223    check(checkPotential(gr, lower, upper, cost, supply, flow, pi),
    226224          "Wrong potentials " + test_id);
    227225  }
    … …  
    232230  // Check the interfaces
    233231  {
    234     typedef int Flow;
    235     typedef int Cost;
    236232    typedef concepts::Digraph GR;
    237     checkConcept< McfClassConcept<GR, Flow, Cost>,
    238                   NetworkSimplex<GR, Flow, Cost> >();
     233    checkConcept< McfClassConcept<GR, int, int>,
     234                  NetworkSimplex<GR> >();
     235    checkConcept< McfClassConcept<GR, double, double>,
     236                  NetworkSimplex<GR, double> >();
     237    checkConcept< McfClassConcept<GR, int, double>,
     238                  NetworkSimplex<GR, int, double> >();
    239239  }
    240240
    … …  
    245245  // Read the test digraph
    246246  Digraph gr;
    247   Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), u(gr);
    248   Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr);
     247  Digraph::ArcMap<int> c(gr), l1(gr), l2(gr), l3(gr), u(gr);
     248  Digraph::NodeMap<int> s1(gr), s2(gr), s3(gr), s4(gr), s5(gr), s6(gr);
    249249  ConstMap<Arc, int> cc(1), cu(std::numeric_limits<int>::max());
    250250  Node v, w;
    … …  
    256256    .arcMap("low1", l1)
    257257    .arcMap("low2", l2)
     258    .arcMap("low3", l3)
    258259    .nodeMap("sup1", s1)
    259260    .nodeMap("sup2", s2)
    … …  
    261262    .nodeMap("sup4", s4)
    262263    .nodeMap("sup5", s5)
     264    .nodeMap("sup6", s6)
    263265    .node("source", v)
    264266    .node("target", w)
    265267    .run();
     268 
     269  // Build a test digraph for testing negative costs
     270  Digraph ngr;
     271  Node n1 = ngr.addNode();
     272  Node n2 = ngr.addNode();
     273  Node n3 = ngr.addNode();
     274  Node n4 = ngr.addNode();
     275  Node n5 = ngr.addNode();
     276  Node n6 = ngr.addNode();
     277  Node n7 = ngr.addNode();
     278 
     279  Arc a1 = ngr.addArc(n1, n2);
     280  Arc a2 = ngr.addArc(n1, n3);
     281  Arc a3 = ngr.addArc(n2, n4);
     282  Arc a4 = ngr.addArc(n3, n4);
     283  Arc a5 = ngr.addArc(n3, n2);
     284  Arc a6 = ngr.addArc(n5, n3);
     285  Arc a7 = ngr.addArc(n5, n6);
     286  Arc a8 = ngr.addArc(n6, n7);
     287  Arc a9 = ngr.addArc(n7, n5);
     288 
     289  Digraph::ArcMap<int> nc(ngr), nl1(ngr, 0), nl2(ngr, 0);
     290  ConstMap<Arc, int> nu1(std::numeric_limits<int>::max()), nu2(5000);
     291  Digraph::NodeMap<int> ns(ngr, 0);
     292 
     293  nl2[a7] =  1000;
     294  nl2[a8] = -1000;
     295 
     296  ns[n1] =  100;
     297  ns[n4] = -100;
     298 
     299  nc[a1] =  100;
     300  nc[a2] =   30;
     301  nc[a3] =   20;
     302  nc[a4] =   80;
     303  nc[a5] =   50;
     304  nc[a6] =   10;
     305  nc[a7] =   80;
     306  nc[a8] =   30;
     307  nc[a9] = -120;
    266308
    267309  // A. Test NetworkSimplex with the default pivot rule
    … …  
    272314    mcf.upperMap(u).costMap(c);
    273315    checkMcf(mcf, mcf.supplyMap(s1).run(),
    274              gr, l1, u, c, s1, true,  5240, "#A1");
     316             gr, l1, u, c, s1, mcf.OPTIMAL, true,   5240, "#A1");
    275317    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
    276              gr, l1, u, c, s2, true,  7620, "#A2");
     318             gr, l1, u, c, s2, mcf.OPTIMAL, true,   7620, "#A2");
    277319    mcf.lowerMap(l2);
    278320    checkMcf(mcf, mcf.supplyMap(s1).run(),
    279              gr, l2, u, c, s1, true,  5970, "#A3");
     321             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#A3");
    280322    checkMcf(mcf, mcf.stSupply(v, w, 27).run(),
    281              gr, l2, u, c, s2, true,  8010, "#A4");
     323             gr, l2, u, c, s2, mcf.OPTIMAL, true,   8010, "#A4");
    282324    mcf.reset();
    283325    checkMcf(mcf, mcf.supplyMap(s1).run(),
    284              gr, l1, cu, cc, s1, true,  74, "#A5");
     326             gr, l1, cu, cc, s1, mcf.OPTIMAL, true,   74, "#A5");
    285327    checkMcf(mcf, mcf.lowerMap(l2).stSupply(v, w, 27).run(),
    286              gr, l2, cu, cc, s2, true,  94, "#A6");
     328             gr, l2, cu, cc, s2, mcf.OPTIMAL, true,   94, "#A6");
    287329    mcf.reset();
    288330    checkMcf(mcf, mcf.run(),
    289              gr, l1, cu, cc, s3, true,   0, "#A7");
    290     checkMcf(mcf, mcf.boundMaps(l2, u).run(),
    291              gr, l2, u, cc, s3, false,   0, "#A8");
     331             gr, l1, cu, cc, s3, mcf.OPTIMAL, true,    0, "#A7");
     332    checkMcf(mcf, mcf.lowerMap(l2).upperMap(u).run(),
     333             gr, l2, u, cc, s3, mcf.INFEASIBLE, false, 0, "#A8");
     334    mcf.reset().lowerMap(l3).upperMap(u).costMap(c).supplyMap(s4);
     335    checkMcf(mcf, mcf.run(),
     336             gr, l3, u, c, s4, mcf.OPTIMAL, true,   6360, "#A9");
    292337
    293338    // Check the GEQ form
    294     mcf.reset().upperMap(u).costMap(c).supplyMap(s4);
    295     checkMcf(mcf, mcf.run(),
    296              gr, l1, u, c, s4, true,  3530, "#A9", GEQ);
    297     mcf.problemType(mcf.GEQ);
     339    mcf.reset().upperMap(u).costMap(c).supplyMap(s5);
     340    checkMcf(mcf, mcf.run(),
     341             gr, l1, u, c, s5, mcf.OPTIMAL, true,   3530, "#A10", GEQ);
     342    mcf.supplyType(mcf.GEQ);
    298343    checkMcf(mcf, mcf.lowerMap(l2).run(),
    299              gr, l2, u, c, s4, true,  4540, "#A10", GEQ);
    300     mcf.problemType(mcf.CARRY_SUPPLIES).supplyMap(s5);
    301     checkMcf(mcf, mcf.run(),
    302              gr, l2, u, c, s5, false,    0, "#A11", GEQ);
     344             gr, l2, u, c, s5, mcf.OPTIMAL, true,   4540, "#A11", GEQ);
     345    mcf.supplyType(mcf.CARRY_SUPPLIES).supplyMap(s6);
     346    checkMcf(mcf, mcf.run(),
     347             gr, l2, u, c, s6, mcf.INFEASIBLE, false,  0, "#A12", GEQ);
    303348
    304349    // Check the LEQ form
    305     mcf.reset().problemType(mcf.LEQ);
    306     mcf.upperMap(u).costMap(c).supplyMap(s5);
    307     checkMcf(mcf, mcf.run(),
    308              gr, l1, u, c, s5, true,  5080, "#A12", LEQ);
     350    mcf.reset().supplyType(mcf.LEQ);
     351    mcf.upperMap(u).costMap(c).supplyMap(s6);
     352    checkMcf(mcf, mcf.run(),
     353             gr, l1, u, c, s6, mcf.OPTIMAL, true,   5080, "#A13", LEQ);
    309354    checkMcf(mcf, mcf.lowerMap(l2).run(),
    310              gr, l2, u, c, s5, true,  5930, "#A13", LEQ);
    311     mcf.problemType(mcf.SATISFY_DEMANDS).supplyMap(s4);
    312     checkMcf(mcf, mcf.run(),
    313              gr, l2, u, c, s4, false,    0, "#A14", LEQ);
     355             gr, l2, u, c, s6, mcf.OPTIMAL, true,   5930, "#A14", LEQ);
     356    mcf.supplyType(mcf.SATISFY_DEMANDS).supplyMap(s5);
     357    checkMcf(mcf, mcf.run(),
     358             gr, l2, u, c, s5, mcf.INFEASIBLE, false,  0, "#A15", LEQ);
     359
     360    // Check negative costs
     361    NetworkSimplex<Digraph> nmcf(ngr);
     362    nmcf.lowerMap(nl1).costMap(nc).supplyMap(ns);
     363    checkMcf(nmcf, nmcf.run(),
     364      ngr, nl1, nu1, nc, ns, nmcf.UNBOUNDED, false,    0, "#A16");
     365    checkMcf(nmcf, nmcf.upperMap(nu2).run(),
     366      ngr, nl1, nu2, nc, ns, nmcf.OPTIMAL, true,  -40000, "#A17");
     367    nmcf.reset().lowerMap(nl2).costMap(nc).supplyMap(ns);
     368    checkMcf(nmcf, nmcf.run(),
     369      ngr, nl2, nu1, nc, ns, nmcf.UNBOUNDED, false,    0, "#A18");
    314370  }
    315371
    … …  
    317373  {
    318374    NetworkSimplex<Digraph> mcf(gr);
    319     mcf.supplyMap(s1).costMap(c).capacityMap(u).lowerMap(l2);
     375    mcf.supplyMap(s1).costMap(c).upperMap(u).lowerMap(l2);
    320376
    321377    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::FIRST_ELIGIBLE),
    322              gr, l2, u, c, s1, true,  5970, "#B1");
     378             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B1");
    323379    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BEST_ELIGIBLE),
    324              gr, l2, u, c, s1, true,  5970, "#B2");
     380             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B2");
    325381    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::BLOCK_SEARCH),
    326              gr, l2, u, c, s1, true,  5970, "#B3");
     382             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B3");
    327383    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::CANDIDATE_LIST),
    328              gr, l2, u, c, s1, true,  5970, "#B4");
     384             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B4");
    329385    checkMcf(mcf, mcf.run(NetworkSimplex<Digraph>::ALTERING_LIST),
    330              gr, l2, u, c, s1, true,  5970, "#B5");
     386             gr, l2, u, c, s1, mcf.OPTIMAL, true,   5970, "#B5");
    331387  }
    332388

  • test/mip_test.cc

    r627 r631  
    1919#include "test_tools.h"
    2020
    21 #ifdef HAVE_CONFIG_H
    2221#include <lemon/config.h>
    23 #endif
    2422
    2523#ifdef LEMON_HAVE_CPLEX

  • tools/dimacs-solver.cc

    r627 r644  
    120120  ti.restart();
    121121  NetworkSimplex<Digraph, Value> ns(g);
    122   ns.lowerMap(lower).capacityMap(cap).costMap(cost).supplyMap(sup);
    123   if (sum_sup > 0) ns.problemType(ns.LEQ);
     122  ns.lowerMap(lower).upperMap(cap).costMap(cost).supplyMap(sup);
     123  if (sum_sup > 0) ns.supplyType(ns.LEQ);
    124124  if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n';
    125125  ti.restart();
Note: See TracChangeset for help on using the changeset viewer.