# HG changeset patch # User Alpar Juttner # Date 2009-04-26 17:36:23 # Node ID 58357e986a08f59fd3fe0db28468b69517950a31 # Parent 029a48052c67830ec6babba83b8eb3fde749d735 # Parent 1f631044c290ffb9b8dce21dfb3f09a295a53be3 Merge diff --git a/CMakeLists.txt b/CMakeLists.txt --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -14,6 +14,8 @@ INCLUDE(FindDoxygen) INCLUDE(FindGhostscript) FIND_PACKAGE(GLPK 4.33) +FIND_PACKAGE(CPLEX) +FIND_PACKAGE(COIN) ADD_DEFINITIONS(-DHAVE_CONFIG_H) @@ -26,12 +28,6 @@ # C4996: 'function': was declared deprecated ENDIF(MSVC) -IF(GLPK_FOUND) - SET(HAVE_LP TRUE) - SET(HAVE_MIP TRUE) - SET(HAVE_GLPK TRUE) -ENDIF(GLPK_FOUND) - INCLUDE(CheckTypeSize) CHECK_TYPE_SIZE("long long" LONG_LONG) diff --git a/cmake/FindCOIN.cmake b/cmake/FindCOIN.cmake new file mode 100644 --- /dev/null +++ b/cmake/FindCOIN.cmake @@ -0,0 +1,68 @@ +SET(COIN_ROOT_DIR "" CACHE PATH "COIN root directory") + +FIND_PATH(COIN_INCLUDE_DIR coin/CoinUtilsConfig.h + PATHS ${COIN_ROOT_DIR}/include) + +FIND_LIBRARY(COIN_CBC_LIBRARY libCbc + PATHS ${COIN_ROOT_DIR}/lib) +FIND_LIBRARY(COIN_CBC_SOLVER_LIBRARY libCbcSolver + PATHS ${COIN_ROOT_DIR}/lib) +FIND_LIBRARY(COIN_CGL_LIBRARY libCgl + PATHS ${COIN_ROOT_DIR}/lib) +FIND_LIBRARY(COIN_CLP_LIBRARY libClp + PATHS ${COIN_ROOT_DIR}/lib) +FIND_LIBRARY(COIN_COIN_UTILS_LIBRARY libCoinUtils + PATHS ${COIN_ROOT_DIR}/lib) +FIND_LIBRARY(COIN_OSI_LIBRARY libOsi + PATHS ${COIN_ROOT_DIR}/lib) +FIND_LIBRARY(COIN_OSI_CBC_LIBRARY libOsiCbc + PATHS ${COIN_ROOT_DIR}/lib) +FIND_LIBRARY(COIN_OSI_CLP_LIBRARY libOsiClp + PATHS ${COIN_ROOT_DIR}/lib) +FIND_LIBRARY(COIN_OSI_VOL_LIBRARY libOsiVol + PATHS ${COIN_ROOT_DIR}/lib) +FIND_LIBRARY(COIN_VOL_LIBRARY libVol + PATHS ${COIN_ROOT_DIR}/lib) + +INCLUDE(FindPackageHandleStandardArgs) +FIND_PACKAGE_HANDLE_STANDARD_ARGS(COIN DEFAULT_MSG + COIN_INCLUDE_DIR + 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 +) + +IF(COIN_FOUND) + SET(COIN_INCLUDE_DIRS ${COIN_INCLUDE_DIR}) + 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}") + SET(COIN_CLP_LIBRARIES "${COIN_CLP_LIBRARY};${COIN_COIN_UTILS_LIBRARY}") + SET(COIN_CBC_LIBRARIES ${COIN_LIBRARIES}) +ENDIF(COIN_FOUND) + +MARK_AS_ADVANCED( + COIN_INCLUDE_DIR + 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 +) + +IF(COIN_FOUND) + SET(HAVE_LP TRUE) + SET(HAVE_MIP TRUE) + SET(HAVE_CLP TRUE) + SET(HAVE_CBC TRUE) +ENDIF(COIN_FOUND) diff --git a/cmake/FindCPLEX.cmake b/cmake/FindCPLEX.cmake new file mode 100644 --- /dev/null +++ b/cmake/FindCPLEX.cmake @@ -0,0 +1,27 @@ +FIND_PATH(CPLEX_INCLUDE_DIR + ilcplex/cplex.h + PATHS "C:/ILOG/CPLEX91/include") + +FIND_LIBRARY(CPLEX_LIBRARY + NAMES cplex91 + PATHS "C:/ILOG/CPLEX91/lib/msvc7/stat_mda") + +INCLUDE(FindPackageHandleStandardArgs) +FIND_PACKAGE_HANDLE_STANDARD_ARGS(CPLEX DEFAULT_MSG CPLEX_LIBRARY CPLEX_INCLUDE_DIR) + +FIND_PATH(CPLEX_BIN_DIR + cplex91.dll + PATHS "C:/ILOG/CPLEX91/bin/x86_win32") + +IF(CPLEX_FOUND) + SET(CPLEX_INCLUDE_DIRS ${CPLEX_INCLUDE_DIR}) + SET(CPLEX_LIBRARIES ${CPLEX_LIBRARY}) +ENDIF(CPLEX_FOUND) + +MARK_AS_ADVANCED(CPLEX_LIBRARY CPLEX_INCLUDE_DIR CPLEX_BIN_DIR) + +IF(CPLEX_FOUND) + SET(HAVE_LP TRUE) + SET(HAVE_MIP TRUE) + SET(HAVE_CPLEX TRUE) +ENDIF(CPLEX_FOUND) diff --git a/cmake/FindGLPK.cmake b/cmake/FindGLPK.cmake --- a/cmake/FindGLPK.cmake +++ b/cmake/FindGLPK.cmake @@ -13,8 +13,15 @@ FIND_PACKAGE_HANDLE_STANDARD_ARGS(GLPK DEFAULT_MSG GLPK_LIBRARY GLPK_INCLUDE_DIR) IF(GLPK_FOUND) + SET(GLPK_INCLUDE_DIRS ${GLPK_INCLUDE_DIR}) SET(GLPK_LIBRARIES ${GLPK_LIBRARY}) SET(GLPK_BIN_DIR ${GLPK_ROOT_PATH}/bin) ENDIF(GLPK_FOUND) MARK_AS_ADVANCED(GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_BIN_DIR) + +IF(GLPK_FOUND) + SET(HAVE_LP TRUE) + SET(HAVE_MIP TRUE) + SET(HAVE_GLPK TRUE) +ENDIF(GLPK_FOUND) diff --git a/lemon/CMakeLists.txt b/lemon/CMakeLists.txt --- a/lemon/CMakeLists.txt +++ b/lemon/CMakeLists.txt @@ -20,7 +20,7 @@ IF(HAVE_GLPK) SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc) - INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR}) + INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS}) IF(WIN32) INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin) INSTALL(FILES ${GLPK_BIN_DIR}/libltdl3.dll DESTINATION bin) @@ -28,6 +28,21 @@ ENDIF(WIN32) ENDIF(HAVE_GLPK) +IF(HAVE_CPLEX) + SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc) + INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS}) +ENDIF(HAVE_CPLEX) + +IF(HAVE_CLP) + SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc) + INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS}) +ENDIF(HAVE_CLP) + +IF(HAVE_CBC) + SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc) + INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS}) +ENDIF(HAVE_CBC) + ADD_LIBRARY(lemon ${LEMON_SOURCES}) INSTALL( diff --git a/lemon/circulation.h b/lemon/circulation.h --- a/lemon/circulation.h +++ b/lemon/circulation.h @@ -21,6 +21,7 @@ #include #include +#include ///\ingroup max_flow ///\file @@ -119,15 +120,15 @@ at the nodes. The exact formulation of this problem is the following. - Let \f$G=(V,A)\f$ be a digraph, - \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and - upper bounds on the arcs, for which \f$0 \leq lower(uv) \leq upper(uv)\f$ + Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$ + \f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and + upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$ holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$ denotes the signed supply values of the nodes. If \f$sup(u)>0\f$, then \f$u\f$ is a supply node with \f$sup(u)\f$ supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with \f$-sup(u)\f$ demand. - A feasible circulation is an \f$f: A\rightarrow\mathbf{R}^+_0\f$ + A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$ solution of the following problem. \f[ \sum_{uv\in A} f(uv) - \sum_{vu\in A} f(vu) @@ -151,6 +152,10 @@ the direction of the arcs and taking the negative of the supply values (e.g. using \ref ReverseDigraph and \ref NegMap adaptors). + This algorithm either calculates a feasible circulation, or provides + a \ref barrier() "barrier", which prooves that a feasible soultion + cannot exist. + Note that this algorithm also provides a feasible solution for the \ref min_cost_flow "minimum cost flow problem". @@ -337,6 +342,13 @@ private: + bool checkBoundMaps() { + for (ArcIt e(_g);e!=INVALID;++e) { + if (_tol.less((*_up)[e], (*_lo)[e])) return false; + } + return true; + } + void createStructures() { _node_num = _el = countNodes(_g); @@ -380,7 +392,7 @@ /// Sets the upper bound (capacity) map. /// \return (*this) - Circulation& upperMap(const LowerMap& map) { + Circulation& upperMap(const UpperMap& map) { _up = ↦ return *this; } @@ -467,6 +479,9 @@ /// to the lower bound. void init() { + LEMON_DEBUG(checkBoundMaps(), + "Upper bounds must be greater or equal to the lower bounds"); + createStructures(); for(NodeIt n(_g);n!=INVALID;++n) { @@ -496,6 +511,9 @@ /// to construct the initial solution. void greedyInit() { + LEMON_DEBUG(checkBoundMaps(), + "Upper bounds must be greater or equal to the lower bounds"); + createStructures(); for(NodeIt n(_g);n!=INVALID;++n) { @@ -503,11 +521,11 @@ } for (ArcIt e(_g);e!=INVALID;++e) { - if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) { + if (!_tol.less(-(*_excess)[_g.target(e)], (*_up)[e])) { _flow->set(e, (*_up)[e]); (*_excess)[_g.target(e)] += (*_up)[e]; (*_excess)[_g.source(e)] -= (*_up)[e]; - } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) { + } else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) { _flow->set(e, (*_lo)[e]); (*_excess)[_g.target(e)] += (*_lo)[e]; (*_excess)[_g.source(e)] -= (*_lo)[e]; @@ -748,6 +766,9 @@ bool checkBarrier() const { Flow delta=0; + Flow inf_cap = std::numeric_limits::has_infinity ? + std::numeric_limits::infinity() : + std::numeric_limits::max(); for(NodeIt n(_g);n!=INVALID;++n) if(barrier(n)) delta-=(*_supply)[n]; @@ -755,7 +776,10 @@ { Node s=_g.source(e); Node t=_g.target(e); - if(barrier(s)&&!barrier(t)) delta+=(*_up)[e]; + if(barrier(s)&&!barrier(t)) { + if (_tol.less(inf_cap - (*_up)[e], delta)) return false; + delta+=(*_up)[e]; + } else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e]; } return _tol.negative(delta); diff --git a/lemon/config.h.cmake b/lemon/config.h.cmake --- a/lemon/config.h.cmake +++ b/lemon/config.h.cmake @@ -2,3 +2,6 @@ #cmakedefine HAVE_LP 1 #cmakedefine HAVE_MIP 1 #cmakedefine HAVE_GLPK 1 +#cmakedefine HAVE_CPLEX 1 +#cmakedefine HAVE_CLP 1 +#cmakedefine HAVE_CBC 1 diff --git a/lemon/suurballe.h b/lemon/suurballe.h --- a/lemon/suurballe.h +++ b/lemon/suurballe.h @@ -25,6 +25,7 @@ /// nodes having minimum total length. #include +#include #include #include #include @@ -42,22 +43,26 @@ /// finding arc-disjoint paths having minimum total length (cost) /// from a given source node to a given target node in a digraph. /// - /// In fact, this implementation is the specialization of the - /// \ref CapacityScaling "successive shortest path" algorithm. + /// Note that this problem is a special case of the \ref min_cost_flow + /// "minimum cost flow problem". This implementation is actually an + /// efficient specialized version of the \ref CapacityScaling + /// "Successive Shortest Path" algorithm directly for this problem. + /// Therefore this class provides query functions for flow values and + /// node potentials (the dual solution) just like the minimum cost flow + /// algorithms. /// /// \tparam GR The digraph type the algorithm runs on. - /// The default value is \c ListDigraph. - /// \tparam LEN The type of the length (cost) map. - /// The default value is Digraph::ArcMap. + /// \tparam LEN The type of the length map. + /// The default value is GR::ArcMap. /// /// \warning Length values should be \e non-negative \e integers. /// /// \note For finding node-disjoint paths this algorithm can be used - /// with \ref SplitNodes. + /// along with the \ref SplitNodes adaptor. #ifdef DOXYGEN template #else - template < typename GR = ListDigraph, + template < typename GR, typename LEN = typename GR::template ArcMap > #endif class Suurballe @@ -75,23 +80,28 @@ typedef LEN LengthMap; /// The type of the lengths. typedef typename LengthMap::Value Length; +#ifdef DOXYGEN + /// The type of the flow map. + typedef GR::ArcMap FlowMap; + /// The type of the potential map. + typedef GR::NodeMap PotentialMap; +#else /// The type of the flow map. typedef typename Digraph::template ArcMap FlowMap; /// The type of the potential map. typedef typename Digraph::template NodeMap PotentialMap; +#endif + /// The type of the path structures. - typedef SimplePath Path; + typedef SimplePath Path; private: - /// \brief Special implementation of the Dijkstra algorithm - /// for finding shortest paths in the residual network. - /// - /// \ref ResidualDijkstra is a special implementation of the - /// \ref Dijkstra algorithm for finding shortest paths in the - /// residual network of the digraph with respect to the reduced arc - /// lengths and modifying the node potentials according to the - /// distance of the nodes. + // ResidualDijkstra is a special implementation of the + // Dijkstra algorithm for finding shortest paths in the + // residual network with respect to the reduced arc lengths + // and modifying the node potentials according to the + // distance of the nodes. class ResidualDijkstra { typedef typename Digraph::template NodeMap HeapCrossRef; @@ -120,14 +130,14 @@ public: /// Constructor. - ResidualDijkstra( const Digraph &digraph, + ResidualDijkstra( const Digraph &graph, const FlowMap &flow, const LengthMap &length, PotentialMap &potential, PredMap &pred, Node s, Node t ) : - _graph(digraph), _flow(flow), _length(length), _potential(potential), - _dist(digraph), _pred(pred), _s(s), _t(t) {} + _graph(graph), _flow(flow), _length(length), _potential(potential), + _dist(graph), _pred(pred), _s(s), _t(t) {} /// \brief Run the algorithm. It returns \c true if a path is found /// from the source node to the target node. @@ -236,16 +246,16 @@ /// /// Constructor. /// - /// \param digraph The digraph the algorithm runs on. + /// \param graph The digraph the algorithm runs on. /// \param length The length (cost) values of the arcs. - /// \param s The source node. - /// \param t The target node. - Suurballe( const Digraph &digraph, - const LengthMap &length, - Node s, Node t ) : - _graph(digraph), _length(length), _flow(0), _local_flow(false), - _potential(0), _local_potential(false), _source(s), _target(t), - _pred(digraph) {} + Suurballe( const Digraph &graph, + const LengthMap &length ) : + _graph(graph), _length(length), _flow(0), _local_flow(false), + _potential(0), _local_potential(false), _pred(graph) + { + LEMON_ASSERT(std::numeric_limits::is_integer, + "The length type of Suurballe must be integer"); + } /// Destructor. ~Suurballe() { @@ -257,9 +267,12 @@ /// \brief Set the flow map. /// /// This function sets the flow map. + /// If it is not used before calling \ref run() or \ref init(), + /// an instance will be allocated automatically. The destructor + /// deallocates this automatically allocated map, of course. /// - /// The found flow contains only 0 and 1 values. It is the union of - /// the found arc-disjoint paths. + /// The found flow contains only 0 and 1 values, since it is the + /// union of the found arc-disjoint paths. /// /// \return (*this) Suurballe& flowMap(FlowMap &map) { @@ -274,9 +287,12 @@ /// \brief Set the potential map. /// /// This function sets the potential map. + /// If it is not used before calling \ref run() or \ref init(), + /// an instance will be allocated automatically. The destructor + /// deallocates this automatically allocated map, of course. /// - /// The potentials provide the dual solution of the underlying - /// minimum cost flow problem. + /// The node potentials provide the dual solution of the underlying + /// \ref min_cost_flow "minimum cost flow problem". /// /// \return (*this) Suurballe& potentialMap(PotentialMap &map) { @@ -301,22 +317,24 @@ /// /// This function runs the algorithm. /// + /// \param s The source node. + /// \param t The target node. /// \param k The number of paths to be found. /// /// \return \c k if there are at least \c k arc-disjoint paths from /// \c s to \c t in the digraph. Otherwise it returns the number of /// arc-disjoint paths found. /// - /// \note Apart from the return value, s.run(k) is just a - /// shortcut of the following code. + /// \note Apart from the return value, s.run(s, t, k) is + /// just a shortcut of the following code. /// \code - /// s.init(); - /// s.findFlow(k); + /// s.init(s); + /// s.findFlow(t, k); /// s.findPaths(); /// \endcode - int run(int k = 2) { - init(); - findFlow(k); + int run(const Node& s, const Node& t, int k = 2) { + init(s); + findFlow(t, k); findPaths(); return _path_num; } @@ -324,7 +342,11 @@ /// \brief Initialize the algorithm. /// /// This function initializes the algorithm. - void init() { + /// + /// \param s The source node. + void init(const Node& s) { + _source = s; + // Initialize maps if (!_flow) { _flow = new FlowMap(_graph); @@ -336,25 +358,28 @@ } for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0; for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0; - - _dijkstra = new ResidualDijkstra( _graph, *_flow, _length, - *_potential, _pred, - _source, _target ); } - /// \brief Execute the successive shortest path algorithm to find - /// an optimal flow. + /// \brief Execute the algorithm to find an optimal flow. /// /// This function executes the successive shortest path algorithm to - /// find a minimum cost flow, which is the union of \c k or less + /// find a minimum cost flow, which is the union of \c k (or less) /// arc-disjoint paths. /// + /// \param t The target node. + /// \param k The number of paths to be found. + /// /// \return \c k if there are at least \c k arc-disjoint paths from - /// \c s to \c t in the digraph. Otherwise it returns the number of - /// arc-disjoint paths found. + /// the source node to the given node \c t in the digraph. + /// Otherwise it returns the number of arc-disjoint paths found. /// /// \pre \ref init() must be called before using this function. - int findFlow(int k = 2) { + int findFlow(const Node& t, int k = 2) { + _target = t; + _dijkstra = + new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred, + _source, _target ); + // Find shortest paths _path_num = 0; while (_path_num < k) { @@ -380,13 +405,12 @@ /// \brief Compute the paths from the flow. /// - /// This function computes the paths from the flow. + /// This function computes the paths from the found minimum cost flow, + /// which is the union of some arc-disjoint paths. /// /// \pre \ref init() and \ref findFlow() must be called before using /// this function. void findPaths() { - // Create the residual flow map (the union of the paths not found - // so far) FlowMap res_flow(_graph); for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a]; @@ -413,10 +437,37 @@ /// @{ - /// \brief Return a const reference to the arc map storing the + /// \brief Return the total length of the found paths. + /// + /// This function returns the total length of the found paths, i.e. + /// the total cost of the found flow. + /// The complexity of the function is O(e). + /// + /// \pre \ref run() or \ref findFlow() must be called before using + /// this function. + Length totalLength() const { + Length c = 0; + for (ArcIt e(_graph); e != INVALID; ++e) + c += (*_flow)[e] * _length[e]; + return c; + } + + /// \brief Return the flow value on the given arc. + /// + /// This function returns the flow value on the given arc. + /// It is \c 1 if the arc is involved in one of the found arc-disjoint + /// paths, otherwise it is \c 0. + /// + /// \pre \ref run() or \ref findFlow() must be called before using + /// this function. + int flow(const Arc& arc) const { + return (*_flow)[arc]; + } + + /// \brief Return a const reference to an arc map storing the /// found flow. /// - /// This function returns a const reference to the arc map storing + /// This function returns a const reference to an arc map storing /// the flow that is the union of the found arc-disjoint paths. /// /// \pre \ref run() or \ref findFlow() must be called before using @@ -425,34 +476,11 @@ return *_flow; } - /// \brief Return a const reference to the node map storing the - /// found potentials (the dual solution). - /// - /// This function returns a const reference to the node map storing - /// the found potentials that provide the dual solution of the - /// underlying minimum cost flow problem. - /// - /// \pre \ref run() or \ref findFlow() must be called before using - /// this function. - const PotentialMap& potentialMap() const { - return *_potential; - } - - /// \brief Return the flow on the given arc. - /// - /// This function returns the flow on the given arc. - /// It is \c 1 if the arc is involved in one of the found paths, - /// otherwise it is \c 0. - /// - /// \pre \ref run() or \ref findFlow() must be called before using - /// this function. - int flow(const Arc& arc) const { - return (*_flow)[arc]; - } - /// \brief Return the potential of the given node. /// /// This function returns the potential of the given node. + /// The node potentials provide the dual solution of the + /// underlying \ref min_cost_flow "minimum cost flow problem". /// /// \pre \ref run() or \ref findFlow() must be called before using /// this function. @@ -460,18 +488,17 @@ return (*_potential)[node]; } - /// \brief Return the total length (cost) of the found paths (flow). + /// \brief Return a const reference to a node map storing the + /// found potentials (the dual solution). /// - /// This function returns the total length (cost) of the found paths - /// (flow). The complexity of the function is O(e). + /// This function returns a const reference to a node map storing + /// the found potentials that provide the dual solution of the + /// underlying \ref min_cost_flow "minimum cost flow problem". /// /// \pre \ref run() or \ref findFlow() must be called before using /// this function. - Length totalLength() const { - Length c = 0; - for (ArcIt e(_graph); e != INVALID; ++e) - c += (*_flow)[e] * _length[e]; - return c; + const PotentialMap& potentialMap() const { + return *_potential; } /// \brief Return the number of the found paths. @@ -488,7 +515,7 @@ /// /// This function returns a const reference to the specified path. /// - /// \param i The function returns the \c i-th path. + /// \param i The function returns the i-th path. /// \c i must be between \c 0 and %pathNum()-1. /// /// \pre \ref run() or \ref findPaths() must be called before using diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt --- a/test/CMakeLists.txt +++ b/test/CMakeLists.txt @@ -3,10 +3,6 @@ ${PROJECT_BINARY_DIR} ) -IF(HAVE_GLPK) - INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR}) -ENDIF(HAVE_GLPK) - LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon) SET(TESTS @@ -42,9 +38,17 @@ IF(HAVE_LP) ADD_EXECUTABLE(lp_test lp_test.cc) + SET(LP_TEST_LIBS lemon) IF(HAVE_GLPK) - TARGET_LINK_LIBRARIES(lp_test lemon ${GLPK_LIBRARIES}) + SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${GLPK_LIBRARIES}) ENDIF(HAVE_GLPK) + IF(HAVE_CPLEX) + SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES}) + ENDIF(HAVE_CPLEX) + IF(HAVE_CLP) + SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${COIN_CLP_LIBRARIES}) + ENDIF(HAVE_CLP) + TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS}) ADD_TEST(lp_test lp_test) IF(WIN32 AND HAVE_GLPK) @@ -56,13 +60,28 @@ COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH} ) ENDIF(WIN32 AND HAVE_GLPK) + IF(WIN32 AND HAVE_CPLEX) + GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION) + GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH) + ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD + COMMAND cmake -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH} + ) + ENDIF(WIN32 AND HAVE_CPLEX) ENDIF(HAVE_LP) IF(HAVE_MIP) ADD_EXECUTABLE(mip_test mip_test.cc) + SET(MIP_TEST_LIBS lemon) IF(HAVE_GLPK) - TARGET_LINK_LIBRARIES(mip_test lemon ${GLPK_LIBRARIES}) + SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${GLPK_LIBRARIES}) ENDIF(HAVE_GLPK) + IF(HAVE_CPLEX) + SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${CPLEX_LIBRARIES}) + ENDIF(HAVE_CPLEX) + IF(HAVE_CBC) + SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${COIN_CBC_LIBRARIES}) + ENDIF(HAVE_CBC) + TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS}) ADD_TEST(mip_test mip_test) IF(WIN32 AND HAVE_GLPK) @@ -74,6 +93,13 @@ COMMAND cmake -E copy ${GLPK_BIN_DIR}/zlib1.dll ${TARGET_PATH} ) ENDIF(WIN32 AND HAVE_GLPK) + IF(WIN32 AND HAVE_CPLEX) + GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION) + GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH) + ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD + COMMAND cmake -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH} + ) + ENDIF(WIN32 AND HAVE_CPLEX) ENDIF(HAVE_MIP) FOREACH(TEST_NAME ${TESTS}) diff --git a/test/suurballe_test.cc b/test/suurballe_test.cc --- a/test/suurballe_test.cc +++ b/test/suurballe_test.cc @@ -22,6 +22,7 @@ #include #include #include +#include #include "test_tools.h" @@ -29,47 +30,97 @@ char test_lgf[] = "@nodes\n" - "label supply1 supply2 supply3\n" - "1 0 20 27\n" - "2 0 -4 0\n" - "3 0 0 0\n" - "4 0 0 0\n" - "5 0 9 0\n" - "6 0 -6 0\n" - "7 0 0 0\n" - "8 0 0 0\n" - "9 0 3 0\n" - "10 0 -2 0\n" - "11 0 0 0\n" - "12 0 -20 -27\n" + "label\n" + "1\n" + "2\n" + "3\n" + "4\n" + "5\n" + "6\n" + "7\n" + "8\n" + "9\n" + "10\n" + "11\n" + "12\n" "@arcs\n" - " cost capacity lower1 lower2\n" - " 1 2 70 11 0 8\n" - " 1 3 150 3 0 1\n" - " 1 4 80 15 0 2\n" - " 2 8 80 12 0 0\n" - " 3 5 140 5 0 3\n" - " 4 6 60 10 0 1\n" - " 4 7 80 2 0 0\n" - " 4 8 110 3 0 0\n" - " 5 7 60 14 0 0\n" - " 5 11 120 12 0 0\n" - " 6 3 0 3 0 0\n" - " 6 9 140 4 0 0\n" - " 6 10 90 8 0 0\n" - " 7 1 30 5 0 0\n" - " 8 12 60 16 0 4\n" - " 9 12 50 6 0 0\n" - "10 12 70 13 0 5\n" - "10 2 100 7 0 0\n" - "10 7 60 10 0 0\n" - "11 10 20 14 0 6\n" - "12 11 30 10 0 0\n" + " length\n" + " 1 2 70\n" + " 1 3 150\n" + " 1 4 80\n" + " 2 8 80\n" + " 3 5 140\n" + " 4 6 60\n" + " 4 7 80\n" + " 4 8 110\n" + " 5 7 60\n" + " 5 11 120\n" + " 6 3 0\n" + " 6 9 140\n" + " 6 10 90\n" + " 7 1 30\n" + " 8 12 60\n" + " 9 12 50\n" + "10 12 70\n" + "10 2 100\n" + "10 7 60\n" + "11 10 20\n" + "12 11 30\n" "@attributes\n" "source 1\n" "target 12\n" "@end\n"; +// Check the interface of Suurballe +void checkSuurballeCompile() +{ + typedef int VType; + typedef concepts::Digraph Digraph; + + typedef Digraph::Node Node; + typedef Digraph::Arc Arc; + typedef concepts::ReadMap LengthMap; + + typedef Suurballe SuurballeType; + + Digraph g; + Node n; + Arc e; + LengthMap len; + SuurballeType::FlowMap flow(g); + SuurballeType::PotentialMap pi(g); + + SuurballeType suurb_test(g, len); + const SuurballeType& const_suurb_test = suurb_test; + + suurb_test + .flowMap(flow) + .potentialMap(pi); + + int k; + k = suurb_test.run(n, n); + k = suurb_test.run(n, n, k); + suurb_test.init(n); + k = suurb_test.findFlow(n); + k = suurb_test.findFlow(n, k); + suurb_test.findPaths(); + + int f; + VType c; + c = const_suurb_test.totalLength(); + f = const_suurb_test.flow(e); + const SuurballeType::FlowMap& fm = + const_suurb_test.flowMap(); + c = const_suurb_test.potential(n); + const SuurballeType::PotentialMap& pm = + const_suurb_test.potentialMap(); + k = const_suurb_test.pathNum(); + Path p = const_suurb_test.path(k); + + ignore_unused_variable_warning(fm); + ignore_unused_variable_warning(pm); +} + // Check the feasibility of the flow template bool checkFlow( const Digraph& gr, const FlowMap& flow, @@ -118,7 +169,6 @@ bool checkPath( const Digraph& gr, const Path& path, typename Digraph::Node s, typename Digraph::Node t) { - // Check the "Complementary Slackness" optimality condition TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); Node n = s; for (int i = 0; i < path.length(); ++i) { @@ -136,58 +186,55 @@ // Read the test digraph ListDigraph digraph; ListDigraph::ArcMap length(digraph); - Node source, target; + Node s, t; std::istringstream input(test_lgf); DigraphReader(digraph, input). - arcMap("cost", length). - node("source", source). - node("target", target). + arcMap("length", length). + node("source", s). + node("target", t). run(); // Find 2 paths { - Suurballe suurballe(digraph, length, source, target); - check(suurballe.run(2) == 2, "Wrong number of paths"); - check(checkFlow(digraph, suurballe.flowMap(), source, target, 2), + Suurballe suurballe(digraph, length); + check(suurballe.run(s, t) == 2, "Wrong number of paths"); + check(checkFlow(digraph, suurballe.flowMap(), s, t, 2), "The flow is not feasible"); check(suurballe.totalLength() == 510, "The flow is not optimal"); check(checkOptimality(digraph, length, suurballe.flowMap(), suurballe.potentialMap()), "Wrong potentials"); for (int i = 0; i < suurballe.pathNum(); ++i) - check(checkPath(digraph, suurballe.path(i), source, target), - "Wrong path"); + check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); } // Find 3 paths { - Suurballe suurballe(digraph, length, source, target); - check(suurballe.run(3) == 3, "Wrong number of paths"); - check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), + Suurballe suurballe(digraph, length); + check(suurballe.run(s, t, 3) == 3, "Wrong number of paths"); + check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), "The flow is not feasible"); check(suurballe.totalLength() == 1040, "The flow is not optimal"); check(checkOptimality(digraph, length, suurballe.flowMap(), suurballe.potentialMap()), "Wrong potentials"); for (int i = 0; i < suurballe.pathNum(); ++i) - check(checkPath(digraph, suurballe.path(i), source, target), - "Wrong path"); + check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); } // Find 5 paths (only 3 can be found) { - Suurballe suurballe(digraph, length, source, target); - check(suurballe.run(5) == 3, "Wrong number of paths"); - check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), + Suurballe suurballe(digraph, length); + check(suurballe.run(s, t, 5) == 3, "Wrong number of paths"); + check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), "The flow is not feasible"); check(suurballe.totalLength() == 1040, "The flow is not optimal"); check(checkOptimality(digraph, length, suurballe.flowMap(), suurballe.potentialMap()), "Wrong potentials"); for (int i = 0; i < suurballe.pathNum(); ++i) - check(checkPath(digraph, suurballe.path(i), source, target), - "Wrong path"); + check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); } return 0; diff --git a/tools/lgf-gen.cc b/tools/lgf-gen.cc --- a/tools/lgf-gen.cc +++ b/tools/lgf-gen.cc @@ -480,8 +480,8 @@ Node b=g.v(*ei); g.erase(*ei); ConstMap cegy(1); - Suurballe > sur(g,cegy,a,b); - int k=sur.run(2); + Suurballe > sur(g,cegy); + int k=sur.run(a,b,2); if(k<2 || sur.totalLength()>d) g.addEdge(a,b); else cnt++; @@ -511,9 +511,8 @@ Edge ne; if(e==INVALID) { ConstMap cegy(1); - Suurballe > - sur(g,cegy,pi->a,pi->b); - int k=sur.run(2); + Suurballe > sur(g,cegy); + int k=sur.run(pi->a,pi->b,2); if(k<2 || sur.totalLength()>d) { ne=g.addEdge(pi->a,pi->b);