Changes in / [625:029a48052c67:626:58357e986a08] in lemon-1.2
- Files:
-
- 2 added
- 9 edited
Legend:
- Unmodified
- Added
- Removed
-
CMakeLists.txt
r552 r621 15 15 INCLUDE(FindGhostscript) 16 16 FIND_PACKAGE(GLPK 4.33) 17 FIND_PACKAGE(CPLEX) 18 FIND_PACKAGE(COIN) 17 19 18 20 ADD_DEFINITIONS(-DHAVE_CONFIG_H) … … 26 28 # C4996: 'function': was declared deprecated 27 29 ENDIF(MSVC) 28 29 IF(GLPK_FOUND)30 SET(HAVE_LP TRUE)31 SET(HAVE_MIP TRUE)32 SET(HAVE_GLPK TRUE)33 ENDIF(GLPK_FOUND)34 30 35 31 INCLUDE(CheckTypeSize) -
cmake/FindGLPK.cmake
r473 r619 14 14 15 15 IF(GLPK_FOUND) 16 SET(GLPK_INCLUDE_DIRS ${GLPK_INCLUDE_DIR}) 16 17 SET(GLPK_LIBRARIES ${GLPK_LIBRARY}) 17 18 SET(GLPK_BIN_DIR ${GLPK_ROOT_PATH}/bin) … … 19 20 20 21 MARK_AS_ADVANCED(GLPK_LIBRARY GLPK_INCLUDE_DIR GLPK_BIN_DIR) 22 23 IF(GLPK_FOUND) 24 SET(HAVE_LP TRUE) 25 SET(HAVE_MIP TRUE) 26 SET(HAVE_GLPK TRUE) 27 ENDIF(GLPK_FOUND) -
lemon/CMakeLists.txt
r549 r621 21 21 IF(HAVE_GLPK) 22 22 SET(LEMON_SOURCES ${LEMON_SOURCES} glpk.cc) 23 INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR })23 INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIRS}) 24 24 IF(WIN32) 25 25 INSTALL(FILES ${GLPK_BIN_DIR}/glpk.dll DESTINATION bin) … … 28 28 ENDIF(WIN32) 29 29 ENDIF(HAVE_GLPK) 30 31 IF(HAVE_CPLEX) 32 SET(LEMON_SOURCES ${LEMON_SOURCES} cplex.cc) 33 INCLUDE_DIRECTORIES(${CPLEX_INCLUDE_DIRS}) 34 ENDIF(HAVE_CPLEX) 35 36 IF(HAVE_CLP) 37 SET(LEMON_SOURCES ${LEMON_SOURCES} clp.cc) 38 INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS}) 39 ENDIF(HAVE_CLP) 40 41 IF(HAVE_CBC) 42 SET(LEMON_SOURCES ${LEMON_SOURCES} cbc.cc) 43 INCLUDE_DIRECTORIES(${COIN_INCLUDE_DIRS}) 44 ENDIF(HAVE_CBC) 30 45 31 46 ADD_LIBRARY(lemon ${LEMON_SOURCES}) -
lemon/circulation.h
r611 r622 22 22 #include <lemon/tolerance.h> 23 23 #include <lemon/elevator.h> 24 #include <limits> 24 25 25 26 ///\ingroup max_flow … … 120 121 121 122 The exact formulation of this problem is the following. 122 Let \f$G=(V,A)\f$ be a digraph, 123 \f$ lower, upper: A\rightarrow\mathbf{R}^+_0\f$ denote the lower and124 upper bounds on the arcs, for which \f$ 0 \leqlower(uv) \leq upper(uv)\f$123 Let \f$G=(V,A)\f$ be a digraph, \f$lower: A\rightarrow\mathbf{R}\f$ 124 \f$upper: A\rightarrow\mathbf{R}\cup\{\infty\}\f$ denote the lower and 125 upper bounds on the arcs, for which \f$lower(uv) \leq upper(uv)\f$ 125 126 holds for all \f$uv\in A\f$, and \f$sup: V\rightarrow\mathbf{R}\f$ 126 127 denotes the signed supply values of the nodes. … … 128 129 supply, if \f$sup(u)<0\f$, then \f$u\f$ is a demand node with 129 130 \f$-sup(u)\f$ demand. 130 A feasible circulation is an \f$f: A\rightarrow\mathbf{R} ^+_0\f$131 A feasible circulation is an \f$f: A\rightarrow\mathbf{R}\f$ 131 132 solution of the following problem. 132 133 … … 151 152 the direction of the arcs and taking the negative of the supply values 152 153 (e.g. using \ref ReverseDigraph and \ref NegMap adaptors). 154 155 This algorithm either calculates a feasible circulation, or provides 156 a \ref barrier() "barrier", which prooves that a feasible soultion 157 cannot exist. 153 158 154 159 Note that this algorithm also provides a feasible solution for the … … 338 343 private: 339 344 345 bool checkBoundMaps() { 346 for (ArcIt e(_g);e!=INVALID;++e) { 347 if (_tol.less((*_up)[e], (*_lo)[e])) return false; 348 } 349 return true; 350 } 351 340 352 void createStructures() { 341 353 _node_num = _el = countNodes(_g); … … 381 393 /// Sets the upper bound (capacity) map. 382 394 /// \return <tt>(*this)</tt> 383 Circulation& upperMap(const LowerMap& map) {395 Circulation& upperMap(const UpperMap& map) { 384 396 _up = ↦ 385 397 return *this; … … 468 480 void init() 469 481 { 482 LEMON_DEBUG(checkBoundMaps(), 483 "Upper bounds must be greater or equal to the lower bounds"); 484 470 485 createStructures(); 471 486 … … 497 512 void greedyInit() 498 513 { 514 LEMON_DEBUG(checkBoundMaps(), 515 "Upper bounds must be greater or equal to the lower bounds"); 516 499 517 createStructures(); 500 518 … … 504 522 505 523 for (ArcIt e(_g);e!=INVALID;++e) { 506 if (!_tol. positive((*_excess)[_g.target(e)] +(*_up)[e])) {524 if (!_tol.less(-(*_excess)[_g.target(e)], (*_up)[e])) { 507 525 _flow->set(e, (*_up)[e]); 508 526 (*_excess)[_g.target(e)] += (*_up)[e]; 509 527 (*_excess)[_g.source(e)] -= (*_up)[e]; 510 } else if (_tol. positive((*_excess)[_g.target(e)] +(*_lo)[e])) {528 } else if (_tol.less(-(*_excess)[_g.target(e)], (*_lo)[e])) { 511 529 _flow->set(e, (*_lo)[e]); 512 530 (*_excess)[_g.target(e)] += (*_lo)[e]; … … 749 767 { 750 768 Flow delta=0; 769 Flow inf_cap = std::numeric_limits<Flow>::has_infinity ? 770 std::numeric_limits<Flow>::infinity() : 771 std::numeric_limits<Flow>::max(); 751 772 for(NodeIt n(_g);n!=INVALID;++n) 752 773 if(barrier(n)) … … 756 777 Node s=_g.source(e); 757 778 Node t=_g.target(e); 758 if(barrier(s)&&!barrier(t)) delta+=(*_up)[e]; 779 if(barrier(s)&&!barrier(t)) { 780 if (_tol.less(inf_cap - (*_up)[e], delta)) return false; 781 delta+=(*_up)[e]; 782 } 759 783 else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e]; 760 784 } -
lemon/config.h.cmake
r517 r621 3 3 #cmakedefine HAVE_MIP 1 4 4 #cmakedefine HAVE_GLPK 1 5 #cmakedefine HAVE_CPLEX 1 6 #cmakedefine HAVE_CLP 1 7 #cmakedefine HAVE_CBC 1 -
lemon/suurballe.h
r584 r623 26 26 27 27 #include <vector> 28 #include <limits> 28 29 #include <lemon/bin_heap.h> 29 30 #include <lemon/path.h> … … 43 44 /// from a given source node to a given target node in a digraph. 44 45 /// 45 /// In fact, this implementation is the specialization of the 46 /// \ref CapacityScaling "successive shortest path" algorithm. 46 /// Note that this problem is a special case of the \ref min_cost_flow 47 /// "minimum cost flow problem". This implementation is actually an 48 /// efficient specialized version of the \ref CapacityScaling 49 /// "Successive Shortest Path" algorithm directly for this problem. 50 /// Therefore this class provides query functions for flow values and 51 /// node potentials (the dual solution) just like the minimum cost flow 52 /// algorithms. 47 53 /// 48 54 /// \tparam GR The digraph type the algorithm runs on. 49 /// The default value is \c ListDigraph. 50 /// \tparam LEN The type of the length (cost) map. 51 /// The default value is <tt>Digraph::ArcMap<int></tt>. 55 /// \tparam LEN The type of the length map. 56 /// The default value is <tt>GR::ArcMap<int></tt>. 52 57 /// 53 58 /// \warning Length values should be \e non-negative \e integers. 54 59 /// 55 60 /// \note For finding node-disjoint paths this algorithm can be used 56 /// with \ref SplitNodes.61 /// along with the \ref SplitNodes adaptor. 57 62 #ifdef DOXYGEN 58 63 template <typename GR, typename LEN> 59 64 #else 60 template < typename GR = ListDigraph,65 template < typename GR, 61 66 typename LEN = typename GR::template ArcMap<int> > 62 67 #endif … … 76 81 /// The type of the lengths. 77 82 typedef typename LengthMap::Value Length; 83 #ifdef DOXYGEN 84 /// The type of the flow map. 85 typedef GR::ArcMap<int> FlowMap; 86 /// The type of the potential map. 87 typedef GR::NodeMap<Length> PotentialMap; 88 #else 78 89 /// The type of the flow map. 79 90 typedef typename Digraph::template ArcMap<int> FlowMap; 80 91 /// The type of the potential map. 81 92 typedef typename Digraph::template NodeMap<Length> PotentialMap; 93 #endif 94 82 95 /// The type of the path structures. 83 typedef SimplePath< Digraph> Path;96 typedef SimplePath<GR> Path; 84 97 85 98 private: 86 99 87 /// \brief Special implementation of the Dijkstra algorithm 88 /// for finding shortest paths in the residual network. 89 /// 90 /// \ref ResidualDijkstra is a special implementation of the 91 /// \ref Dijkstra algorithm for finding shortest paths in the 92 /// residual network of the digraph with respect to the reduced arc 93 /// lengths and modifying the node potentials according to the 94 /// distance of the nodes. 100 // ResidualDijkstra is a special implementation of the 101 // Dijkstra algorithm for finding shortest paths in the 102 // residual network with respect to the reduced arc lengths 103 // and modifying the node potentials according to the 104 // distance of the nodes. 95 105 class ResidualDijkstra 96 106 { … … 121 131 122 132 /// Constructor. 123 ResidualDijkstra( const Digraph & digraph,133 ResidualDijkstra( const Digraph &graph, 124 134 const FlowMap &flow, 125 135 const LengthMap &length, … … 127 137 PredMap &pred, 128 138 Node s, Node t ) : 129 _graph( digraph), _flow(flow), _length(length), _potential(potential),130 _dist( digraph), _pred(pred), _s(s), _t(t) {}139 _graph(graph), _flow(flow), _length(length), _potential(potential), 140 _dist(graph), _pred(pred), _s(s), _t(t) {} 131 141 132 142 /// \brief Run the algorithm. It returns \c true if a path is found … … 237 247 /// Constructor. 238 248 /// 239 /// \param digraph The digraph the algorithm runs on.249 /// \param graph The digraph the algorithm runs on. 240 250 /// \param length The length (cost) values of the arcs. 241 /// \param s The source node.242 /// \param t The target node.243 Suurballe( const Digraph &digraph,244 const LengthMap &length,245 Node s, Node t ) :246 _graph(digraph), _length(length), _flow(0), _local_flow(false),247 _potential(0), _local_potential(false), _source(s), _target(t),248 _pred(digraph) {}251 Suurballe( const Digraph &graph, 252 const LengthMap &length ) : 253 _graph(graph), _length(length), _flow(0), _local_flow(false), 254 _potential(0), _local_potential(false), _pred(graph) 255 { 256 LEMON_ASSERT(std::numeric_limits<Length>::is_integer, 257 "The length type of Suurballe must be integer"); 258 } 249 259 250 260 /// Destructor. … … 258 268 /// 259 269 /// This function sets the flow map. 260 /// 261 /// The found flow contains only 0 and 1 values. It is the union of 262 /// the found arc-disjoint paths. 270 /// If it is not used before calling \ref run() or \ref init(), 271 /// an instance will be allocated automatically. The destructor 272 /// deallocates this automatically allocated map, of course. 273 /// 274 /// The found flow contains only 0 and 1 values, since it is the 275 /// union of the found arc-disjoint paths. 263 276 /// 264 277 /// \return <tt>(*this)</tt> … … 275 288 /// 276 289 /// This function sets the potential map. 277 /// 278 /// The potentials provide the dual solution of the underlying 279 /// minimum cost flow problem. 290 /// If it is not used before calling \ref run() or \ref init(), 291 /// an instance will be allocated automatically. The destructor 292 /// deallocates this automatically allocated map, of course. 293 /// 294 /// The node potentials provide the dual solution of the underlying 295 /// \ref min_cost_flow "minimum cost flow problem". 280 296 /// 281 297 /// \return <tt>(*this)</tt> … … 302 318 /// This function runs the algorithm. 303 319 /// 320 /// \param s The source node. 321 /// \param t The target node. 304 322 /// \param k The number of paths to be found. 305 323 /// … … 308 326 /// arc-disjoint paths found. 309 327 /// 310 /// \note Apart from the return value, <tt>s.run( k)</tt> is just a311 /// shortcut of the following code.328 /// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is 329 /// just a shortcut of the following code. 312 330 /// \code 313 /// s.init( );314 /// s.findFlow( k);331 /// s.init(s); 332 /// s.findFlow(t, k); 315 333 /// s.findPaths(); 316 334 /// \endcode 317 int run( int k = 2) {318 init( );319 findFlow( k);335 int run(const Node& s, const Node& t, int k = 2) { 336 init(s); 337 findFlow(t, k); 320 338 findPaths(); 321 339 return _path_num; … … 325 343 /// 326 344 /// This function initializes the algorithm. 327 void init() { 345 /// 346 /// \param s The source node. 347 void init(const Node& s) { 348 _source = s; 349 328 350 // Initialize maps 329 351 if (!_flow) { … … 337 359 for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0; 338 360 for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0; 339 340 _dijkstra = new ResidualDijkstra( _graph, *_flow, _length, 341 *_potential, _pred, 342 _source, _target ); 343 } 344 345 /// \brief Execute the successive shortest path algorithm to find 346 /// an optimal flow. 361 } 362 363 /// \brief Execute the algorithm to find an optimal flow. 347 364 /// 348 365 /// This function executes the successive shortest path algorithm to 349 /// find a minimum cost flow, which is the union of \c k or less366 /// find a minimum cost flow, which is the union of \c k (or less) 350 367 /// arc-disjoint paths. 351 368 /// 369 /// \param t The target node. 370 /// \param k The number of paths to be found. 371 /// 352 372 /// \return \c k if there are at least \c k arc-disjoint paths from 353 /// \c s to \c t in the digraph. Otherwise it returns the number of354 /// arc-disjoint paths found.373 /// the source node to the given node \c t in the digraph. 374 /// Otherwise it returns the number of arc-disjoint paths found. 355 375 /// 356 376 /// \pre \ref init() must be called before using this function. 357 int findFlow(int k = 2) { 377 int findFlow(const Node& t, int k = 2) { 378 _target = t; 379 _dijkstra = 380 new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred, 381 _source, _target ); 382 358 383 // Find shortest paths 359 384 _path_num = 0; … … 381 406 /// \brief Compute the paths from the flow. 382 407 /// 383 /// This function computes the paths from the flow. 408 /// This function computes the paths from the found minimum cost flow, 409 /// which is the union of some arc-disjoint paths. 384 410 /// 385 411 /// \pre \ref init() and \ref findFlow() must be called before using 386 412 /// this function. 387 413 void findPaths() { 388 // Create the residual flow map (the union of the paths not found389 // so far)390 414 FlowMap res_flow(_graph); 391 415 for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a]; … … 414 438 /// @{ 415 439 416 /// \brief Return a const reference to the arc map storing the 417 /// found flow. 418 /// 419 /// This function returns a const reference to the arc map storing 420 /// the flow that is the union of the found arc-disjoint paths. 421 /// 422 /// \pre \ref run() or \ref findFlow() must be called before using 423 /// this function. 424 const FlowMap& flowMap() const { 425 return *_flow; 426 } 427 428 /// \brief Return a const reference to the node map storing the 429 /// found potentials (the dual solution). 430 /// 431 /// This function returns a const reference to the node map storing 432 /// the found potentials that provide the dual solution of the 433 /// underlying minimum cost flow problem. 434 /// 435 /// \pre \ref run() or \ref findFlow() must be called before using 436 /// this function. 437 const PotentialMap& potentialMap() const { 438 return *_potential; 439 } 440 441 /// \brief Return the flow on the given arc. 442 /// 443 /// This function returns the flow on the given arc. 444 /// It is \c 1 if the arc is involved in one of the found paths, 445 /// otherwise it is \c 0. 446 /// 447 /// \pre \ref run() or \ref findFlow() must be called before using 448 /// this function. 449 int flow(const Arc& arc) const { 450 return (*_flow)[arc]; 451 } 452 453 /// \brief Return the potential of the given node. 454 /// 455 /// This function returns the potential of the given node. 456 /// 457 /// \pre \ref run() or \ref findFlow() must be called before using 458 /// this function. 459 Length potential(const Node& node) const { 460 return (*_potential)[node]; 461 } 462 463 /// \brief Return the total length (cost) of the found paths (flow). 464 /// 465 /// This function returns the total length (cost) of the found paths 466 /// (flow). The complexity of the function is O(e). 440 /// \brief Return the total length of the found paths. 441 /// 442 /// This function returns the total length of the found paths, i.e. 443 /// the total cost of the found flow. 444 /// The complexity of the function is O(e). 467 445 /// 468 446 /// \pre \ref run() or \ref findFlow() must be called before using … … 475 453 } 476 454 455 /// \brief Return the flow value on the given arc. 456 /// 457 /// This function returns the flow value on the given arc. 458 /// It is \c 1 if the arc is involved in one of the found arc-disjoint 459 /// paths, otherwise it is \c 0. 460 /// 461 /// \pre \ref run() or \ref findFlow() must be called before using 462 /// this function. 463 int flow(const Arc& arc) const { 464 return (*_flow)[arc]; 465 } 466 467 /// \brief Return a const reference to an arc map storing the 468 /// found flow. 469 /// 470 /// This function returns a const reference to an arc map storing 471 /// the flow that is the union of the found arc-disjoint paths. 472 /// 473 /// \pre \ref run() or \ref findFlow() must be called before using 474 /// this function. 475 const FlowMap& flowMap() const { 476 return *_flow; 477 } 478 479 /// \brief Return the potential of the given node. 480 /// 481 /// This function returns the potential of the given node. 482 /// The node potentials provide the dual solution of the 483 /// underlying \ref min_cost_flow "minimum cost flow problem". 484 /// 485 /// \pre \ref run() or \ref findFlow() must be called before using 486 /// this function. 487 Length potential(const Node& node) const { 488 return (*_potential)[node]; 489 } 490 491 /// \brief Return a const reference to a node map storing the 492 /// found potentials (the dual solution). 493 /// 494 /// This function returns a const reference to a node map storing 495 /// the found potentials that provide the dual solution of the 496 /// underlying \ref min_cost_flow "minimum cost flow problem". 497 /// 498 /// \pre \ref run() or \ref findFlow() must be called before using 499 /// this function. 500 const PotentialMap& potentialMap() const { 501 return *_potential; 502 } 503 477 504 /// \brief Return the number of the found paths. 478 505 /// … … 489 516 /// This function returns a const reference to the specified path. 490 517 /// 491 /// \param i The function returns the \c i-th path.518 /// \param i The function returns the <tt>i</tt>-th path. 492 519 /// \c i must be between \c 0 and <tt>%pathNum()-1</tt>. 493 520 /// -
test/CMakeLists.txt
r611 r621 3 3 ${PROJECT_BINARY_DIR} 4 4 ) 5 6 IF(HAVE_GLPK)7 INCLUDE_DIRECTORIES(${GLPK_INCLUDE_DIR})8 ENDIF(HAVE_GLPK)9 5 10 6 LINK_DIRECTORIES(${PROJECT_BINARY_DIR}/lemon) … … 43 39 IF(HAVE_LP) 44 40 ADD_EXECUTABLE(lp_test lp_test.cc) 41 SET(LP_TEST_LIBS lemon) 45 42 IF(HAVE_GLPK) 46 TARGET_LINK_LIBRARIES(lp_test lemon${GLPK_LIBRARIES})43 SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${GLPK_LIBRARIES}) 47 44 ENDIF(HAVE_GLPK) 45 IF(HAVE_CPLEX) 46 SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${CPLEX_LIBRARIES}) 47 ENDIF(HAVE_CPLEX) 48 IF(HAVE_CLP) 49 SET(LP_TEST_LIBS ${LP_TEST_LIBS} ${COIN_CLP_LIBRARIES}) 50 ENDIF(HAVE_CLP) 51 TARGET_LINK_LIBRARIES(lp_test ${LP_TEST_LIBS}) 48 52 ADD_TEST(lp_test lp_test) 49 53 … … 57 61 ) 58 62 ENDIF(WIN32 AND HAVE_GLPK) 63 IF(WIN32 AND HAVE_CPLEX) 64 GET_TARGET_PROPERTY(TARGET_LOC lp_test LOCATION) 65 GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH) 66 ADD_CUSTOM_COMMAND(TARGET lp_test POST_BUILD 67 COMMAND cmake -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH} 68 ) 69 ENDIF(WIN32 AND HAVE_CPLEX) 59 70 ENDIF(HAVE_LP) 60 71 61 72 IF(HAVE_MIP) 62 73 ADD_EXECUTABLE(mip_test mip_test.cc) 74 SET(MIP_TEST_LIBS lemon) 63 75 IF(HAVE_GLPK) 64 TARGET_LINK_LIBRARIES(mip_test lemon${GLPK_LIBRARIES})76 SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${GLPK_LIBRARIES}) 65 77 ENDIF(HAVE_GLPK) 78 IF(HAVE_CPLEX) 79 SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${CPLEX_LIBRARIES}) 80 ENDIF(HAVE_CPLEX) 81 IF(HAVE_CBC) 82 SET(MIP_TEST_LIBS ${MIP_TEST_LIBS} ${COIN_CBC_LIBRARIES}) 83 ENDIF(HAVE_CBC) 84 TARGET_LINK_LIBRARIES(mip_test ${MIP_TEST_LIBS}) 66 85 ADD_TEST(mip_test mip_test) 67 86 … … 75 94 ) 76 95 ENDIF(WIN32 AND HAVE_GLPK) 96 IF(WIN32 AND HAVE_CPLEX) 97 GET_TARGET_PROPERTY(TARGET_LOC mip_test LOCATION) 98 GET_FILENAME_COMPONENT(TARGET_PATH ${TARGET_LOC} PATH) 99 ADD_CUSTOM_COMMAND(TARGET mip_test POST_BUILD 100 COMMAND cmake -E copy ${CPLEX_BIN_DIR}/cplex91.dll ${TARGET_PATH} 101 ) 102 ENDIF(WIN32 AND HAVE_CPLEX) 77 103 ENDIF(HAVE_MIP) 78 104 -
test/suurballe_test.cc
r440 r623 23 23 #include <lemon/path.h> 24 24 #include <lemon/suurballe.h> 25 #include <lemon/concepts/digraph.h> 25 26 26 27 #include "test_tools.h" … … 30 31 char test_lgf[] = 31 32 "@nodes\n" 32 "label supply1 supply2 supply3\n"33 "1 0 20 27\n"34 "2 0 -4 0\n"35 "3 0 0 0\n"36 "4 0 0 0\n"37 "5 0 9 0\n"38 "6 0 -6 0\n"39 "7 0 0 0\n"40 "8 0 0 0\n"41 "9 0 3 0\n"42 "10 0 -2 0\n"43 "11 0 0 0\n"44 "12 0 -20 -27\n"33 "label\n" 34 "1\n" 35 "2\n" 36 "3\n" 37 "4\n" 38 "5\n" 39 "6\n" 40 "7\n" 41 "8\n" 42 "9\n" 43 "10\n" 44 "11\n" 45 "12\n" 45 46 "@arcs\n" 46 " cost capacity lower1 lower2\n"47 " 1 2 70 11 0 8\n"48 " 1 3 150 3 0 1\n"49 " 1 4 80 15 0 2\n"50 " 2 8 80 12 0 0\n"51 " 3 5 140 5 0 3\n"52 " 4 6 60 10 0 1\n"53 " 4 7 80 2 0 0\n"54 " 4 8 110 3 0 0\n"55 " 5 7 60 14 0 0\n"56 " 5 11 120 12 0 0\n"57 " 6 3 0 3 0 0\n"58 " 6 9 140 4 0 0\n"59 " 6 10 90 8 0 0\n"60 " 7 1 30 5 0 0\n"61 " 8 12 60 16 0 4\n"62 " 9 12 50 6 0 0\n"63 "10 12 70 13 0 5\n"64 "10 2 100 7 0 0\n"65 "10 7 60 10 0 0\n"66 "11 10 20 14 0 6\n"67 "12 11 30 10 0 0\n"47 " length\n" 48 " 1 2 70\n" 49 " 1 3 150\n" 50 " 1 4 80\n" 51 " 2 8 80\n" 52 " 3 5 140\n" 53 " 4 6 60\n" 54 " 4 7 80\n" 55 " 4 8 110\n" 56 " 5 7 60\n" 57 " 5 11 120\n" 58 " 6 3 0\n" 59 " 6 9 140\n" 60 " 6 10 90\n" 61 " 7 1 30\n" 62 " 8 12 60\n" 63 " 9 12 50\n" 64 "10 12 70\n" 65 "10 2 100\n" 66 "10 7 60\n" 67 "11 10 20\n" 68 "12 11 30\n" 68 69 "@attributes\n" 69 70 "source 1\n" 70 71 "target 12\n" 71 72 "@end\n"; 73 74 // Check the interface of Suurballe 75 void checkSuurballeCompile() 76 { 77 typedef int VType; 78 typedef concepts::Digraph Digraph; 79 80 typedef Digraph::Node Node; 81 typedef Digraph::Arc Arc; 82 typedef concepts::ReadMap<Arc, VType> LengthMap; 83 84 typedef Suurballe<Digraph, LengthMap> SuurballeType; 85 86 Digraph g; 87 Node n; 88 Arc e; 89 LengthMap len; 90 SuurballeType::FlowMap flow(g); 91 SuurballeType::PotentialMap pi(g); 92 93 SuurballeType suurb_test(g, len); 94 const SuurballeType& const_suurb_test = suurb_test; 95 96 suurb_test 97 .flowMap(flow) 98 .potentialMap(pi); 99 100 int k; 101 k = suurb_test.run(n, n); 102 k = suurb_test.run(n, n, k); 103 suurb_test.init(n); 104 k = suurb_test.findFlow(n); 105 k = suurb_test.findFlow(n, k); 106 suurb_test.findPaths(); 107 108 int f; 109 VType c; 110 c = const_suurb_test.totalLength(); 111 f = const_suurb_test.flow(e); 112 const SuurballeType::FlowMap& fm = 113 const_suurb_test.flowMap(); 114 c = const_suurb_test.potential(n); 115 const SuurballeType::PotentialMap& pm = 116 const_suurb_test.potentialMap(); 117 k = const_suurb_test.pathNum(); 118 Path<Digraph> p = const_suurb_test.path(k); 119 120 ignore_unused_variable_warning(fm); 121 ignore_unused_variable_warning(pm); 122 } 72 123 73 124 // Check the feasibility of the flow … … 119 170 typename Digraph::Node s, typename Digraph::Node t) 120 171 { 121 // Check the "Complementary Slackness" optimality condition122 172 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 123 173 Node n = s; … … 137 187 ListDigraph digraph; 138 188 ListDigraph::ArcMap<int> length(digraph); 139 Node s ource, target;189 Node s, t; 140 190 141 191 std::istringstream input(test_lgf); 142 192 DigraphReader<ListDigraph>(digraph, input). 143 arcMap(" cost", length).144 node("source", s ource).145 node("target", t arget).193 arcMap("length", length). 194 node("source", s). 195 node("target", t). 146 196 run(); 147 197 148 198 // Find 2 paths 149 199 { 150 Suurballe<ListDigraph> suurballe(digraph, length , source, target);151 check(suurballe.run( 2) == 2, "Wrong number of paths");152 check(checkFlow(digraph, suurballe.flowMap(), s ource, target, 2),200 Suurballe<ListDigraph> suurballe(digraph, length); 201 check(suurballe.run(s, t) == 2, "Wrong number of paths"); 202 check(checkFlow(digraph, suurballe.flowMap(), s, t, 2), 153 203 "The flow is not feasible"); 154 204 check(suurballe.totalLength() == 510, "The flow is not optimal"); … … 157 207 "Wrong potentials"); 158 208 for (int i = 0; i < suurballe.pathNum(); ++i) 159 check(checkPath(digraph, suurballe.path(i), source, target), 160 "Wrong path"); 209 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); 161 210 } 162 211 163 212 // Find 3 paths 164 213 { 165 Suurballe<ListDigraph> suurballe(digraph, length , source, target);166 check(suurballe.run( 3) == 3, "Wrong number of paths");167 check(checkFlow(digraph, suurballe.flowMap(), s ource, target, 3),214 Suurballe<ListDigraph> suurballe(digraph, length); 215 check(suurballe.run(s, t, 3) == 3, "Wrong number of paths"); 216 check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), 168 217 "The flow is not feasible"); 169 218 check(suurballe.totalLength() == 1040, "The flow is not optimal"); … … 172 221 "Wrong potentials"); 173 222 for (int i = 0; i < suurballe.pathNum(); ++i) 174 check(checkPath(digraph, suurballe.path(i), source, target), 175 "Wrong path"); 223 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); 176 224 } 177 225 178 226 // Find 5 paths (only 3 can be found) 179 227 { 180 Suurballe<ListDigraph> suurballe(digraph, length , source, target);181 check(suurballe.run( 5) == 3, "Wrong number of paths");182 check(checkFlow(digraph, suurballe.flowMap(), s ource, target, 3),228 Suurballe<ListDigraph> suurballe(digraph, length); 229 check(suurballe.run(s, t, 5) == 3, "Wrong number of paths"); 230 check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), 183 231 "The flow is not feasible"); 184 232 check(suurballe.totalLength() == 1040, "The flow is not optimal"); … … 187 235 "Wrong potentials"); 188 236 for (int i = 0; i < suurballe.pathNum(); ++i) 189 check(checkPath(digraph, suurballe.path(i), source, target), 190 "Wrong path"); 237 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); 191 238 } 192 239 -
tools/lgf-gen.cc
r616 r623 481 481 g.erase(*ei); 482 482 ConstMap<Arc,int> cegy(1); 483 Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy ,a,b);484 int k=sur.run( 2);483 Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy); 484 int k=sur.run(a,b,2); 485 485 if(k<2 || sur.totalLength()>d) 486 486 g.addEdge(a,b); … … 512 512 if(e==INVALID) { 513 513 ConstMap<Arc,int> cegy(1); 514 Suurballe<ListGraph,ConstMap<Arc,int> > 515 sur(g,cegy,pi->a,pi->b); 516 int k=sur.run(2); 514 Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy); 515 int k=sur.run(pi->a,pi->b,2); 517 516 if(k<2 || sur.totalLength()>d) 518 517 {
Note: See TracChangeset
for help on using the changeset viewer.