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 = ↦
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);