Merge
authorAlpar Juttner <alpar@cs.elte.hu>
Sun, 26 Apr 2009 16:36:23 +0100
changeset 61858357e986a08
parent 617 029a48052c67
parent 616 1f631044c290
child 622 20dac2104519
child 624 70a356a461a5
child 636 6c408d864fa1
Merge
     1.1 --- a/CMakeLists.txt	Sun Apr 26 16:44:53 2009 +0200
     1.2 +++ b/CMakeLists.txt	Sun Apr 26 16:36:23 2009 +0100
     1.3 @@ -14,6 +14,8 @@
     1.4  INCLUDE(FindDoxygen)
     1.5  INCLUDE(FindGhostscript)
     1.6  FIND_PACKAGE(GLPK 4.33)
     1.7 +FIND_PACKAGE(CPLEX)
     1.8 +FIND_PACKAGE(COIN)
     1.9  
    1.10  ADD_DEFINITIONS(-DHAVE_CONFIG_H)
    1.11  
    1.12 @@ -26,12 +28,6 @@
    1.13  # C4996: 'function': was declared deprecated
    1.14  ENDIF(MSVC)
    1.15  
    1.16 -IF(GLPK_FOUND)
    1.17 -  SET(HAVE_LP TRUE)
    1.18 -  SET(HAVE_MIP TRUE)
    1.19 -  SET(HAVE_GLPK TRUE)
    1.20 -ENDIF(GLPK_FOUND)
    1.21 -
    1.22  INCLUDE(CheckTypeSize)
    1.23  CHECK_TYPE_SIZE("long long" LONG_LONG)
    1.24  
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/cmake/FindCOIN.cmake	Sun Apr 26 16:36:23 2009 +0100
     2.3 @@ -0,0 +1,68 @@
     2.4 +SET(COIN_ROOT_DIR "" CACHE PATH "COIN root directory")
     2.5 +
     2.6 +FIND_PATH(COIN_INCLUDE_DIR coin/CoinUtilsConfig.h
     2.7 +  PATHS ${COIN_ROOT_DIR}/include)
     2.8 +
     2.9 +FIND_LIBRARY(COIN_CBC_LIBRARY libCbc
    2.10 +  PATHS ${COIN_ROOT_DIR}/lib)
    2.11 +FIND_LIBRARY(COIN_CBC_SOLVER_LIBRARY libCbcSolver
    2.12 +  PATHS ${COIN_ROOT_DIR}/lib)
    2.13 +FIND_LIBRARY(COIN_CGL_LIBRARY libCgl
    2.14 +  PATHS ${COIN_ROOT_DIR}/lib)
    2.15 +FIND_LIBRARY(COIN_CLP_LIBRARY libClp
    2.16 +  PATHS ${COIN_ROOT_DIR}/lib)
    2.17 +FIND_LIBRARY(COIN_COIN_UTILS_LIBRARY libCoinUtils
    2.18 +  PATHS ${COIN_ROOT_DIR}/lib)
    2.19 +FIND_LIBRARY(COIN_OSI_LIBRARY libOsi
    2.20 +  PATHS ${COIN_ROOT_DIR}/lib)
    2.21 +FIND_LIBRARY(COIN_OSI_CBC_LIBRARY libOsiCbc
    2.22 +  PATHS ${COIN_ROOT_DIR}/lib)
    2.23 +FIND_LIBRARY(COIN_OSI_CLP_LIBRARY libOsiClp
    2.24 +  PATHS ${COIN_ROOT_DIR}/lib)
    2.25 +FIND_LIBRARY(COIN_OSI_VOL_LIBRARY libOsiVol
    2.26 +  PATHS ${COIN_ROOT_DIR}/lib)
    2.27 +FIND_LIBRARY(COIN_VOL_LIBRARY libVol
    2.28 +  PATHS ${COIN_ROOT_DIR}/lib)
    2.29 +
    2.30 +INCLUDE(FindPackageHandleStandardArgs)
    2.31 +FIND_PACKAGE_HANDLE_STANDARD_ARGS(COIN DEFAULT_MSG
    2.32 +  COIN_INCLUDE_DIR
    2.33 +  COIN_CBC_LIBRARY
    2.34 +  COIN_CBC_SOLVER_LIBRARY
    2.35 +  COIN_CGL_LIBRARY
    2.36 +  COIN_CLP_LIBRARY
    2.37 +  COIN_COIN_UTILS_LIBRARY
    2.38 +  COIN_OSI_LIBRARY
    2.39 +  COIN_OSI_CBC_LIBRARY
    2.40 +  COIN_OSI_CLP_LIBRARY
    2.41 +  COIN_OSI_VOL_LIBRARY
    2.42 +  COIN_VOL_LIBRARY
    2.43 +)
    2.44 +
    2.45 +IF(COIN_FOUND)
    2.46 +  SET(COIN_INCLUDE_DIRS ${COIN_INCLUDE_DIR})
    2.47 +  SET(COIN_LIBRARIES "${COIN_CBC_LIBRARY};${COIN_CBC_SOLVER_LIBRARY};${COIN_CGL_LIBRARY};${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY};${COIN_OSI_LIBRARY};${COIN_OSI_CBC_LIBRARY};${COIN_OSI_CLP_LIBRARY};${COIN_OSI_VOL_LIBRARY};${COIN_VOL_LIBRARY}")
    2.48 +  SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY}")
    2.49 +  SET(COIN_CBC_LIBRARIES ${COIN_LIBRARIES})
    2.50 +ENDIF(COIN_FOUND)
    2.51 +
    2.52 +MARK_AS_ADVANCED(
    2.53 +  COIN_INCLUDE_DIR
    2.54 +  COIN_CBC_LIBRARY
    2.55 +  COIN_CBC_SOLVER_LIBRARY
    2.56 +  COIN_CGL_LIBRARY
    2.57 +  COIN_CLP_LIBRARY
    2.58 +  COIN_COIN_UTILS_LIBRARY
    2.59 +  COIN_OSI_LIBRARY
    2.60 +  COIN_OSI_CBC_LIBRARY
    2.61 +  COIN_OSI_CLP_LIBRARY
    2.62 +  COIN_OSI_VOL_LIBRARY
    2.63 +  COIN_VOL_LIBRARY
    2.64 +)
    2.65 +
    2.66 +IF(COIN_FOUND)
    2.67 +  SET(HAVE_LP TRUE)
    2.68 +  SET(HAVE_MIP TRUE)
    2.69 +  SET(HAVE_CLP TRUE)
    2.70 +  SET(HAVE_CBC TRUE)
    2.71 +ENDIF(COIN_FOUND)
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/cmake/FindCPLEX.cmake	Sun Apr 26 16:36:23 2009 +0100
     3.3 @@ -0,0 +1,27 @@
     3.4 +FIND_PATH(CPLEX_INCLUDE_DIR
     3.5 +  ilcplex/cplex.h
     3.6 +  PATHS "C:/ILOG/CPLEX91/include")
     3.7 +
     3.8 +FIND_LIBRARY(CPLEX_LIBRARY
     3.9 +  NAMES cplex91
    3.10 +  PATHS "C:/ILOG/CPLEX91/lib/msvc7/stat_mda")
    3.11 +
    3.12 +INCLUDE(FindPackageHandleStandardArgs)
    3.13 +FIND_PACKAGE_HANDLE_STANDARD_ARGS(CPLEX DEFAULT_MSG CPLEX_LIBRARY CPLEX_INCLUDE_DIR)
    3.14 +
    3.15 +FIND_PATH(CPLEX_BIN_DIR
    3.16 +  cplex91.dll
    3.17 +  PATHS "C:/ILOG/CPLEX91/bin/x86_win32")
    3.18 +
    3.19 +IF(CPLEX_FOUND)
    3.20 +  SET(CPLEX_INCLUDE_DIRS ${CPLEX_INCLUDE_DIR})
    3.21 +  SET(CPLEX_LIBRARIES ${CPLEX_LIBRARY})
    3.22 +ENDIF(CPLEX_FOUND)
    3.23 +
    3.24 +MARK_AS_ADVANCED(CPLEX_LIBRARY CPLEX_INCLUDE_DIR CPLEX_BIN_DIR)
    3.25 +
    3.26 +IF(CPLEX_FOUND)
    3.27 +  SET(HAVE_LP TRUE)
    3.28 +  SET(HAVE_MIP TRUE)
    3.29 +  SET(HAVE_CPLEX TRUE)
    3.30 +ENDIF(CPLEX_FOUND)
     4.1 --- a/cmake/FindGLPK.cmake	Sun Apr 26 16:44:53 2009 +0200
     4.2 +++ b/cmake/FindGLPK.cmake	Sun Apr 26 16:36:23 2009 +0100
     4.3 @@ -13,8 +13,15 @@
     4.4  FIND_PACKAGE_HANDLE_STANDARD_ARGS(GLPK DEFAULT_MSG GLPK_LIBRARY GLPK_INCLUDE_DIR)
     4.5  
     4.6  IF(GLPK_FOUND)
     4.7 +  SET(GLPK_INCLUDE_DIRS ${GLPK_INCLUDE_DIR})
     4.8    SET(GLPK_LIBRARIES ${GLPK_LIBRARY})
     4.9    SET(GLPK_BIN_DIR ${GLPK_ROOT_PATH}/bin)
    4.10  ENDIF(GLPK_FOUND)
    4.11  
    4.12  MARK_AS_ADVANCED(GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_BIN_DIR)
    4.13 +
    4.14 +IF(GLPK_FOUND)
    4.15 +  SET(HAVE_LP TRUE)
    4.16 +  SET(HAVE_MIP TRUE)
    4.17 +  SET(HAVE_GLPK TRUE)
    4.18 +ENDIF(GLPK_FOUND)
     5.1 --- a/lemon/CMakeLists.txt	Sun Apr 26 16:44:53 2009 +0200
     5.2 +++ b/lemon/CMakeLists.txt	Sun Apr 26 16:36:23 2009 +0100
     5.3 @@ -20,7 +20,7 @@
     5.4  
     5.5  IF(HAVE_GLPK)
     5.6    SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc)
     5.7 -  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
     5.8 +  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS})
     5.9    IF(WIN32)
    5.10      INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin)
    5.11      INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin)
    5.12 @@ -28,6 +28,21 @@
    5.13    ENDIF(WIN32)
    5.14  ENDIF(HAVE_GLPK)
    5.15  
    5.16 +IF(HAVE_CPLEX)
    5.17 +  SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc)
    5.18 +  INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS})
    5.19 +ENDIF(HAVE_CPLEX)
    5.20 +
    5.21 +IF(HAVE_CLP)
    5.22 +  SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc)
    5.23 +  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
    5.24 +ENDIF(HAVE_CLP)
    5.25 +
    5.26 +IF(HAVE_CBC)
    5.27 +  SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc)
    5.28 +  INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS})
    5.29 +ENDIF(HAVE_CBC)
    5.30 +
    5.31  ADD_LIBRARY(lemon ${LEMON_SOURCES})
    5.32  
    5.33  INSTALL(
     6.1 --- a/lemon/circulation.h	Sun Apr 26 16:44:53 2009 +0200
     6.2 +++ b/lemon/circulation.h	Sun Apr 26 16:36:23 2009 +0100
     6.3 @@ -21,6 +21,7 @@
     6.4  
     6.5  #include <lemon/tolerance.h>
     6.6  #include <lemon/elevator.h>
     6.7 +#include <limits>
     6.8  
     6.9  ///\ingroup max_flow
    6.10  ///\file
    6.11 @@ -119,15 +120,15 @@
    6.12       at the nodes.
    6.13  
    6.14       The exact formulation of this problem is the following.
    6.15 -     Let \f$G=(V,A)\f$ be a digraph,
    6.16 -     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and
    6.17 -     upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$
    6.18 +     Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$
    6.19 +     \f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and
    6.20 +     upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$
    6.21       holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$
    6.22       denotes the signed supply values of the nodes.
    6.23       If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$
    6.24       supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with
    6.25       \f$-sup(u)\f$ demand.
    6.26 -     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$
    6.27 +     A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$
    6.28       solution of the following problem.
    6.29  
    6.30       \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu)
    6.31 @@ -151,6 +152,10 @@
    6.32       the direction of the arcs and taking the negative of the supply values
    6.33       (e.g. using \ref ReverseDigraph and \ref NegMap adaptors).
    6.34  
    6.35 +     This algorithm either calculates a feasible circulation, or provides
    6.36 +     a \ref barrier() "barrier", which prooves that a feasible soultion
    6.37 +     cannot exist.
    6.38 +
    6.39       Note that this algorithm also provides a feasible solution for the
    6.40       \ref min_cost_flow "minimum cost flow problem".
    6.41  
    6.42 @@ -337,6 +342,13 @@
    6.43  
    6.44    private:
    6.45  
    6.46 +    bool checkBoundMaps() {
    6.47 +      for (ArcIt e(_g);e!=INVALID;++e) {
    6.48 +        if (_tol.less((*_up)[e], (*_lo)[e])) return false;
    6.49 +      }
    6.50 +      return true;
    6.51 +    }
    6.52 +
    6.53      void createStructures() {
    6.54        _node_num = _el = countNodes(_g);
    6.55  
    6.56 @@ -380,7 +392,7 @@
    6.57  
    6.58      /// Sets the upper bound (capacity) map.
    6.59      /// \return <tt>(*this)</tt>
    6.60 -    Circulation& upperMap(const LowerMap& map) {
    6.61 +    Circulation& upperMap(const UpperMap& map) {
    6.62        _up = &map;
    6.63        return *this;
    6.64      }
    6.65 @@ -467,6 +479,9 @@
    6.66      /// to the lower bound.
    6.67      void init()
    6.68      {
    6.69 +      LEMON_DEBUG(checkBoundMaps(),
    6.70 +        "Upper bounds must be greater or equal to the lower bounds");
    6.71 +
    6.72        createStructures();
    6.73  
    6.74        for(NodeIt n(_g);n!=INVALID;++n) {
    6.75 @@ -496,6 +511,9 @@
    6.76      /// to construct the initial solution.
    6.77      void greedyInit()
    6.78      {
    6.79 +      LEMON_DEBUG(checkBoundMaps(),
    6.80 +        "Upper bounds must be greater or equal to the lower bounds");
    6.81 +
    6.82        createStructures();
    6.83  
    6.84        for(NodeIt n(_g);n!=INVALID;++n) {
    6.85 @@ -503,11 +521,11 @@
    6.86        }
    6.87  
    6.88        for (ArcIt e(_g);e!=INVALID;++e) {
    6.89 -        if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) {
    6.90 +        if (!_tol.less(-(*_excess)[_g.target(e)], (*_up)[e])) {
    6.91            _flow->set(e, (*_up)[e]);
    6.92            (*_excess)[_g.target(e)] += (*_up)[e];
    6.93            (*_excess)[_g.source(e)] -= (*_up)[e];
    6.94 -        } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) {
    6.95 +        } else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) {
    6.96            _flow->set(e, (*_lo)[e]);
    6.97            (*_excess)[_g.target(e)] += (*_lo)[e];
    6.98            (*_excess)[_g.source(e)] -= (*_lo)[e];
    6.99 @@ -748,6 +766,9 @@
   6.100      bool checkBarrier() const
   6.101      {
   6.102        Flow delta=0;
   6.103 +      Flow inf_cap = std::numeric_limits<Flow>::has_infinity ?
   6.104 +        std::numeric_limits<Flow>::infinity() :
   6.105 +        std::numeric_limits<Flow>::max();
   6.106        for(NodeIt n(_g);n!=INVALID;++n)
   6.107          if(barrier(n))
   6.108            delta-=(*_supply)[n];
   6.109 @@ -755,7 +776,10 @@
   6.110          {
   6.111            Node s=_g.source(e);
   6.112            Node t=_g.target(e);
   6.113 -          if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];
   6.114 +          if(barrier(s)&&!barrier(t)) {
   6.115 +            if (_tol.less(inf_cap - (*_up)[e], delta)) return false;
   6.116 +            delta+=(*_up)[e];
   6.117 +          }
   6.118            else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];
   6.119          }
   6.120        return _tol.negative(delta);
     7.1 --- a/lemon/config.h.cmake	Sun Apr 26 16:44:53 2009 +0200
     7.2 +++ b/lemon/config.h.cmake	Sun Apr 26 16:36:23 2009 +0100
     7.3 @@ -2,3 +2,6 @@
     7.4  #cmakedefine HAVE_LP 1
     7.5  #cmakedefine HAVE_MIP 1
     7.6  #cmakedefine HAVE_GLPK 1
     7.7 +#cmakedefine HAVE_CPLEX 1
     7.8 +#cmakedefine HAVE_CLP 1
     7.9 +#cmakedefine HAVE_CBC 1
     8.1 --- a/lemon/suurballe.h	Sun Apr 26 16:44:53 2009 +0200
     8.2 +++ b/lemon/suurballe.h	Sun Apr 26 16:36:23 2009 +0100
     8.3 @@ -25,6 +25,7 @@
     8.4  /// nodes having minimum total length.
     8.5  
     8.6  #include <vector>
     8.7 +#include <limits>
     8.8  #include <lemon/bin_heap.h>
     8.9  #include <lemon/path.h>
    8.10  #include <lemon/list_graph.h>
    8.11 @@ -42,22 +43,26 @@
    8.12    /// finding arc-disjoint paths having minimum total length (cost)
    8.13    /// from a given source node to a given target node in a digraph.
    8.14    ///
    8.15 -  /// In fact, this implementation is the specialization of the
    8.16 -  /// \ref CapacityScaling "successive shortest path" algorithm.
    8.17 +  /// Note that this problem is a special case of the \ref min_cost_flow
    8.18 +  /// "minimum cost flow problem". This implementation is actually an
    8.19 +  /// efficient specialized version of the \ref CapacityScaling
    8.20 +  /// "Successive Shortest Path" algorithm directly for this problem.
    8.21 +  /// Therefore this class provides query functions for flow values and
    8.22 +  /// node potentials (the dual solution) just like the minimum cost flow
    8.23 +  /// algorithms.
    8.24    ///
    8.25    /// \tparam GR The digraph type the algorithm runs on.
    8.26 -  /// The default value is \c ListDigraph.
    8.27 -  /// \tparam LEN The type of the length (cost) map.
    8.28 -  /// The default value is <tt>Digraph::ArcMap<int></tt>.
    8.29 +  /// \tparam LEN The type of the length map.
    8.30 +  /// The default value is <tt>GR::ArcMap<int></tt>.
    8.31    ///
    8.32    /// \warning Length values should be \e non-negative \e integers.
    8.33    ///
    8.34    /// \note For finding node-disjoint paths this algorithm can be used
    8.35 -  /// with \ref SplitNodes.
    8.36 +  /// along with the \ref SplitNodes adaptor.
    8.37  #ifdef DOXYGEN
    8.38    template <typename GR, typename LEN>
    8.39  #else
    8.40 -  template < typename GR = ListDigraph,
    8.41 +  template < typename GR,
    8.42               typename LEN = typename GR::template ArcMap<int> >
    8.43  #endif
    8.44    class Suurballe
    8.45 @@ -75,23 +80,28 @@
    8.46      typedef LEN LengthMap;
    8.47      /// The type of the lengths.
    8.48      typedef typename LengthMap::Value Length;
    8.49 +#ifdef DOXYGEN
    8.50 +    /// The type of the flow map.
    8.51 +    typedef GR::ArcMap<int> FlowMap;
    8.52 +    /// The type of the potential map.
    8.53 +    typedef GR::NodeMap<Length> PotentialMap;
    8.54 +#else
    8.55      /// The type of the flow map.
    8.56      typedef typename Digraph::template ArcMap<int> FlowMap;
    8.57      /// The type of the potential map.
    8.58      typedef typename Digraph::template NodeMap<Length> PotentialMap;
    8.59 +#endif
    8.60 +
    8.61      /// The type of the path structures.
    8.62 -    typedef SimplePath<Digraph> Path;
    8.63 +    typedef SimplePath<GR> Path;
    8.64  
    8.65    private:
    8.66  
    8.67 -    /// \brief Special implementation of the Dijkstra algorithm
    8.68 -    /// for finding shortest paths in the residual network.
    8.69 -    ///
    8.70 -    /// \ref ResidualDijkstra is a special implementation of the
    8.71 -    /// \ref Dijkstra algorithm for finding shortest paths in the
    8.72 -    /// residual network of the digraph with respect to the reduced arc
    8.73 -    /// lengths and modifying the node potentials according to the
    8.74 -    /// distance of the nodes.
    8.75 +    // ResidualDijkstra is a special implementation of the
    8.76 +    // Dijkstra algorithm for finding shortest paths in the
    8.77 +    // residual network with respect to the reduced arc lengths
    8.78 +    // and modifying the node potentials according to the
    8.79 +    // distance of the nodes.
    8.80      class ResidualDijkstra
    8.81      {
    8.82        typedef typename Digraph::template NodeMap<int> HeapCrossRef;
    8.83 @@ -120,14 +130,14 @@
    8.84      public:
    8.85  
    8.86        /// Constructor.
    8.87 -      ResidualDijkstra( const Digraph &digraph,
    8.88 +      ResidualDijkstra( const Digraph &graph,
    8.89                          const FlowMap &flow,
    8.90                          const LengthMap &length,
    8.91                          PotentialMap &potential,
    8.92                          PredMap &pred,
    8.93                          Node s, Node t ) :
    8.94 -        _graph(digraph), _flow(flow), _length(length), _potential(potential),
    8.95 -        _dist(digraph), _pred(pred), _s(s), _t(t) {}
    8.96 +        _graph(graph), _flow(flow), _length(length), _potential(potential),
    8.97 +        _dist(graph), _pred(pred), _s(s), _t(t) {}
    8.98  
    8.99        /// \brief Run the algorithm. It returns \c true if a path is found
   8.100        /// from the source node to the target node.
   8.101 @@ -236,16 +246,16 @@
   8.102      ///
   8.103      /// Constructor.
   8.104      ///
   8.105 -    /// \param digraph The digraph the algorithm runs on.
   8.106 +    /// \param graph The digraph the algorithm runs on.
   8.107      /// \param length The length (cost) values of the arcs.
   8.108 -    /// \param s The source node.
   8.109 -    /// \param t The target node.
   8.110 -    Suurballe( const Digraph &digraph,
   8.111 -               const LengthMap &length,
   8.112 -               Node s, Node t ) :
   8.113 -      _graph(digraph), _length(length), _flow(0), _local_flow(false),
   8.114 -      _potential(0), _local_potential(false), _source(s), _target(t),
   8.115 -      _pred(digraph) {}
   8.116 +    Suurballe( const Digraph &graph,
   8.117 +               const LengthMap &length ) :
   8.118 +      _graph(graph), _length(length), _flow(0), _local_flow(false),
   8.119 +      _potential(0), _local_potential(false), _pred(graph)
   8.120 +    {
   8.121 +      LEMON_ASSERT(std::numeric_limits<Length>::is_integer,
   8.122 +        "The length type of Suurballe must be integer");
   8.123 +    }
   8.124  
   8.125      /// Destructor.
   8.126      ~Suurballe() {
   8.127 @@ -257,9 +267,12 @@
   8.128      /// \brief Set the flow map.
   8.129      ///
   8.130      /// This function sets the flow map.
   8.131 +    /// If it is not used before calling \ref run() or \ref init(),
   8.132 +    /// an instance will be allocated automatically. The destructor
   8.133 +    /// deallocates this automatically allocated map, of course.
   8.134      ///
   8.135 -    /// The found flow contains only 0 and 1 values. It is the union of
   8.136 -    /// the found arc-disjoint paths.
   8.137 +    /// The found flow contains only 0 and 1 values, since it is the
   8.138 +    /// union of the found arc-disjoint paths.
   8.139      ///
   8.140      /// \return <tt>(*this)</tt>
   8.141      Suurballe& flowMap(FlowMap &map) {
   8.142 @@ -274,9 +287,12 @@
   8.143      /// \brief Set the potential map.
   8.144      ///
   8.145      /// This function sets the potential map.
   8.146 +    /// If it is not used before calling \ref run() or \ref init(),
   8.147 +    /// an instance will be allocated automatically. The destructor
   8.148 +    /// deallocates this automatically allocated map, of course.
   8.149      ///
   8.150 -    /// The potentials provide the dual solution of the underlying
   8.151 -    /// minimum cost flow problem.
   8.152 +    /// The node potentials provide the dual solution of the underlying
   8.153 +    /// \ref min_cost_flow "minimum cost flow problem".
   8.154      ///
   8.155      /// \return <tt>(*this)</tt>
   8.156      Suurballe& potentialMap(PotentialMap &map) {
   8.157 @@ -301,22 +317,24 @@
   8.158      ///
   8.159      /// This function runs the algorithm.
   8.160      ///
   8.161 +    /// \param s The source node.
   8.162 +    /// \param t The target node.
   8.163      /// \param k The number of paths to be found.
   8.164      ///
   8.165      /// \return \c k if there are at least \c k arc-disjoint paths from
   8.166      /// \c s to \c t in the digraph. Otherwise it returns the number of
   8.167      /// arc-disjoint paths found.
   8.168      ///
   8.169 -    /// \note Apart from the return value, <tt>s.run(k)</tt> is just a
   8.170 -    /// shortcut of the following code.
   8.171 +    /// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is
   8.172 +    /// just a shortcut of the following code.
   8.173      /// \code
   8.174 -    ///   s.init();
   8.175 -    ///   s.findFlow(k);
   8.176 +    ///   s.init(s);
   8.177 +    ///   s.findFlow(t, k);
   8.178      ///   s.findPaths();
   8.179      /// \endcode
   8.180 -    int run(int k = 2) {
   8.181 -      init();
   8.182 -      findFlow(k);
   8.183 +    int run(const Node& s, const Node& t, int k = 2) {
   8.184 +      init(s);
   8.185 +      findFlow(t, k);
   8.186        findPaths();
   8.187        return _path_num;
   8.188      }
   8.189 @@ -324,7 +342,11 @@
   8.190      /// \brief Initialize the algorithm.
   8.191      ///
   8.192      /// This function initializes the algorithm.
   8.193 -    void init() {
   8.194 +    ///
   8.195 +    /// \param s The source node.
   8.196 +    void init(const Node& s) {
   8.197 +      _source = s;
   8.198 +
   8.199        // Initialize maps
   8.200        if (!_flow) {
   8.201          _flow = new FlowMap(_graph);
   8.202 @@ -336,25 +358,28 @@
   8.203        }
   8.204        for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0;
   8.205        for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0;
   8.206 -
   8.207 -      _dijkstra = new ResidualDijkstra( _graph, *_flow, _length,
   8.208 -                                        *_potential, _pred,
   8.209 -                                        _source, _target );
   8.210      }
   8.211  
   8.212 -    /// \brief Execute the successive shortest path algorithm to find
   8.213 -    /// an optimal flow.
   8.214 +    /// \brief Execute the algorithm to find an optimal flow.
   8.215      ///
   8.216      /// This function executes the successive shortest path algorithm to
   8.217 -    /// find a minimum cost flow, which is the union of \c k or less
   8.218 +    /// find a minimum cost flow, which is the union of \c k (or less)
   8.219      /// arc-disjoint paths.
   8.220      ///
   8.221 +    /// \param t The target node.
   8.222 +    /// \param k The number of paths to be found.
   8.223 +    ///
   8.224      /// \return \c k if there are at least \c k arc-disjoint paths from
   8.225 -    /// \c s to \c t in the digraph. Otherwise it returns the number of
   8.226 -    /// arc-disjoint paths found.
   8.227 +    /// the source node to the given node \c t in the digraph.
   8.228 +    /// Otherwise it returns the number of arc-disjoint paths found.
   8.229      ///
   8.230      /// \pre \ref init() must be called before using this function.
   8.231 -    int findFlow(int k = 2) {
   8.232 +    int findFlow(const Node& t, int k = 2) {
   8.233 +      _target = t;
   8.234 +      _dijkstra =
   8.235 +        new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred,
   8.236 +                              _source, _target );
   8.237 +
   8.238        // Find shortest paths
   8.239        _path_num = 0;
   8.240        while (_path_num < k) {
   8.241 @@ -380,13 +405,12 @@
   8.242  
   8.243      /// \brief Compute the paths from the flow.
   8.244      ///
   8.245 -    /// This function computes the paths from the flow.
   8.246 +    /// This function computes the paths from the found minimum cost flow,
   8.247 +    /// which is the union of some arc-disjoint paths.
   8.248      ///
   8.249      /// \pre \ref init() and \ref findFlow() must be called before using
   8.250      /// this function.
   8.251      void findPaths() {
   8.252 -      // Create the residual flow map (the union of the paths not found
   8.253 -      // so far)
   8.254        FlowMap res_flow(_graph);
   8.255        for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a];
   8.256  
   8.257 @@ -413,10 +437,37 @@
   8.258  
   8.259      /// @{
   8.260  
   8.261 -    /// \brief Return a const reference to the arc map storing the
   8.262 +    /// \brief Return the total length of the found paths.
   8.263 +    ///
   8.264 +    /// This function returns the total length of the found paths, i.e.
   8.265 +    /// the total cost of the found flow.
   8.266 +    /// The complexity of the function is O(e).
   8.267 +    ///
   8.268 +    /// \pre \ref run() or \ref findFlow() must be called before using
   8.269 +    /// this function.
   8.270 +    Length totalLength() const {
   8.271 +      Length c = 0;
   8.272 +      for (ArcIt e(_graph); e != INVALID; ++e)
   8.273 +        c += (*_flow)[e] * _length[e];
   8.274 +      return c;
   8.275 +    }
   8.276 +
   8.277 +    /// \brief Return the flow value on the given arc.
   8.278 +    ///
   8.279 +    /// This function returns the flow value on the given arc.
   8.280 +    /// It is \c 1 if the arc is involved in one of the found arc-disjoint
   8.281 +    /// paths, otherwise it is \c 0.
   8.282 +    ///
   8.283 +    /// \pre \ref run() or \ref findFlow() must be called before using
   8.284 +    /// this function.
   8.285 +    int flow(const Arc& arc) const {
   8.286 +      return (*_flow)[arc];
   8.287 +    }
   8.288 +
   8.289 +    /// \brief Return a const reference to an arc map storing the
   8.290      /// found flow.
   8.291      ///
   8.292 -    /// This function returns a const reference to the arc map storing
   8.293 +    /// This function returns a const reference to an arc map storing
   8.294      /// the flow that is the union of the found arc-disjoint paths.
   8.295      ///
   8.296      /// \pre \ref run() or \ref findFlow() must be called before using
   8.297 @@ -425,34 +476,11 @@
   8.298        return *_flow;
   8.299      }
   8.300  
   8.301 -    /// \brief Return a const reference to the node map storing the
   8.302 -    /// found potentials (the dual solution).
   8.303 -    ///
   8.304 -    /// This function returns a const reference to the node map storing
   8.305 -    /// the found potentials that provide the dual solution of the
   8.306 -    /// underlying minimum cost flow problem.
   8.307 -    ///
   8.308 -    /// \pre \ref run() or \ref findFlow() must be called before using
   8.309 -    /// this function.
   8.310 -    const PotentialMap& potentialMap() const {
   8.311 -      return *_potential;
   8.312 -    }
   8.313 -
   8.314 -    /// \brief Return the flow on the given arc.
   8.315 -    ///
   8.316 -    /// This function returns the flow on the given arc.
   8.317 -    /// It is \c 1 if the arc is involved in one of the found paths,
   8.318 -    /// otherwise it is \c 0.
   8.319 -    ///
   8.320 -    /// \pre \ref run() or \ref findFlow() must be called before using
   8.321 -    /// this function.
   8.322 -    int flow(const Arc& arc) const {
   8.323 -      return (*_flow)[arc];
   8.324 -    }
   8.325 -
   8.326      /// \brief Return the potential of the given node.
   8.327      ///
   8.328      /// This function returns the potential of the given node.
   8.329 +    /// The node potentials provide the dual solution of the
   8.330 +    /// underlying \ref min_cost_flow "minimum cost flow problem".
   8.331      ///
   8.332      /// \pre \ref run() or \ref findFlow() must be called before using
   8.333      /// this function.
   8.334 @@ -460,18 +488,17 @@
   8.335        return (*_potential)[node];
   8.336      }
   8.337  
   8.338 -    /// \brief Return the total length (cost) of the found paths (flow).
   8.339 +    /// \brief Return a const reference to a node map storing the
   8.340 +    /// found potentials (the dual solution).
   8.341      ///
   8.342 -    /// This function returns the total length (cost) of the found paths
   8.343 -    /// (flow). The complexity of the function is O(e).
   8.344 +    /// This function returns a const reference to a node map storing
   8.345 +    /// the found potentials that provide the dual solution of the
   8.346 +    /// underlying \ref min_cost_flow "minimum cost flow problem".
   8.347      ///
   8.348      /// \pre \ref run() or \ref findFlow() must be called before using
   8.349      /// this function.
   8.350 -    Length totalLength() const {
   8.351 -      Length c = 0;
   8.352 -      for (ArcIt e(_graph); e != INVALID; ++e)
   8.353 -        c += (*_flow)[e] * _length[e];
   8.354 -      return c;
   8.355 +    const PotentialMap& potentialMap() const {
   8.356 +      return *_potential;
   8.357      }
   8.358  
   8.359      /// \brief Return the number of the found paths.
   8.360 @@ -488,7 +515,7 @@
   8.361      ///
   8.362      /// This function returns a const reference to the specified path.
   8.363      ///
   8.364 -    /// \param i The function returns the \c i-th path.
   8.365 +    /// \param i The function returns the <tt>i</tt>-th path.
   8.366      /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>.
   8.367      ///
   8.368      /// \pre \ref run() or \ref findPaths() must be called before using
     9.1 --- a/test/CMakeLists.txt	Sun Apr 26 16:44:53 2009 +0200
     9.2 +++ b/test/CMakeLists.txt	Sun Apr 26 16:36:23 2009 +0100
     9.3 @@ -3,10 +3,6 @@
     9.4    ${PROJECT_BINARY_DIR}
     9.5  )
     9.6  
     9.7 -IF(HAVE_GLPK)
     9.8 -  INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})
     9.9 -ENDIF(HAVE_GLPK)
    9.10 -
    9.11  LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon)
    9.12  
    9.13  SET(TESTS
    9.14 @@ -42,9 +38,17 @@
    9.15  
    9.16  IF(HAVE_LP)
    9.17    ADD_EXECUTABLE(lp_test lp_test.cc)
    9.18 +  SET(LP_TEST_LIBS lemon)
    9.19    IF(HAVE_GLPK)
    9.20 -    TARGET_LINK_LIBRARIES(lp_test lemon ${GLPK_LIBRARIES})
    9.21 +    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${GLPK_LIBRARIES})
    9.22    ENDIF(HAVE_GLPK)
    9.23 +  IF(HAVE_CPLEX)
    9.24 +    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES})
    9.25 +  ENDIF(HAVE_CPLEX)
    9.26 +  IF(HAVE_CLP)
    9.27 +    SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${COIN_CLP_LIBRARIES})
    9.28 +  ENDIF(HAVE_CLP)
    9.29 +  TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS})
    9.30    ADD_TEST(lp_test lp_test)
    9.31  
    9.32    IF(WIN32 AND HAVE_GLPK)
    9.33 @@ -56,13 +60,28 @@
    9.34        COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
    9.35      )
    9.36    ENDIF(WIN32 AND HAVE_GLPK)
    9.37 +  IF(WIN32 AND HAVE_CPLEX)
    9.38 +    GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION)
    9.39 +    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
    9.40 +    ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD
    9.41 +      COMMAND cmake -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
    9.42 +    )
    9.43 +  ENDIF(WIN32 AND HAVE_CPLEX)
    9.44  ENDIF(HAVE_LP)
    9.45  
    9.46  IF(HAVE_MIP)
    9.47    ADD_EXECUTABLE(mip_test mip_test.cc)
    9.48 +  SET(MIP_TEST_LIBS lemon)
    9.49    IF(HAVE_GLPK)
    9.50 -    TARGET_LINK_LIBRARIES(mip_test lemon ${GLPK_LIBRARIES})
    9.51 +    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${GLPK_LIBRARIES})
    9.52    ENDIF(HAVE_GLPK)
    9.53 +  IF(HAVE_CPLEX)
    9.54 +    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${CPLEX_LIBRARIES})
    9.55 +  ENDIF(HAVE_CPLEX)
    9.56 +  IF(HAVE_CBC)
    9.57 +    SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${COIN_CBC_LIBRARIES})
    9.58 +  ENDIF(HAVE_CBC)
    9.59 +  TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS})
    9.60    ADD_TEST(mip_test mip_test)
    9.61  
    9.62    IF(WIN32 AND HAVE_GLPK)
    9.63 @@ -74,6 +93,13 @@
    9.64        COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH}
    9.65      )
    9.66    ENDIF(WIN32 AND HAVE_GLPK)
    9.67 +  IF(WIN32 AND HAVE_CPLEX)
    9.68 +    GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION)
    9.69 +    GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH)
    9.70 +    ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD
    9.71 +      COMMAND cmake -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH}
    9.72 +    )
    9.73 +  ENDIF(WIN32 AND HAVE_CPLEX)
    9.74  ENDIF(HAVE_MIP)
    9.75  
    9.76  FOREACH(TEST_NAME ${TESTS})
    10.1 --- a/test/suurballe_test.cc	Sun Apr 26 16:44:53 2009 +0200
    10.2 +++ b/test/suurballe_test.cc	Sun Apr 26 16:36:23 2009 +0100
    10.3 @@ -22,6 +22,7 @@
    10.4  #include <lemon/lgf_reader.h>
    10.5  #include <lemon/path.h>
    10.6  #include <lemon/suurballe.h>
    10.7 +#include <lemon/concepts/digraph.h>
    10.8  
    10.9  #include "test_tools.h"
   10.10  
   10.11 @@ -29,47 +30,97 @@
   10.12  
   10.13  char test_lgf[] =
   10.14    "@nodes\n"
   10.15 -  "label supply1 supply2 supply3\n"
   10.16 -  "1     0        20      27\n"
   10.17 -  "2     0       -4        0\n"
   10.18 -  "3     0        0        0\n"
   10.19 -  "4     0        0        0\n"
   10.20 -  "5     0        9        0\n"
   10.21 -  "6     0       -6        0\n"
   10.22 -  "7     0        0        0\n"
   10.23 -  "8     0        0        0\n"
   10.24 -  "9     0        3        0\n"
   10.25 -  "10    0       -2        0\n"
   10.26 -  "11    0        0        0\n"
   10.27 -  "12    0       -20     -27\n"
   10.28 +  "label\n"
   10.29 +  "1\n"
   10.30 +  "2\n"
   10.31 +  "3\n"
   10.32 +  "4\n"
   10.33 +  "5\n"
   10.34 +  "6\n"
   10.35 +  "7\n"
   10.36 +  "8\n"
   10.37 +  "9\n"
   10.38 +  "10\n"
   10.39 +  "11\n"
   10.40 +  "12\n"
   10.41    "@arcs\n"
   10.42 -  "      cost capacity lower1 lower2\n"
   10.43 -  " 1  2  70  11       0      8\n"
   10.44 -  " 1  3 150   3       0      1\n"
   10.45 -  " 1  4  80  15       0      2\n"
   10.46 -  " 2  8  80  12       0      0\n"
   10.47 -  " 3  5 140   5       0      3\n"
   10.48 -  " 4  6  60  10       0      1\n"
   10.49 -  " 4  7  80   2       0      0\n"
   10.50 -  " 4  8 110   3       0      0\n"
   10.51 -  " 5  7  60  14       0      0\n"
   10.52 -  " 5 11 120  12       0      0\n"
   10.53 -  " 6  3   0   3       0      0\n"
   10.54 -  " 6  9 140   4       0      0\n"
   10.55 -  " 6 10  90   8       0      0\n"
   10.56 -  " 7  1  30   5       0      0\n"
   10.57 -  " 8 12  60  16       0      4\n"
   10.58 -  " 9 12  50   6       0      0\n"
   10.59 -  "10 12  70  13       0      5\n"
   10.60 -  "10  2 100   7       0      0\n"
   10.61 -  "10  7  60  10       0      0\n"
   10.62 -  "11 10  20  14       0      6\n"
   10.63 -  "12 11  30  10       0      0\n"
   10.64 +  "      length\n"
   10.65 +  " 1  2  70\n"
   10.66 +  " 1  3 150\n"
   10.67 +  " 1  4  80\n"
   10.68 +  " 2  8  80\n"
   10.69 +  " 3  5 140\n"
   10.70 +  " 4  6  60\n"
   10.71 +  " 4  7  80\n"
   10.72 +  " 4  8 110\n"
   10.73 +  " 5  7  60\n"
   10.74 +  " 5 11 120\n"
   10.75 +  " 6  3   0\n"
   10.76 +  " 6  9 140\n"
   10.77 +  " 6 10  90\n"
   10.78 +  " 7  1  30\n"
   10.79 +  " 8 12  60\n"
   10.80 +  " 9 12  50\n"
   10.81 +  "10 12  70\n"
   10.82 +  "10  2 100\n"
   10.83 +  "10  7  60\n"
   10.84 +  "11 10  20\n"
   10.85 +  "12 11  30\n"
   10.86    "@attributes\n"
   10.87    "source  1\n"
   10.88    "target 12\n"
   10.89    "@end\n";
   10.90  
   10.91 +// Check the interface of Suurballe
   10.92 +void checkSuurballeCompile()
   10.93 +{
   10.94 +  typedef int VType;
   10.95 +  typedef concepts::Digraph Digraph;
   10.96 +
   10.97 +  typedef Digraph::Node Node;
   10.98 +  typedef Digraph::Arc Arc;
   10.99 +  typedef concepts::ReadMap<Arc, VType> LengthMap;
  10.100 +  
  10.101 +  typedef Suurballe<Digraph, LengthMap> SuurballeType;
  10.102 +
  10.103 +  Digraph g;
  10.104 +  Node n;
  10.105 +  Arc e;
  10.106 +  LengthMap len;
  10.107 +  SuurballeType::FlowMap flow(g);
  10.108 +  SuurballeType::PotentialMap pi(g);
  10.109 +
  10.110 +  SuurballeType suurb_test(g, len);
  10.111 +  const SuurballeType& const_suurb_test = suurb_test;
  10.112 +
  10.113 +  suurb_test
  10.114 +    .flowMap(flow)
  10.115 +    .potentialMap(pi);
  10.116 +
  10.117 +  int k;
  10.118 +  k = suurb_test.run(n, n);
  10.119 +  k = suurb_test.run(n, n, k);
  10.120 +  suurb_test.init(n);
  10.121 +  k = suurb_test.findFlow(n);
  10.122 +  k = suurb_test.findFlow(n, k);
  10.123 +  suurb_test.findPaths();
  10.124 +  
  10.125 +  int f;
  10.126 +  VType c;
  10.127 +  c = const_suurb_test.totalLength();
  10.128 +  f = const_suurb_test.flow(e);
  10.129 +  const SuurballeType::FlowMap& fm =
  10.130 +    const_suurb_test.flowMap();
  10.131 +  c = const_suurb_test.potential(n);
  10.132 +  const SuurballeType::PotentialMap& pm =
  10.133 +    const_suurb_test.potentialMap();
  10.134 +  k = const_suurb_test.pathNum();
  10.135 +  Path<Digraph> p = const_suurb_test.path(k);
  10.136 +  
  10.137 +  ignore_unused_variable_warning(fm);
  10.138 +  ignore_unused_variable_warning(pm);
  10.139 +}
  10.140 +
  10.141  // Check the feasibility of the flow
  10.142  template <typename Digraph, typename FlowMap>
  10.143  bool checkFlow( const Digraph& gr, const FlowMap& flow,
  10.144 @@ -118,7 +169,6 @@
  10.145  bool checkPath( const Digraph& gr, const Path& path,
  10.146                  typename Digraph::Node s, typename Digraph::Node t)
  10.147  {
  10.148 -  // Check the "Complementary Slackness" optimality condition
  10.149    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
  10.150    Node n = s;
  10.151    for (int i = 0; i < path.length(); ++i) {
  10.152 @@ -136,58 +186,55 @@
  10.153    // Read the test digraph
  10.154    ListDigraph digraph;
  10.155    ListDigraph::ArcMap<int> length(digraph);
  10.156 -  Node source, target;
  10.157 +  Node s, t;
  10.158  
  10.159    std::istringstream input(test_lgf);
  10.160    DigraphReader<ListDigraph>(digraph, input).
  10.161 -    arcMap("cost", length).
  10.162 -    node("source", source).
  10.163 -    node("target", target).
  10.164 +    arcMap("length", length).
  10.165 +    node("source", s).
  10.166 +    node("target", t).
  10.167      run();
  10.168  
  10.169    // Find 2 paths
  10.170    {
  10.171 -    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
  10.172 -    check(suurballe.run(2) == 2, "Wrong number of paths");
  10.173 -    check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
  10.174 +    Suurballe<ListDigraph> suurballe(digraph, length);
  10.175 +    check(suurballe.run(s, t) == 2, "Wrong number of paths");
  10.176 +    check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
  10.177            "The flow is not feasible");
  10.178      check(suurballe.totalLength() == 510, "The flow is not optimal");
  10.179      check(checkOptimality(digraph, length, suurballe.flowMap(),
  10.180                            suurballe.potentialMap()),
  10.181            "Wrong potentials");
  10.182      for (int i = 0; i < suurballe.pathNum(); ++i)
  10.183 -      check(checkPath(digraph, suurballe.path(i), source, target),
  10.184 -            "Wrong path");
  10.185 +      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
  10.186    }
  10.187  
  10.188    // Find 3 paths
  10.189    {
  10.190 -    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
  10.191 -    check(suurballe.run(3) == 3, "Wrong number of paths");
  10.192 -    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
  10.193 +    Suurballe<ListDigraph> suurballe(digraph, length);
  10.194 +    check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
  10.195 +    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
  10.196            "The flow is not feasible");
  10.197      check(suurballe.totalLength() == 1040, "The flow is not optimal");
  10.198      check(checkOptimality(digraph, length, suurballe.flowMap(),
  10.199                            suurballe.potentialMap()),
  10.200            "Wrong potentials");
  10.201      for (int i = 0; i < suurballe.pathNum(); ++i)
  10.202 -      check(checkPath(digraph, suurballe.path(i), source, target),
  10.203 -            "Wrong path");
  10.204 +      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
  10.205    }
  10.206  
  10.207    // Find 5 paths (only 3 can be found)
  10.208    {
  10.209 -    Suurballe<ListDigraph> suurballe(digraph, length, source, target);
  10.210 -    check(suurballe.run(5) == 3, "Wrong number of paths");
  10.211 -    check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
  10.212 +    Suurballe<ListDigraph> suurballe(digraph, length);
  10.213 +    check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
  10.214 +    check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
  10.215            "The flow is not feasible");
  10.216      check(suurballe.totalLength() == 1040, "The flow is not optimal");
  10.217      check(checkOptimality(digraph, length, suurballe.flowMap(),
  10.218                            suurballe.potentialMap()),
  10.219            "Wrong potentials");
  10.220      for (int i = 0; i < suurballe.pathNum(); ++i)
  10.221 -      check(checkPath(digraph, suurballe.path(i), source, target),
  10.222 -            "Wrong path");
  10.223 +      check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
  10.224    }
  10.225  
  10.226    return 0;
    11.1 --- a/tools/lgf-gen.cc	Sun Apr 26 16:44:53 2009 +0200
    11.2 +++ b/tools/lgf-gen.cc	Sun Apr 26 16:36:23 2009 +0100
    11.3 @@ -480,8 +480,8 @@
    11.4        Node b=g.v(*ei);
    11.5        g.erase(*ei);
    11.6        ConstMap<Arc,int> cegy(1);
    11.7 -      Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy,a,b);
    11.8 -      int k=sur.run(2);
    11.9 +      Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);
   11.10 +      int k=sur.run(a,b,2);
   11.11        if(k<2 || sur.totalLength()>d)
   11.12          g.addEdge(a,b);
   11.13        else cnt++;
   11.14 @@ -511,9 +511,8 @@
   11.15        Edge ne;
   11.16        if(e==INVALID) {
   11.17          ConstMap<Arc,int> cegy(1);
   11.18 -        Suurballe<ListGraph,ConstMap<Arc,int> >
   11.19 -          sur(g,cegy,pi->a,pi->b);
   11.20 -        int k=sur.run(2);
   11.21 +        Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy);
   11.22 +        int k=sur.run(pi->a,pi->b,2);
   11.23          if(k<2 || sur.totalLength()>d)
   11.24            {
   11.25              ne=g.addEdge(pi->a,pi->b);