Changes in / [922:1b8db382910c:921:e05b2b48515a] in lemon
- Files:
-
- 1 deleted
- 28 edited
Legend:
- Unmodified
- Added
- Removed
-
INSTALL
r890 r615 174 174 175 175 Disable COIN-OR support. 176 177 178 Makefile Variables179 ==================180 181 Some Makefile variables are reserved by the GNU Coding Standards for182 the use of the "user" - the person building the package. For instance,183 CXX and CXXFLAGS are such variables, and have the same meaning as184 explained in the previous section. These variables can be set on the185 command line when invoking `make' like this:186 `make [VARIABLE=VALUE]...'187 188 WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us189 to hold several compiler flags related to warnings. Its default value190 can be overridden when invoking `make'. For example to disable all191 warning flags use `make WARNINGCXXFLAGS='.192 193 In order to turn off a single flag from the default set of warning194 flags, you can use the CXXFLAGS variable, since this is passed after195 WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is196 used by default when g++ is detected) you can use197 `make CXXFLAGS="-g -O2 -Wno-old-style-cast"'. -
demo/arg_parser_demo.cc
r915 r463 66 66 .other("..."); 67 67 68 // Throw an exception when problems occurs. The default behavior is to69 // exit(1) on these cases, but this makes Valgrind falsely warn70 // about memory leaks.71 ap.throwOnProblems();72 73 68 // Perform the parsing process 74 69 // (in case of any error it terminates the program) 75 // The try {} construct is necessary only if the ap.trowOnProblems() 76 // setting is in use. 77 try { 78 ap.parse(); 79 } catch (ArgParserException &) { return 1; } 70 ap.parse(); 80 71 81 72 // Check each option if it has been given and print its value -
doc/CMakeLists.txt
r895 r791 27 27 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps 28 28 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps 29 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps30 29 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps 31 30 COMMAND ${CMAKE_COMMAND} -E remove_directory html -
doc/Makefile.am
r895 r791 29 29 edge_biconnected_components.eps \ 30 30 node_biconnected_components.eps \ 31 planar.eps \32 31 strongly_connected_components.eps 33 32 -
lemon/arg_parser.cc
r915 r463 21 21 namespace lemon { 22 22 23 void ArgParser::_terminate(ArgParserException::Reason reason) const24 {25 if(_exit_on_problems)26 exit(1);27 else throw(ArgParserException(reason));28 }29 30 31 23 void ArgParser::_showHelp(void *p) 32 24 { 33 25 (static_cast<ArgParser*>(p))->showHelp(); 34 (static_cast<ArgParser*>(p))->_terminate(ArgParserException::HELP);26 exit(1); 35 27 } 36 28 37 29 ArgParser::ArgParser(int argc, const char * const *argv) 38 :_argc(argc), _argv(argv), _command_name(argv[0]), 39 _exit_on_problems(true) { 30 :_argc(argc), _argv(argv), _command_name(argv[0]) { 40 31 funcOption("-help","Print a short help message",_showHelp,this); 41 32 synonym("help","-help"); … … 352 343 i!=_others_help.end();++i) showHelp(i); 353 344 for(Opts::const_iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i); 354 _terminate(ArgParserException::HELP);345 exit(1); 355 346 } 356 347 … … 361 352 std::cerr << "\nType '" << _command_name << 362 353 " --help' to obtain a short summary on the usage.\n\n"; 363 _terminate(ArgParserException::UNKNOWN_OPT);354 exit(1); 364 355 } 365 356 … … 424 415 std::cerr << "\nType '" << _command_name << 425 416 " --help' to obtain a short summary on the usage.\n\n"; 426 _terminate(ArgParserException::INVALID_OPT);417 exit(1); 427 418 } 428 419 } -
lemon/arg_parser.h
r915 r463 34 34 35 35 namespace lemon { 36 37 ///Exception used by ArgParser38 class ArgParserException : public Exception {39 public:40 enum Reason {41 HELP, /// <tt>--help</tt> option was given42 UNKNOWN_OPT, /// Unknown option was given43 INVALID_OPT /// Invalid combination of options44 };45 46 private:47 Reason _reason;48 49 public:50 ///Constructor51 ArgParserException(Reason r) throw() : _reason(r) {}52 ///Virtual destructor53 virtual ~ArgParserException() throw() {}54 ///A short description of the exception55 virtual const char* what() const throw() {56 switch(_reason)57 {58 case HELP:59 return "lemon::ArgParseException: ask for help";60 break;61 case UNKNOWN_OPT:62 return "lemon::ArgParseException: unknown option";63 break;64 case INVALID_OPT:65 return "lemon::ArgParseException: invalid combination of options";66 break;67 }68 return "";69 }70 ///Return the reason for the failure71 Reason reason() const {return _reason; }72 };73 74 36 75 37 ///Command line arguments parser … … 142 104 std::string _command_name; 143 105 144 106 145 107 private: 146 108 //Bind a function to an option. … … 154 116 const std::string &help, 155 117 void (*func)(void *),void *data); 156 157 bool _exit_on_problems;158 159 void _terminate(ArgParserException::Reason reason) const;160 118 161 119 public: … … 423 381 const std::vector<std::string> &files() const { return _file_args; } 424 382 425 ///Throw instead of exit in case of problems426 void throwOnProblems()427 {428 _exit_on_problems=false;429 }430 383 }; 431 384 } -
lemon/bellman_ford.h
r917 r870 29 29 #include <lemon/error.h> 30 30 #include <lemon/maps.h> 31 #include <lemon/tolerance.h>32 31 #include <lemon/path.h> 33 32 … … 36 35 namespace lemon { 37 36 38 /// \brief Default operation traits for the BellmanFord algorithm class.37 /// \brief Default OperationTraits for the BellmanFord algorithm class. 39 38 /// 40 39 /// This operation traits class defines all computational operations … … 43 42 /// If the numeric type does not have infinity value, then the maximum 44 43 /// value is used as extremal infinity value. 45 ///46 /// \see BellmanFordToleranceOperationTraits47 44 template < 48 45 typename V, 49 46 bool has_inf = std::numeric_limits<V>::has_infinity> 50 47 struct BellmanFordDefaultOperationTraits { 51 /// \ brief Value type for the algorithm.48 /// \e 52 49 typedef V Value; 53 50 /// \brief Gives back the zero value of the type. … … 88 85 }; 89 86 90 /// \brief Operation traits for the BellmanFord algorithm class91 /// using tolerance.92 ///93 /// This operation traits class defines all computational operations94 /// and constants that are used in the Bellman-Ford algorithm.95 /// The only difference between this implementation and96 /// \ref BellmanFordDefaultOperationTraits is that this class uses97 /// the \ref Tolerance "tolerance technique" in its \ref less()98 /// function.99 ///100 /// \tparam V The value type.101 /// \tparam eps The epsilon value for the \ref less() function.102 /// By default, it is the epsilon value used by \ref Tolerance103 /// "Tolerance<V>".104 ///105 /// \see BellmanFordDefaultOperationTraits106 #ifdef DOXYGEN107 template <typename V, V eps>108 #else109 template <110 typename V,111 V eps = Tolerance<V>::def_epsilon>112 #endif113 struct BellmanFordToleranceOperationTraits {114 /// \brief Value type for the algorithm.115 typedef V Value;116 /// \brief Gives back the zero value of the type.117 static Value zero() {118 return static_cast<Value>(0);119 }120 /// \brief Gives back the positive infinity value of the type.121 static Value infinity() {122 return std::numeric_limits<Value>::infinity();123 }124 /// \brief Gives back the sum of the given two elements.125 static Value plus(const Value& left, const Value& right) {126 return left + right;127 }128 /// \brief Gives back \c true only if the first value is less than129 /// the second.130 static bool less(const Value& left, const Value& right) {131 return left + eps < right;132 }133 };134 135 87 /// \brief Default traits class of BellmanFord class. 136 88 /// … … 156 108 /// It defines the used operations and the infinity value for the 157 109 /// given \c Value type. 158 /// \see BellmanFordDefaultOperationTraits, 159 /// BellmanFordToleranceOperationTraits 110 /// \see BellmanFordDefaultOperationTraits 160 111 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 161 112 … … 221 172 /// the lengths of the arcs. The default map type is 222 173 /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 223 /// \tparam TR The traits class that defines various types used by the224 /// algorithm. By default, it is \ref BellmanFordDefaultTraits225 /// "BellmanFordDefaultTraits<GR, LEN>".226 /// In most cases, this parameter should not be set directly,227 /// consider to use the named template parameters instead.228 174 #ifdef DOXYGEN 229 175 template <typename GR, typename LEN, typename TR> … … 887 833 /// It defines the used operations and the infinity value for the 888 834 /// given \c Value type. 889 /// \see BellmanFordDefaultOperationTraits, 890 /// BellmanFordToleranceOperationTraits 835 /// \see BellmanFordDefaultOperationTraits 891 836 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; 892 837 … … 989 934 /// This class should only be used through the \ref bellmanFord() 990 935 /// function, which makes it easier to use the algorithm. 991 ///992 /// \tparam TR The traits class that defines various types used by the993 /// algorithm.994 936 template<class TR> 995 937 class BellmanFordWizard : public TR { -
lemon/bfs.h
r891 r835 122 122 ///\tparam GR The type of the digraph the algorithm runs on. 123 123 ///The default type is \ref ListDigraph. 124 ///\tparam TR The traits class that defines various types used by the125 ///algorithm. By default, it is \ref BfsDefaultTraits126 ///"BfsDefaultTraits<GR>".127 ///In most cases, this parameter should not be set directly,128 ///consider to use the named template parameters instead.129 124 #ifdef DOXYGEN 130 125 template <typename GR, … … 963 958 /// This class should only be used through the \ref bfs() function, 964 959 /// which makes it easier to use the algorithm. 965 ///966 /// \tparam TR The traits class that defines various types used by the967 /// algorithm.968 960 template<class TR> 969 961 class BfsWizard : public TR … … 1304 1296 /// does not observe the BFS events. If you want to observe the BFS 1305 1297 /// events, you should implement your own visitor class. 1306 /// \tparam TR T he traits class that defines varioustypes used by the1307 /// algorithm. By default, it is \ref BfsVisitDefaultTraits1308 /// "BfsVisitDefaultTraits<GR>".1309 /// In most cases, this parameter should not be set directly,1310 /// consider to use the named template parameters instead.1298 /// \tparam TR Traits class to set various data types used by the 1299 /// algorithm. The default traits class is 1300 /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>". 1301 /// See \ref BfsVisitDefaultTraits for the documentation of 1302 /// a BFS visit traits class. 1311 1303 #ifdef DOXYGEN 1312 1304 template <typename GR, typename VS, typename TR> -
lemon/capacity_scaling.h
r911 r887 78 78 /// \tparam GR The digraph type the algorithm runs on. 79 79 /// \tparam V The number type used for flow amounts, capacity bounds 80 /// and supply values in the algorithm. By default ,it is \c int.80 /// and supply values in the algorithm. By default it is \c int. 81 81 /// \tparam C The number type used for costs and potentials in the 82 /// algorithm. By default, it is the same as \c V. 83 /// \tparam TR The traits class that defines various types used by the 84 /// algorithm. By default, it is \ref CapacityScalingDefaultTraits 85 /// "CapacityScalingDefaultTraits<GR, V, C>". 86 /// In most cases, this parameter should not be set directly, 87 /// consider to use the named template parameters instead. 82 /// algorithm. By default it is the same as \c V. 88 83 /// 89 84 /// \warning Both number types must be signed and all input data must … … 140 135 141 136 typedef std::vector<int> IntVector; 137 typedef std::vector<char> BoolVector; 142 138 typedef std::vector<Value> ValueVector; 143 139 typedef std::vector<Cost> CostVector; 144 typedef std::vector<char> BoolVector;145 // Note: vector<char> is used instead of vector<bool> for efficiency reasons146 140 147 141 private: … … 321 315 "The cost type of CapacityScaling must be signed"); 322 316 323 // Reset data structures 317 // Resize vectors 318 _node_num = countNodes(_graph); 319 _arc_num = countArcs(_graph); 320 _res_arc_num = 2 * (_arc_num + _node_num); 321 _root = _node_num; 322 ++_node_num; 323 324 _first_out.resize(_node_num + 1); 325 _forward.resize(_res_arc_num); 326 _source.resize(_res_arc_num); 327 _target.resize(_res_arc_num); 328 _reverse.resize(_res_arc_num); 329 330 _lower.resize(_res_arc_num); 331 _upper.resize(_res_arc_num); 332 _cost.resize(_res_arc_num); 333 _supply.resize(_node_num); 334 335 _res_cap.resize(_res_arc_num); 336 _pi.resize(_node_num); 337 _excess.resize(_node_num); 338 _pred.resize(_node_num); 339 340 // Copy the graph 341 int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1; 342 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 343 _node_id[n] = i; 344 } 345 i = 0; 346 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 347 _first_out[i] = j; 348 for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) { 349 _arc_idf[a] = j; 350 _forward[j] = true; 351 _source[j] = i; 352 _target[j] = _node_id[_graph.runningNode(a)]; 353 } 354 for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) { 355 _arc_idb[a] = j; 356 _forward[j] = false; 357 _source[j] = i; 358 _target[j] = _node_id[_graph.runningNode(a)]; 359 } 360 _forward[j] = false; 361 _source[j] = i; 362 _target[j] = _root; 363 _reverse[j] = k; 364 _forward[k] = true; 365 _source[k] = _root; 366 _target[k] = i; 367 _reverse[k] = j; 368 ++j; ++k; 369 } 370 _first_out[i] = j; 371 _first_out[_node_num] = k; 372 for (ArcIt a(_graph); a != INVALID; ++a) { 373 int fi = _arc_idf[a]; 374 int bi = _arc_idb[a]; 375 _reverse[fi] = bi; 376 _reverse[bi] = fi; 377 } 378 379 // Reset parameters 324 380 reset(); 325 381 } … … 456 512 /// \endcode 457 513 /// 458 /// This function can be called more than once. All the givenparameters459 /// are kept for the next call, unless \ref resetParams() or \ref reset()460 /// is used, thus only the modified parameters have to be set again.461 /// If the underlying digraph was also modified after the construction462 /// of the class (or the last \ref reset() call), then the \ref reset()463 /// function must be called.514 /// This function can be called more than once. All the parameters 515 /// that have been given are kept for the next call, unless 516 /// \ref reset() is called, thus only the modified parameters 517 /// have to be set again. See \ref reset() for examples. 518 /// However, the underlying digraph must not be modified after this 519 /// class have been constructed, since it copies and extends the graph. 464 520 /// 465 521 /// \param factor The capacity scaling factor. It must be larger than … … 478 534 /// 479 535 /// \see ProblemType 480 /// \see resetParams(), reset()481 536 ProblemType run(int factor = 4) { 482 537 _factor = factor; … … 492 547 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 493 548 /// 494 /// It is useful for multiple \ref run() calls. Basically, all the given 495 /// parameters are kept for the next \ref run() call, unless 496 /// \ref resetParams() or \ref reset() is used. 497 /// If the underlying digraph was also modified after the construction 498 /// of the class or the last \ref reset() call, then the \ref reset() 499 /// function must be used, otherwise \ref resetParams() is sufficient. 549 /// It is useful for multiple run() calls. If this function is not 550 /// used, all the parameters given before are kept for the next 551 /// \ref run() call. 552 /// However, the underlying digraph must not be modified after this 553 /// class have been constructed, since it copies and extends the graph. 500 554 /// 501 555 /// For example, … … 507 561 /// .supplyMap(sup).run(); 508 562 /// 509 /// // Run again with modified cost map (reset Params() is not called,563 /// // Run again with modified cost map (reset() is not called, 510 564 /// // so only the cost map have to be set again) 511 565 /// cost[e] += 100; 512 566 /// cs.costMap(cost).run(); 513 567 /// 514 /// // Run again from scratch using reset Params()568 /// // Run again from scratch using reset() 515 569 /// // (the lower bounds will be set to zero on all arcs) 516 /// cs.reset Params();570 /// cs.reset(); 517 571 /// cs.upperMap(capacity).costMap(cost) 518 572 /// .supplyMap(sup).run(); … … 520 574 /// 521 575 /// \return <tt>(*this)</tt> 522 /// 523 /// \see reset(), run() 524 CapacityScaling& resetParams() { 576 CapacityScaling& reset() { 525 577 for (int i = 0; i != _node_num; ++i) { 526 578 _supply[i] = 0; … … 532 584 } 533 585 _have_lower = false; 534 return *this;535 }536 537 /// \brief Reset the internal data structures and all the parameters538 /// that have been given before.539 ///540 /// This function resets the internal data structures and all the541 /// paramaters that have been given before using functions \ref lowerMap(),542 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().543 ///544 /// It is useful for multiple \ref run() calls. Basically, all the given545 /// parameters are kept for the next \ref run() call, unless546 /// \ref resetParams() or \ref reset() is used.547 /// If the underlying digraph was also modified after the construction548 /// of the class or the last \ref reset() call, then the \ref reset()549 /// function must be used, otherwise \ref resetParams() is sufficient.550 ///551 /// See \ref resetParams() for examples.552 ///553 /// \return <tt>(*this)</tt>554 ///555 /// \see resetParams(), run()556 CapacityScaling& reset() {557 // Resize vectors558 _node_num = countNodes(_graph);559 _arc_num = countArcs(_graph);560 _res_arc_num = 2 * (_arc_num + _node_num);561 _root = _node_num;562 ++_node_num;563 564 _first_out.resize(_node_num + 1);565 _forward.resize(_res_arc_num);566 _source.resize(_res_arc_num);567 _target.resize(_res_arc_num);568 _reverse.resize(_res_arc_num);569 570 _lower.resize(_res_arc_num);571 _upper.resize(_res_arc_num);572 _cost.resize(_res_arc_num);573 _supply.resize(_node_num);574 575 _res_cap.resize(_res_arc_num);576 _pi.resize(_node_num);577 _excess.resize(_node_num);578 _pred.resize(_node_num);579 580 // Copy the graph581 int i = 0, j = 0, k = 2 * _arc_num + _node_num - 1;582 for (NodeIt n(_graph); n != INVALID; ++n, ++i) {583 _node_id[n] = i;584 }585 i = 0;586 for (NodeIt n(_graph); n != INVALID; ++n, ++i) {587 _first_out[i] = j;588 for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {589 _arc_idf[a] = j;590 _forward[j] = true;591 _source[j] = i;592 _target[j] = _node_id[_graph.runningNode(a)];593 }594 for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {595 _arc_idb[a] = j;596 _forward[j] = false;597 _source[j] = i;598 _target[j] = _node_id[_graph.runningNode(a)];599 }600 _forward[j] = false;601 _source[j] = i;602 _target[j] = _root;603 _reverse[j] = k;604 _forward[k] = true;605 _source[k] = _root;606 _target[k] = i;607 _reverse[k] = j;608 ++j; ++k;609 }610 _first_out[i] = j;611 _first_out[_node_num] = k;612 for (ArcIt a(_graph); a != INVALID; ++a) {613 int fi = _arc_idf[a];614 int bi = _arc_idb[a];615 _reverse[fi] = bi;616 _reverse[bi] = fi;617 }618 619 // Reset parameters620 resetParams();621 586 return *this; 622 587 } … … 800 765 if (_factor > 1) { 801 766 // With scaling 802 Value max_sup = 0, max_dem = 0 , max_cap = 0;803 for (int i = 0; i != _ root; ++i) {767 Value max_sup = 0, max_dem = 0; 768 for (int i = 0; i != _node_num; ++i) { 804 769 Value ex = _excess[i]; 805 770 if ( ex > max_sup) max_sup = ex; 806 771 if (-ex > max_dem) max_dem = -ex; 807 int last_out = _first_out[i+1] - 1;808 for (int j = _first_out[i]; j != last_out; ++j) {809 if (_res_cap[j] > max_cap) max_cap = _res_cap[j];810 }772 } 773 Value max_cap = 0; 774 for (int j = 0; j != _res_arc_num; ++j) { 775 if (_res_cap[j] > max_cap) max_cap = _res_cap[j]; 811 776 } 812 777 max_sup = std::min(std::min(max_sup, max_dem), max_cap); -
lemon/circulation.h
r891 r833 174 174 \tparam SM The type of the supply map. The default map type is 175 175 \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>". 176 \tparam TR The traits class that defines various types used by the177 algorithm. By default, it is \ref CirculationDefaultTraits178 "CirculationDefaultTraits<GR, LM, UM, SM>".179 In most cases, this parameter should not be set directly,180 consider to use the named template parameters instead.181 176 */ 182 177 #ifdef DOXYGEN -
lemon/cost_scaling.h
r911 r887 105 105 /// \tparam GR The digraph type the algorithm runs on. 106 106 /// \tparam V The number type used for flow amounts, capacity bounds 107 /// and supply values in the algorithm. By default ,it is \c int.107 /// and supply values in the algorithm. By default it is \c int. 108 108 /// \tparam C The number type used for costs and potentials in the 109 /// algorithm. By default, it is the same as \c V. 110 /// \tparam TR The traits class that defines various types used by the 111 /// algorithm. By default, it is \ref CostScalingDefaultTraits 112 /// "CostScalingDefaultTraits<GR, V, C>". 113 /// In most cases, this parameter should not be set directly, 114 /// consider to use the named template parameters instead. 109 /// algorithm. By default it is the same as \c V. 115 110 /// 116 111 /// \warning Both number types must be signed and all input data must … … 142 137 /// 143 138 /// The large cost type used for internal computations. 144 /// By default, it is \c long \c long if the \c Cost type is integer, 139 /// Using the \ref CostScalingDefaultTraits "default traits class", 140 /// it is \c long \c long if the \c Cost type is integer, 145 141 /// otherwise it is \c double. 146 142 typedef typename TR::LargeCost LargeCost; … … 202 198 203 199 typedef std::vector<int> IntVector; 200 typedef std::vector<char> BoolVector; 204 201 typedef std::vector<Value> ValueVector; 205 202 typedef std::vector<Cost> CostVector; 206 203 typedef std::vector<LargeCost> LargeCostVector; 207 typedef std::vector<char> BoolVector;208 // Note: vector<char> is used instead of vector<bool> for efficiency reasons209 204 210 205 private: … … 250 245 bool _have_lower; 251 246 Value _sum_supply; 252 int _sup_node_num;253 247 254 248 // Data structures for storing the digraph … … 279 273 int _alpha; 280 274 281 IntVector _buckets;282 IntVector _bucket_next;283 IntVector _bucket_prev;284 IntVector _rank;285 int _max_rank;286 287 275 // Data for a StaticDigraph structure 288 276 typedef std::pair<int, int> IntPair; … … 345 333 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, 346 334 "The cost type of CostScaling must be signed"); 347 348 // Reset data structures 349 reset(); 350 } 351 352 /// \name Parameters 353 /// The parameters of the algorithm can be specified using these 354 /// functions. 355 356 /// @{ 357 358 /// \brief Set the lower bounds on the arcs. 359 /// 360 /// This function sets the lower bounds on the arcs. 361 /// If it is not used before calling \ref run(), the lower bounds 362 /// will be set to zero on all arcs. 363 /// 364 /// \param map An arc map storing the lower bounds. 365 /// Its \c Value type must be convertible to the \c Value type 366 /// of the algorithm. 367 /// 368 /// \return <tt>(*this)</tt> 369 template <typename LowerMap> 370 CostScaling& lowerMap(const LowerMap& map) { 371 _have_lower = true; 372 for (ArcIt a(_graph); a != INVALID; ++a) { 373 _lower[_arc_idf[a]] = map[a]; 374 _lower[_arc_idb[a]] = map[a]; 375 } 376 return *this; 377 } 378 379 /// \brief Set the upper bounds (capacities) on the arcs. 380 /// 381 /// This function sets the upper bounds (capacities) on the arcs. 382 /// If it is not used before calling \ref run(), the upper bounds 383 /// will be set to \ref INF on all arcs (i.e. the flow value will be 384 /// unbounded from above). 385 /// 386 /// \param map An arc map storing the upper bounds. 387 /// Its \c Value type must be convertible to the \c Value type 388 /// of the algorithm. 389 /// 390 /// \return <tt>(*this)</tt> 391 template<typename UpperMap> 392 CostScaling& upperMap(const UpperMap& map) { 393 for (ArcIt a(_graph); a != INVALID; ++a) { 394 _upper[_arc_idf[a]] = map[a]; 395 } 396 return *this; 397 } 398 399 /// \brief Set the costs of the arcs. 400 /// 401 /// This function sets the costs of the arcs. 402 /// If it is not used before calling \ref run(), the costs 403 /// will be set to \c 1 on all arcs. 404 /// 405 /// \param map An arc map storing the costs. 406 /// Its \c Value type must be convertible to the \c Cost type 407 /// of the algorithm. 408 /// 409 /// \return <tt>(*this)</tt> 410 template<typename CostMap> 411 CostScaling& costMap(const CostMap& map) { 412 for (ArcIt a(_graph); a != INVALID; ++a) { 413 _scost[_arc_idf[a]] = map[a]; 414 _scost[_arc_idb[a]] = -map[a]; 415 } 416 return *this; 417 } 418 419 /// \brief Set the supply values of the nodes. 420 /// 421 /// This function sets the supply values of the nodes. 422 /// If neither this function nor \ref stSupply() is used before 423 /// calling \ref run(), the supply of each node will be set to zero. 424 /// 425 /// \param map A node map storing the supply values. 426 /// Its \c Value type must be convertible to the \c Value type 427 /// of the algorithm. 428 /// 429 /// \return <tt>(*this)</tt> 430 template<typename SupplyMap> 431 CostScaling& supplyMap(const SupplyMap& map) { 432 for (NodeIt n(_graph); n != INVALID; ++n) { 433 _supply[_node_id[n]] = map[n]; 434 } 435 return *this; 436 } 437 438 /// \brief Set single source and target nodes and a supply value. 439 /// 440 /// This function sets a single source node and a single target node 441 /// and the required flow value. 442 /// If neither this function nor \ref supplyMap() is used before 443 /// calling \ref run(), the supply of each node will be set to zero. 444 /// 445 /// Using this function has the same effect as using \ref supplyMap() 446 /// with such a map in which \c k is assigned to \c s, \c -k is 447 /// assigned to \c t and all other nodes have zero supply value. 448 /// 449 /// \param s The source node. 450 /// \param t The target node. 451 /// \param k The required amount of flow from node \c s to node \c t 452 /// (i.e. the supply of \c s and the demand of \c t). 453 /// 454 /// \return <tt>(*this)</tt> 455 CostScaling& stSupply(const Node& s, const Node& t, Value k) { 456 for (int i = 0; i != _res_node_num; ++i) { 457 _supply[i] = 0; 458 } 459 _supply[_node_id[s]] = k; 460 _supply[_node_id[t]] = -k; 461 return *this; 462 } 463 464 /// @} 465 466 /// \name Execution control 467 /// The algorithm can be executed using \ref run(). 468 469 /// @{ 470 471 /// \brief Run the algorithm. 472 /// 473 /// This function runs the algorithm. 474 /// The paramters can be specified using functions \ref lowerMap(), 475 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 476 /// For example, 477 /// \code 478 /// CostScaling<ListDigraph> cs(graph); 479 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 480 /// .supplyMap(sup).run(); 481 /// \endcode 482 /// 483 /// This function can be called more than once. All the given parameters 484 /// are kept for the next call, unless \ref resetParams() or \ref reset() 485 /// is used, thus only the modified parameters have to be set again. 486 /// If the underlying digraph was also modified after the construction 487 /// of the class (or the last \ref reset() call), then the \ref reset() 488 /// function must be called. 489 /// 490 /// \param method The internal method that will be used in the 491 /// algorithm. For more information, see \ref Method. 492 /// \param factor The cost scaling factor. It must be larger than one. 493 /// 494 /// \return \c INFEASIBLE if no feasible flow exists, 495 /// \n \c OPTIMAL if the problem has optimal solution 496 /// (i.e. it is feasible and bounded), and the algorithm has found 497 /// optimal flow and node potentials (primal and dual solutions), 498 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 499 /// and infinite upper bound. It means that the objective function 500 /// is unbounded on that arc, however, note that it could actually be 501 /// bounded over the feasible flows, but this algroithm cannot handle 502 /// these cases. 503 /// 504 /// \see ProblemType, Method 505 /// \see resetParams(), reset() 506 ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) { 507 _alpha = factor; 508 ProblemType pt = init(); 509 if (pt != OPTIMAL) return pt; 510 start(method); 511 return OPTIMAL; 512 } 513 514 /// \brief Reset all the parameters that have been given before. 515 /// 516 /// This function resets all the paramaters that have been given 517 /// before using functions \ref lowerMap(), \ref upperMap(), 518 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 519 /// 520 /// It is useful for multiple \ref run() calls. Basically, all the given 521 /// parameters are kept for the next \ref run() call, unless 522 /// \ref resetParams() or \ref reset() is used. 523 /// If the underlying digraph was also modified after the construction 524 /// of the class or the last \ref reset() call, then the \ref reset() 525 /// function must be used, otherwise \ref resetParams() is sufficient. 526 /// 527 /// For example, 528 /// \code 529 /// CostScaling<ListDigraph> cs(graph); 530 /// 531 /// // First run 532 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 533 /// .supplyMap(sup).run(); 534 /// 535 /// // Run again with modified cost map (resetParams() is not called, 536 /// // so only the cost map have to be set again) 537 /// cost[e] += 100; 538 /// cs.costMap(cost).run(); 539 /// 540 /// // Run again from scratch using resetParams() 541 /// // (the lower bounds will be set to zero on all arcs) 542 /// cs.resetParams(); 543 /// cs.upperMap(capacity).costMap(cost) 544 /// .supplyMap(sup).run(); 545 /// \endcode 546 /// 547 /// \return <tt>(*this)</tt> 548 /// 549 /// \see reset(), run() 550 CostScaling& resetParams() { 551 for (int i = 0; i != _res_node_num; ++i) { 552 _supply[i] = 0; 553 } 554 int limit = _first_out[_root]; 555 for (int j = 0; j != limit; ++j) { 556 _lower[j] = 0; 557 _upper[j] = INF; 558 _scost[j] = _forward[j] ? 1 : -1; 559 } 560 for (int j = limit; j != _res_arc_num; ++j) { 561 _lower[j] = 0; 562 _upper[j] = INF; 563 _scost[j] = 0; 564 _scost[_reverse[j]] = 0; 565 } 566 _have_lower = false; 567 return *this; 568 } 569 570 /// \brief Reset all the parameters that have been given before. 571 /// 572 /// This function resets all the paramaters that have been given 573 /// before using functions \ref lowerMap(), \ref upperMap(), 574 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 575 /// 576 /// It is useful for multiple run() calls. If this function is not 577 /// used, all the parameters given before are kept for the next 578 /// \ref run() call. 579 /// However, the underlying digraph must not be modified after this 580 /// class have been constructed, since it copies and extends the graph. 581 /// \return <tt>(*this)</tt> 582 CostScaling& reset() { 335 583 336 // Resize vectors 584 337 _node_num = countNodes(_graph); … … 648 401 649 402 // Reset parameters 650 resetParams(); 403 reset(); 404 } 405 406 /// \name Parameters 407 /// The parameters of the algorithm can be specified using these 408 /// functions. 409 410 /// @{ 411 412 /// \brief Set the lower bounds on the arcs. 413 /// 414 /// This function sets the lower bounds on the arcs. 415 /// If it is not used before calling \ref run(), the lower bounds 416 /// will be set to zero on all arcs. 417 /// 418 /// \param map An arc map storing the lower bounds. 419 /// Its \c Value type must be convertible to the \c Value type 420 /// of the algorithm. 421 /// 422 /// \return <tt>(*this)</tt> 423 template <typename LowerMap> 424 CostScaling& lowerMap(const LowerMap& map) { 425 _have_lower = true; 426 for (ArcIt a(_graph); a != INVALID; ++a) { 427 _lower[_arc_idf[a]] = map[a]; 428 _lower[_arc_idb[a]] = map[a]; 429 } 430 return *this; 431 } 432 433 /// \brief Set the upper bounds (capacities) on the arcs. 434 /// 435 /// This function sets the upper bounds (capacities) on the arcs. 436 /// If it is not used before calling \ref run(), the upper bounds 437 /// will be set to \ref INF on all arcs (i.e. the flow value will be 438 /// unbounded from above). 439 /// 440 /// \param map An arc map storing the upper bounds. 441 /// Its \c Value type must be convertible to the \c Value type 442 /// of the algorithm. 443 /// 444 /// \return <tt>(*this)</tt> 445 template<typename UpperMap> 446 CostScaling& upperMap(const UpperMap& map) { 447 for (ArcIt a(_graph); a != INVALID; ++a) { 448 _upper[_arc_idf[a]] = map[a]; 449 } 450 return *this; 451 } 452 453 /// \brief Set the costs of the arcs. 454 /// 455 /// This function sets the costs of the arcs. 456 /// If it is not used before calling \ref run(), the costs 457 /// will be set to \c 1 on all arcs. 458 /// 459 /// \param map An arc map storing the costs. 460 /// Its \c Value type must be convertible to the \c Cost type 461 /// of the algorithm. 462 /// 463 /// \return <tt>(*this)</tt> 464 template<typename CostMap> 465 CostScaling& costMap(const CostMap& map) { 466 for (ArcIt a(_graph); a != INVALID; ++a) { 467 _scost[_arc_idf[a]] = map[a]; 468 _scost[_arc_idb[a]] = -map[a]; 469 } 470 return *this; 471 } 472 473 /// \brief Set the supply values of the nodes. 474 /// 475 /// This function sets the supply values of the nodes. 476 /// If neither this function nor \ref stSupply() is used before 477 /// calling \ref run(), the supply of each node will be set to zero. 478 /// 479 /// \param map A node map storing the supply values. 480 /// Its \c Value type must be convertible to the \c Value type 481 /// of the algorithm. 482 /// 483 /// \return <tt>(*this)</tt> 484 template<typename SupplyMap> 485 CostScaling& supplyMap(const SupplyMap& map) { 486 for (NodeIt n(_graph); n != INVALID; ++n) { 487 _supply[_node_id[n]] = map[n]; 488 } 489 return *this; 490 } 491 492 /// \brief Set single source and target nodes and a supply value. 493 /// 494 /// This function sets a single source node and a single target node 495 /// and the required flow value. 496 /// If neither this function nor \ref supplyMap() is used before 497 /// calling \ref run(), the supply of each node will be set to zero. 498 /// 499 /// Using this function has the same effect as using \ref supplyMap() 500 /// with such a map in which \c k is assigned to \c s, \c -k is 501 /// assigned to \c t and all other nodes have zero supply value. 502 /// 503 /// \param s The source node. 504 /// \param t The target node. 505 /// \param k The required amount of flow from node \c s to node \c t 506 /// (i.e. the supply of \c s and the demand of \c t). 507 /// 508 /// \return <tt>(*this)</tt> 509 CostScaling& stSupply(const Node& s, const Node& t, Value k) { 510 for (int i = 0; i != _res_node_num; ++i) { 511 _supply[i] = 0; 512 } 513 _supply[_node_id[s]] = k; 514 _supply[_node_id[t]] = -k; 515 return *this; 516 } 517 518 /// @} 519 520 /// \name Execution control 521 /// The algorithm can be executed using \ref run(). 522 523 /// @{ 524 525 /// \brief Run the algorithm. 526 /// 527 /// This function runs the algorithm. 528 /// The paramters can be specified using functions \ref lowerMap(), 529 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(). 530 /// For example, 531 /// \code 532 /// CostScaling<ListDigraph> cs(graph); 533 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 534 /// .supplyMap(sup).run(); 535 /// \endcode 536 /// 537 /// This function can be called more than once. All the parameters 538 /// that have been given are kept for the next call, unless 539 /// \ref reset() is called, thus only the modified parameters 540 /// have to be set again. See \ref reset() for examples. 541 /// However, the underlying digraph must not be modified after this 542 /// class have been constructed, since it copies and extends the graph. 543 /// 544 /// \param method The internal method that will be used in the 545 /// algorithm. For more information, see \ref Method. 546 /// \param factor The cost scaling factor. It must be larger than one. 547 /// 548 /// \return \c INFEASIBLE if no feasible flow exists, 549 /// \n \c OPTIMAL if the problem has optimal solution 550 /// (i.e. it is feasible and bounded), and the algorithm has found 551 /// optimal flow and node potentials (primal and dual solutions), 552 /// \n \c UNBOUNDED if the digraph contains an arc of negative cost 553 /// and infinite upper bound. It means that the objective function 554 /// is unbounded on that arc, however, note that it could actually be 555 /// bounded over the feasible flows, but this algroithm cannot handle 556 /// these cases. 557 /// 558 /// \see ProblemType, Method 559 ProblemType run(Method method = PARTIAL_AUGMENT, int factor = 8) { 560 _alpha = factor; 561 ProblemType pt = init(); 562 if (pt != OPTIMAL) return pt; 563 start(method); 564 return OPTIMAL; 565 } 566 567 /// \brief Reset all the parameters that have been given before. 568 /// 569 /// This function resets all the paramaters that have been given 570 /// before using functions \ref lowerMap(), \ref upperMap(), 571 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 572 /// 573 /// It is useful for multiple run() calls. If this function is not 574 /// used, all the parameters given before are kept for the next 575 /// \ref run() call. 576 /// However, the underlying digraph must not be modified after this 577 /// class have been constructed, since it copies and extends the graph. 578 /// 579 /// For example, 580 /// \code 581 /// CostScaling<ListDigraph> cs(graph); 582 /// 583 /// // First run 584 /// cs.lowerMap(lower).upperMap(upper).costMap(cost) 585 /// .supplyMap(sup).run(); 586 /// 587 /// // Run again with modified cost map (reset() is not called, 588 /// // so only the cost map have to be set again) 589 /// cost[e] += 100; 590 /// cs.costMap(cost).run(); 591 /// 592 /// // Run again from scratch using reset() 593 /// // (the lower bounds will be set to zero on all arcs) 594 /// cs.reset(); 595 /// cs.upperMap(capacity).costMap(cost) 596 /// .supplyMap(sup).run(); 597 /// \endcode 598 /// 599 /// \return <tt>(*this)</tt> 600 CostScaling& reset() { 601 for (int i = 0; i != _res_node_num; ++i) { 602 _supply[i] = 0; 603 } 604 int limit = _first_out[_root]; 605 for (int j = 0; j != limit; ++j) { 606 _lower[j] = 0; 607 _upper[j] = INF; 608 _scost[j] = _forward[j] ? 1 : -1; 609 } 610 for (int j = limit; j != _res_arc_num; ++j) { 611 _lower[j] = 0; 612 _upper[j] = INF; 613 _scost[j] = 0; 614 _scost[_reverse[j]] = 0; 615 } 616 _have_lower = false; 651 617 return *this; 652 618 } … … 837 803 } 838 804 839 _sup_node_num = 0;840 for (NodeIt n(_graph); n != INVALID; ++n) {841 if (sup[n] > 0) ++_sup_node_num;842 }843 844 805 // Find a feasible flow using Circulation 845 806 Circulation<Digraph, ConstMap<Arc, Value>, ValueArcMap, ValueNodeMap> … … 876 837 for (int a = _first_out[_root]; a != _res_arc_num; ++a) { 877 838 int ra = _reverse[a]; 878 _res_cap[a] = 0;839 _res_cap[a] = 1; 879 840 _res_cap[ra] = 0; 880 841 _cost[a] = 0; … … 890 851 // Maximum path length for partial augment 891 852 const int MAX_PATH_LENGTH = 4; 892 893 // Initialize data structures for buckets 894 _max_rank = _alpha * _res_node_num; 895 _buckets.resize(_max_rank); 896 _bucket_next.resize(_res_node_num + 1); 897 _bucket_prev.resize(_res_node_num + 1); 898 _rank.resize(_res_node_num + 1); 899 853 900 854 // Execute the algorithm 901 855 switch (method) { … … 936 890 } 937 891 } 938 939 // Initialize a cost scaling phase 940 void initPhase() { 941 // Saturate arcs not satisfying the optimality condition 942 for (int u = 0; u != _res_node_num; ++u) { 943 int last_out = _first_out[u+1]; 944 LargeCost pi_u = _pi[u]; 945 for (int a = _first_out[u]; a != last_out; ++a) { 946 int v = _target[a]; 947 if (_res_cap[a] > 0 && _cost[a] + pi_u - _pi[v] < 0) { 892 893 /// Execute the algorithm performing augment and relabel operations 894 void startAugment(int max_length = std::numeric_limits<int>::max()) { 895 // Paramters for heuristics 896 const int BF_HEURISTIC_EPSILON_BOUND = 1000; 897 const int BF_HEURISTIC_BOUND_FACTOR = 3; 898 899 // Perform cost scaling phases 900 IntVector pred_arc(_res_node_num); 901 std::vector<int> path_nodes; 902 for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ? 903 1 : _epsilon / _alpha ) 904 { 905 // "Early Termination" heuristic: use Bellman-Ford algorithm 906 // to check if the current flow is optimal 907 if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) { 908 _arc_vec.clear(); 909 _cost_vec.clear(); 910 for (int j = 0; j != _res_arc_num; ++j) { 911 if (_res_cap[j] > 0) { 912 _arc_vec.push_back(IntPair(_source[j], _target[j])); 913 _cost_vec.push_back(_cost[j] + 1); 914 } 915 } 916 _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end()); 917 918 BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map); 919 bf.init(0); 920 bool done = false; 921 int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num)); 922 for (int i = 0; i < K && !done; ++i) 923 done = bf.processNextWeakRound(); 924 if (done) break; 925 } 926 927 // Saturate arcs not satisfying the optimality condition 928 for (int a = 0; a != _res_arc_num; ++a) { 929 if (_res_cap[a] > 0 && 930 _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) { 948 931 Value delta = _res_cap[a]; 949 _excess[ u] -= delta;950 _excess[ v] += delta;932 _excess[_source[a]] -= delta; 933 _excess[_target[a]] += delta; 951 934 _res_cap[a] = 0; 952 935 _res_cap[_reverse[a]] += delta; 953 936 } 954 937 } 955 } 956 957 // Find active nodes (i.e. nodes with positive excess) 958 for (int u = 0; u != _res_node_num; ++u) { 959 if (_excess[u] > 0) _active_nodes.push_back(u); 960 } 961 962 // Initialize the next arcs 963 for (int u = 0; u != _res_node_num; ++u) { 964 _next_out[u] = _first_out[u]; 965 } 966 } 967 968 // Early termination heuristic 969 bool earlyTermination() { 970 const double EARLY_TERM_FACTOR = 3.0; 971 972 // Build a static residual graph 973 _arc_vec.clear(); 974 _cost_vec.clear(); 975 for (int j = 0; j != _res_arc_num; ++j) { 976 if (_res_cap[j] > 0) { 977 _arc_vec.push_back(IntPair(_source[j], _target[j])); 978 _cost_vec.push_back(_cost[j] + 1); 979 } 980 } 981 _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end()); 982 983 // Run Bellman-Ford algorithm to check if the current flow is optimal 984 BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map); 985 bf.init(0); 986 bool done = false; 987 int K = int(EARLY_TERM_FACTOR * std::sqrt(double(_res_node_num))); 988 for (int i = 0; i < K && !done; ++i) { 989 done = bf.processNextWeakRound(); 990 } 991 return done; 992 } 993 994 // Global potential update heuristic 995 void globalUpdate() { 996 int bucket_end = _root + 1; 997 998 // Initialize buckets 999 for (int r = 0; r != _max_rank; ++r) { 1000 _buckets[r] = bucket_end; 1001 } 1002 Value total_excess = 0; 1003 for (int i = 0; i != _res_node_num; ++i) { 1004 if (_excess[i] < 0) { 1005 _rank[i] = 0; 1006 _bucket_next[i] = _buckets[0]; 1007 _bucket_prev[_buckets[0]] = i; 1008 _buckets[0] = i; 1009 } else { 1010 total_excess += _excess[i]; 1011 _rank[i] = _max_rank; 1012 } 1013 } 1014 if (total_excess == 0) return; 1015 1016 // Search the buckets 1017 int r = 0; 1018 for ( ; r != _max_rank; ++r) { 1019 while (_buckets[r] != bucket_end) { 1020 // Remove the first node from the current bucket 1021 int u = _buckets[r]; 1022 _buckets[r] = _bucket_next[u]; 1023 1024 // Search the incomming arcs of u 1025 LargeCost pi_u = _pi[u]; 1026 int last_out = _first_out[u+1]; 1027 for (int a = _first_out[u]; a != last_out; ++a) { 1028 int ra = _reverse[a]; 1029 if (_res_cap[ra] > 0) { 1030 int v = _source[ra]; 1031 int old_rank_v = _rank[v]; 1032 if (r < old_rank_v) { 1033 // Compute the new rank of v 1034 LargeCost nrc = (_cost[ra] + _pi[v] - pi_u) / _epsilon; 1035 int new_rank_v = old_rank_v; 1036 if (nrc < LargeCost(_max_rank)) 1037 new_rank_v = r + 1 + int(nrc); 1038 1039 // Change the rank of v 1040 if (new_rank_v < old_rank_v) { 1041 _rank[v] = new_rank_v; 1042 _next_out[v] = _first_out[v]; 1043 1044 // Remove v from its old bucket 1045 if (old_rank_v < _max_rank) { 1046 if (_buckets[old_rank_v] == v) { 1047 _buckets[old_rank_v] = _bucket_next[v]; 1048 } else { 1049 _bucket_next[_bucket_prev[v]] = _bucket_next[v]; 1050 _bucket_prev[_bucket_next[v]] = _bucket_prev[v]; 1051 } 1052 } 1053 1054 // Insert v to its new bucket 1055 _bucket_next[v] = _buckets[new_rank_v]; 1056 _bucket_prev[_buckets[new_rank_v]] = v; 1057 _buckets[new_rank_v] = v; 1058 } 1059 } 1060 } 1061 } 1062 1063 // Finish search if there are no more active nodes 1064 if (_excess[u] > 0) { 1065 total_excess -= _excess[u]; 1066 if (total_excess <= 0) break; 1067 } 1068 } 1069 if (total_excess <= 0) break; 1070 } 1071 1072 // Relabel nodes 1073 for (int u = 0; u != _res_node_num; ++u) { 1074 int k = std::min(_rank[u], r); 1075 if (k > 0) { 1076 _pi[u] -= _epsilon * k; 938 939 // Find active nodes (i.e. nodes with positive excess) 940 for (int u = 0; u != _res_node_num; ++u) { 941 if (_excess[u] > 0) _active_nodes.push_back(u); 942 } 943 944 // Initialize the next arcs 945 for (int u = 0; u != _res_node_num; ++u) { 1077 946 _next_out[u] = _first_out[u]; 1078 947 } 1079 } 1080 } 1081 1082 /// Execute the algorithm performing augment and relabel operations 1083 void startAugment(int max_length = std::numeric_limits<int>::max()) { 1084 // Paramters for heuristics 1085 const int EARLY_TERM_EPSILON_LIMIT = 1000; 1086 const double GLOBAL_UPDATE_FACTOR = 3.0; 1087 1088 const int global_update_freq = int(GLOBAL_UPDATE_FACTOR * 1089 (_res_node_num + _sup_node_num * _sup_node_num)); 1090 int next_update_limit = global_update_freq; 1091 1092 int relabel_cnt = 0; 1093 1094 // Perform cost scaling phases 1095 std::vector<int> path; 1096 for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ? 1097 1 : _epsilon / _alpha ) 1098 { 1099 // Early termination heuristic 1100 if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) { 1101 if (earlyTermination()) break; 1102 } 1103 1104 // Initialize current phase 1105 initPhase(); 1106 948 1107 949 // Perform partial augment and relabel operations 1108 950 while (true) { … … 1114 956 if (_active_nodes.size() == 0) break; 1115 957 int start = _active_nodes.front(); 958 path_nodes.clear(); 959 path_nodes.push_back(start); 1116 960 1117 961 // Find an augmenting path from the start node 1118 path.clear();1119 962 int tip = start; 1120 while (_excess[tip] >= 0 && int(path.size()) < max_length) { 963 while (_excess[tip] >= 0 && 964 int(path_nodes.size()) <= max_length) { 1121 965 int u; 1122 LargeCost min_red_cost, rc, pi_tip = _pi[tip]; 1123 int last_out = _first_out[tip+1]; 966 LargeCost min_red_cost, rc; 967 int last_out = _sum_supply < 0 ? 968 _first_out[tip+1] : _first_out[tip+1] - 1; 1124 969 for (int a = _next_out[tip]; a != last_out; ++a) { 1125 u = _target[a]; 1126 if (_res_cap[a] > 0 && _cost[a] + pi_tip - _pi[u] < 0) { 1127 path.push_back(a); 970 if (_res_cap[a] > 0 && 971 _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) { 972 u = _target[a]; 973 pred_arc[u] = a; 1128 974 _next_out[tip] = a; 1129 975 tip = u; 976 path_nodes.push_back(tip); 1130 977 goto next_step; 1131 978 } … … 1133 980 1134 981 // Relabel tip node 1135 min_red_cost = std::numeric_limits<LargeCost>::max(); 1136 if (tip != start) { 1137 int ra = _reverse[path.back()]; 1138 min_red_cost = _cost[ra] + pi_tip - _pi[_target[ra]]; 1139 } 982 min_red_cost = std::numeric_limits<LargeCost>::max() / 2; 1140 983 for (int a = _first_out[tip]; a != last_out; ++a) { 1141 rc = _cost[a] + pi_tip- _pi[_target[a]];984 rc = _cost[a] + _pi[_source[a]] - _pi[_target[a]]; 1142 985 if (_res_cap[a] > 0 && rc < min_red_cost) { 1143 986 min_red_cost = rc; … … 1145 988 } 1146 989 _pi[tip] -= min_red_cost + _epsilon; 990 991 // Reset the next arc of tip 1147 992 _next_out[tip] = _first_out[tip]; 1148 ++relabel_cnt;1149 993 1150 994 // Step back 1151 995 if (tip != start) { 1152 tip = _source[path.back()];1153 path.pop_back();996 path_nodes.pop_back(); 997 tip = path_nodes.back(); 1154 998 } 1155 999 … … 1159 1003 // Augment along the found path (as much flow as possible) 1160 1004 Value delta; 1161 int pa, u, v = start; 1162 for (int i = 0; i != int(path.size()); ++i) { 1163 pa = path[i]; 1005 int u, v = path_nodes.front(), pa; 1006 for (int i = 1; i < int(path_nodes.size()); ++i) { 1164 1007 u = v; 1165 v = _target[pa]; 1008 v = path_nodes[i]; 1009 pa = pred_arc[v]; 1166 1010 delta = std::min(_res_cap[pa], _excess[u]); 1167 1011 _res_cap[pa] -= delta; … … 1172 1016 _active_nodes.push_back(v); 1173 1017 } 1174 1175 // Global update heuristic1176 if (relabel_cnt >= next_update_limit) {1177 globalUpdate();1178 next_update_limit += global_update_freq;1179 }1180 1018 } 1181 1019 } … … 1185 1023 void startPush() { 1186 1024 // Paramters for heuristics 1187 const int EARLY_TERM_EPSILON_LIMIT = 1000; 1188 const double GLOBAL_UPDATE_FACTOR = 2.0; 1189 1190 const int global_update_freq = int(GLOBAL_UPDATE_FACTOR * 1191 (_res_node_num + _sup_node_num * _sup_node_num)); 1192 int next_update_limit = global_update_freq; 1193 1194 int relabel_cnt = 0; 1195 1025 const int BF_HEURISTIC_EPSILON_BOUND = 1000; 1026 const int BF_HEURISTIC_BOUND_FACTOR = 3; 1027 1196 1028 // Perform cost scaling phases 1197 1029 BoolVector hyper(_res_node_num, false); 1198 LargeCostVector hyper_cost(_res_node_num);1199 1030 for ( ; _epsilon >= 1; _epsilon = _epsilon < _alpha && _epsilon > 1 ? 1200 1031 1 : _epsilon / _alpha ) 1201 1032 { 1202 // Early termination heuristic 1203 if (_epsilon <= EARLY_TERM_EPSILON_LIMIT) { 1204 if (earlyTermination()) break; 1205 } 1206 1207 // Initialize current phase 1208 initPhase(); 1033 // "Early Termination" heuristic: use Bellman-Ford algorithm 1034 // to check if the current flow is optimal 1035 if (_epsilon <= BF_HEURISTIC_EPSILON_BOUND) { 1036 _arc_vec.clear(); 1037 _cost_vec.clear(); 1038 for (int j = 0; j != _res_arc_num; ++j) { 1039 if (_res_cap[j] > 0) { 1040 _arc_vec.push_back(IntPair(_source[j], _target[j])); 1041 _cost_vec.push_back(_cost[j] + 1); 1042 } 1043 } 1044 _sgr.build(_res_node_num, _arc_vec.begin(), _arc_vec.end()); 1045 1046 BellmanFord<StaticDigraph, LargeCostArcMap> bf(_sgr, _cost_map); 1047 bf.init(0); 1048 bool done = false; 1049 int K = int(BF_HEURISTIC_BOUND_FACTOR * sqrt(_res_node_num)); 1050 for (int i = 0; i < K && !done; ++i) 1051 done = bf.processNextWeakRound(); 1052 if (done) break; 1053 } 1054 1055 // Saturate arcs not satisfying the optimality condition 1056 for (int a = 0; a != _res_arc_num; ++a) { 1057 if (_res_cap[a] > 0 && 1058 _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) { 1059 Value delta = _res_cap[a]; 1060 _excess[_source[a]] -= delta; 1061 _excess[_target[a]] += delta; 1062 _res_cap[a] = 0; 1063 _res_cap[_reverse[a]] += delta; 1064 } 1065 } 1066 1067 // Find active nodes (i.e. nodes with positive excess) 1068 for (int u = 0; u != _res_node_num; ++u) { 1069 if (_excess[u] > 0) _active_nodes.push_back(u); 1070 } 1071 1072 // Initialize the next arcs 1073 for (int u = 0; u != _res_node_num; ++u) { 1074 _next_out[u] = _first_out[u]; 1075 } 1209 1076 1210 1077 // Perform push and relabel operations 1211 1078 while (_active_nodes.size() > 0) { 1212 LargeCost min_red_cost, rc , pi_n;1079 LargeCost min_red_cost, rc; 1213 1080 Value delta; 1214 1081 int n, t, a, last_out = _res_arc_num; 1215 1082 1083 // Select an active node (FIFO selection) 1216 1084 next_node: 1217 // Select an active node (FIFO selection)1218 1085 n = _active_nodes.front(); 1219 last_out = _ first_out[n+1];1220 pi_n = _pi[n];1221 1086 last_out = _sum_supply < 0 ? 1087 _first_out[n+1] : _first_out[n+1] - 1; 1088 1222 1089 // Perform push operations if there are admissible arcs 1223 1090 if (_excess[n] > 0) { 1224 1091 for (a = _next_out[n]; a != last_out; ++a) { 1225 1092 if (_res_cap[a] > 0 && 1226 _cost[a] + pi_n- _pi[_target[a]] < 0) {1093 _cost[a] + _pi[_source[a]] - _pi[_target[a]] < 0) { 1227 1094 delta = std::min(_res_cap[a], _excess[n]); 1228 1095 t = _target[a]; … … 1230 1097 // Push-look-ahead heuristic 1231 1098 Value ahead = -_excess[t]; 1232 int last_out_t = _ first_out[t+1];1233 LargeCost pi_t = _pi[t];1099 int last_out_t = _sum_supply < 0 ? 1100 _first_out[t+1] : _first_out[t+1] - 1; 1234 1101 for (int ta = _next_out[t]; ta != last_out_t; ++ta) { 1235 1102 if (_res_cap[ta] > 0 && 1236 _cost[ta] + pi_t- _pi[_target[ta]] < 0)1103 _cost[ta] + _pi[_source[ta]] - _pi[_target[ta]] < 0) 1237 1104 ahead += _res_cap[ta]; 1238 1105 if (ahead >= delta) break; … … 1241 1108 1242 1109 // Push flow along the arc 1243 if (ahead < delta && !hyper[t]) {1110 if (ahead < delta) { 1244 1111 _res_cap[a] -= ahead; 1245 1112 _res_cap[_reverse[a]] += ahead; … … 1248 1115 _active_nodes.push_front(t); 1249 1116 hyper[t] = true; 1250 hyper_cost[t] = _cost[a] + pi_n - pi_t;1251 1117 _next_out[n] = a; 1252 1118 goto next_node; … … 1271 1137 // Relabel the node if it is still active (or hyper) 1272 1138 if (_excess[n] > 0 || hyper[n]) { 1273 min_red_cost = hyper[n] ? -hyper_cost[n] : 1274 std::numeric_limits<LargeCost>::max(); 1139 min_red_cost = std::numeric_limits<LargeCost>::max() / 2; 1275 1140 for (int a = _first_out[n]; a != last_out; ++a) { 1276 rc = _cost[a] + pi_n- _pi[_target[a]];1141 rc = _cost[a] + _pi[_source[a]] - _pi[_target[a]]; 1277 1142 if (_res_cap[a] > 0 && rc < min_red_cost) { 1278 1143 min_red_cost = rc; … … 1280 1145 } 1281 1146 _pi[n] -= min_red_cost + _epsilon; 1147 hyper[n] = false; 1148 1149 // Reset the next arc 1282 1150 _next_out[n] = _first_out[n]; 1283 hyper[n] = false;1284 ++relabel_cnt;1285 1151 } 1286 1152 … … 1292 1158 _active_nodes.pop_front(); 1293 1159 } 1294 1295 // Global update heuristic1296 if (relabel_cnt >= next_update_limit) {1297 globalUpdate();1298 for (int u = 0; u != _res_node_num; ++u)1299 hyper[u] = false;1300 next_update_limit += global_update_freq;1301 }1302 1160 } 1303 1161 } -
lemon/cycle_canceling.h
r911 r886 145 145 146 146 typedef std::vector<int> IntVector; 147 typedef std::vector<char> CharVector; 147 148 typedef std::vector<double> DoubleVector; 148 149 typedef std::vector<Value> ValueVector; 149 150 typedef std::vector<Cost> CostVector; 150 typedef std::vector<char> BoolVector;151 // Note: vector<char> is used instead of vector<bool> for efficiency reasons152 151 153 152 private: … … 200 199 IntArcMap _arc_idb; 201 200 IntVector _first_out; 202 BoolVector _forward;201 CharVector _forward; 203 202 IntVector _source; 204 203 IntVector _target; … … 252 251 "The cost type of CycleCanceling must be signed"); 253 252 254 // Reset data structures 253 // Resize vectors 254 _node_num = countNodes(_graph); 255 _arc_num = countArcs(_graph); 256 _res_node_num = _node_num + 1; 257 _res_arc_num = 2 * (_arc_num + _node_num); 258 _root = _node_num; 259 260 _first_out.resize(_res_node_num + 1); 261 _forward.resize(_res_arc_num); 262 _source.resize(_res_arc_num); 263 _target.resize(_res_arc_num); 264 _reverse.resize(_res_arc_num); 265 266 _lower.resize(_res_arc_num); 267 _upper.resize(_res_arc_num); 268 _cost.resize(_res_arc_num); 269 _supply.resize(_res_node_num); 270 271 _res_cap.resize(_res_arc_num); 272 _pi.resize(_res_node_num); 273 274 _arc_vec.reserve(_res_arc_num); 275 _cost_vec.reserve(_res_arc_num); 276 _id_vec.reserve(_res_arc_num); 277 278 // Copy the graph 279 int i = 0, j = 0, k = 2 * _arc_num + _node_num; 280 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 281 _node_id[n] = i; 282 } 283 i = 0; 284 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 285 _first_out[i] = j; 286 for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) { 287 _arc_idf[a] = j; 288 _forward[j] = true; 289 _source[j] = i; 290 _target[j] = _node_id[_graph.runningNode(a)]; 291 } 292 for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) { 293 _arc_idb[a] = j; 294 _forward[j] = false; 295 _source[j] = i; 296 _target[j] = _node_id[_graph.runningNode(a)]; 297 } 298 _forward[j] = false; 299 _source[j] = i; 300 _target[j] = _root; 301 _reverse[j] = k; 302 _forward[k] = true; 303 _source[k] = _root; 304 _target[k] = i; 305 _reverse[k] = j; 306 ++j; ++k; 307 } 308 _first_out[i] = j; 309 _first_out[_res_node_num] = k; 310 for (ArcIt a(_graph); a != INVALID; ++a) { 311 int fi = _arc_idf[a]; 312 int bi = _arc_idb[a]; 313 _reverse[fi] = bi; 314 _reverse[bi] = fi; 315 } 316 317 // Reset parameters 255 318 reset(); 256 319 } … … 387 450 /// \endcode 388 451 /// 389 /// This function can be called more than once. All the givenparameters390 /// are kept for the next call, unless \ref resetParams() or \ref reset()391 /// is used, thus only the modified parameters have to be set again.392 /// If the underlying digraph was also modified after the construction393 /// of the class (or the last \ref reset() call), then the \ref reset()394 /// function must be called.452 /// This function can be called more than once. All the parameters 453 /// that have been given are kept for the next call, unless 454 /// \ref reset() is called, thus only the modified parameters 455 /// have to be set again. See \ref reset() for examples. 456 /// However, the underlying digraph must not be modified after this 457 /// class have been constructed, since it copies and extends the graph. 395 458 /// 396 459 /// \param method The cycle-canceling method that will be used. … … 408 471 /// 409 472 /// \see ProblemType, Method 410 /// \see resetParams(), reset()411 473 ProblemType run(Method method = CANCEL_AND_TIGHTEN) { 412 474 ProblemType pt = init(); … … 422 484 /// \ref costMap(), \ref supplyMap(), \ref stSupply(). 423 485 /// 424 /// It is useful for multiple \ref run() calls. Basically, all the given 425 /// parameters are kept for the next \ref run() call, unless 426 /// \ref resetParams() or \ref reset() is used. 427 /// If the underlying digraph was also modified after the construction 428 /// of the class or the last \ref reset() call, then the \ref reset() 429 /// function must be used, otherwise \ref resetParams() is sufficient. 486 /// It is useful for multiple run() calls. If this function is not 487 /// used, all the parameters given before are kept for the next 488 /// \ref run() call. 489 /// However, the underlying digraph must not be modified after this 490 /// class have been constructed, since it copies and extends the graph. 430 491 /// 431 492 /// For example, … … 437 498 /// .supplyMap(sup).run(); 438 499 /// 439 /// // Run again with modified cost map (reset Params() is not called,500 /// // Run again with modified cost map (reset() is not called, 440 501 /// // so only the cost map have to be set again) 441 502 /// cost[e] += 100; 442 503 /// cc.costMap(cost).run(); 443 504 /// 444 /// // Run again from scratch using reset Params()505 /// // Run again from scratch using reset() 445 506 /// // (the lower bounds will be set to zero on all arcs) 446 /// cc.reset Params();507 /// cc.reset(); 447 508 /// cc.upperMap(capacity).costMap(cost) 448 509 /// .supplyMap(sup).run(); … … 450 511 /// 451 512 /// \return <tt>(*this)</tt> 452 /// 453 /// \see reset(), run() 454 CycleCanceling& resetParams() { 513 CycleCanceling& reset() { 455 514 for (int i = 0; i != _res_node_num; ++i) { 456 515 _supply[i] = 0; … … 469 528 } 470 529 _have_lower = false; 471 return *this;472 }473 474 /// \brief Reset the internal data structures and all the parameters475 /// that have been given before.476 ///477 /// This function resets the internal data structures and all the478 /// paramaters that have been given before using functions \ref lowerMap(),479 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply().480 ///481 /// It is useful for multiple \ref run() calls. Basically, all the given482 /// parameters are kept for the next \ref run() call, unless483 /// \ref resetParams() or \ref reset() is used.484 /// If the underlying digraph was also modified after the construction485 /// of the class or the last \ref reset() call, then the \ref reset()486 /// function must be used, otherwise \ref resetParams() is sufficient.487 ///488 /// See \ref resetParams() for examples.489 ///490 /// \return <tt>(*this)</tt>491 ///492 /// \see resetParams(), run()493 CycleCanceling& reset() {494 // Resize vectors495 _node_num = countNodes(_graph);496 _arc_num = countArcs(_graph);497 _res_node_num = _node_num + 1;498 _res_arc_num = 2 * (_arc_num + _node_num);499 _root = _node_num;500 501 _first_out.resize(_res_node_num + 1);502 _forward.resize(_res_arc_num);503 _source.resize(_res_arc_num);504 _target.resize(_res_arc_num);505 _reverse.resize(_res_arc_num);506 507 _lower.resize(_res_arc_num);508 _upper.resize(_res_arc_num);509 _cost.resize(_res_arc_num);510 _supply.resize(_res_node_num);511 512 _res_cap.resize(_res_arc_num);513 _pi.resize(_res_node_num);514 515 _arc_vec.reserve(_res_arc_num);516 _cost_vec.reserve(_res_arc_num);517 _id_vec.reserve(_res_arc_num);518 519 // Copy the graph520 int i = 0, j = 0, k = 2 * _arc_num + _node_num;521 for (NodeIt n(_graph); n != INVALID; ++n, ++i) {522 _node_id[n] = i;523 }524 i = 0;525 for (NodeIt n(_graph); n != INVALID; ++n, ++i) {526 _first_out[i] = j;527 for (OutArcIt a(_graph, n); a != INVALID; ++a, ++j) {528 _arc_idf[a] = j;529 _forward[j] = true;530 _source[j] = i;531 _target[j] = _node_id[_graph.runningNode(a)];532 }533 for (InArcIt a(_graph, n); a != INVALID; ++a, ++j) {534 _arc_idb[a] = j;535 _forward[j] = false;536 _source[j] = i;537 _target[j] = _node_id[_graph.runningNode(a)];538 }539 _forward[j] = false;540 _source[j] = i;541 _target[j] = _root;542 _reverse[j] = k;543 _forward[k] = true;544 _source[k] = _root;545 _target[k] = i;546 _reverse[k] = j;547 ++j; ++k;548 }549 _first_out[i] = j;550 _first_out[_res_node_num] = k;551 for (ArcIt a(_graph); a != INVALID; ++a) {552 int fi = _arc_idf[a];553 int bi = _arc_idb[a];554 _reverse[fi] = bi;555 _reverse[bi] = fi;556 }557 558 // Reset parameters559 resetParams();560 530 return *this; 561 531 } … … 964 934 DoubleVector pi(_res_node_num, 0.0); 965 935 IntVector level(_res_node_num); 966 BoolVector reached(_res_node_num);967 BoolVector processed(_res_node_num);936 CharVector reached(_res_node_num); 937 CharVector processed(_res_node_num); 968 938 IntVector pred_node(_res_node_num); 969 939 IntVector pred_arc(_res_node_num); -
lemon/dfs.h
r891 r835 122 122 ///\tparam GR The type of the digraph the algorithm runs on. 123 123 ///The default type is \ref ListDigraph. 124 ///\tparam TR The traits class that defines various types used by the125 ///algorithm. By default, it is \ref DfsDefaultTraits126 ///"DfsDefaultTraits<GR>".127 ///In most cases, this parameter should not be set directly,128 ///consider to use the named template parameters instead.129 124 #ifdef DOXYGEN 130 125 template <typename GR, … … 893 888 /// This class should only be used through the \ref dfs() function, 894 889 /// which makes it easier to use the algorithm. 895 ///896 /// \tparam TR The traits class that defines various types used by the897 /// algorithm.898 890 template<class TR> 899 891 class DfsWizard : public TR … … 1246 1238 /// does not observe the DFS events. If you want to observe the DFS 1247 1239 /// events, you should implement your own visitor class. 1248 /// \tparam TR T he traits class that defines varioustypes used by the1249 /// algorithm. By default, it is \ref DfsVisitDefaultTraits1250 /// "DfsVisitDefaultTraits<GR>".1251 /// In most cases, this parameter should not be set directly,1252 /// consider to use the named template parameters instead.1240 /// \tparam TR Traits class to set various data types used by the 1241 /// algorithm. The default traits class is 1242 /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>". 1243 /// See \ref DfsVisitDefaultTraits for the documentation of 1244 /// a DFS visit traits class. 1253 1245 #ifdef DOXYGEN 1254 1246 template <typename GR, typename VS, typename TR> -
lemon/dijkstra.h
r891 r835 193 193 ///it is necessary. The default map type is \ref 194 194 ///concepts::Digraph::ArcMap "GR::ArcMap<int>". 195 ///\tparam TR The traits class that defines various types used by the196 ///algorithm. By default, it is \ref DijkstraDefaultTraits197 ///"DijkstraDefaultTraits<GR, LEN>".198 ///In most cases, this parameter should not be set directly,199 ///consider to use the named template parameters instead.200 195 #ifdef DOXYGEN 201 196 template <typename GR, typename LEN, typename TR> … … 1098 1093 /// This class should only be used through the \ref dijkstra() function, 1099 1094 /// which makes it easier to use the algorithm. 1100 ///1101 /// \tparam TR The traits class that defines various types used by the1102 /// algorithm.1103 1095 template<class TR> 1104 1096 class DijkstraWizard : public TR -
lemon/glpk.h
r902 r793 26 26 #include <lemon/lp_base.h> 27 27 28 // forward declaration 29 #if !defined _GLP_PROB && !defined GLP_PROB 30 #define _GLP_PROB 31 #define GLP_PROB 32 typedef struct { double _opaque_prob; } glp_prob; 33 /* LP/MIP problem object */ 34 #endif 35 28 36 namespace lemon { 29 37 30 namespace _solver_bits {31 class VoidPtr {32 private:33 void *_ptr;34 public:35 VoidPtr() : _ptr(0) {}36 37 template <typename T>38 VoidPtr(T* ptr) : _ptr(reinterpret_cast<void*>(ptr)) {}39 40 template <typename T>41 VoidPtr& operator=(T* ptr) {42 _ptr = reinterpret_cast<void*>(ptr);43 return *this;44 }45 46 template <typename T>47 operator T*() const { return reinterpret_cast<T*>(_ptr); }48 };49 }50 38 51 39 /// \brief Base interface for the GLPK LP and MIP solver … … 56 44 protected: 57 45 58 _solver_bits::VoidPtr lp; 46 typedef glp_prob LPX; 47 glp_prob* lp; 59 48 60 49 GlpkBase(); … … 135 124 136 125 ///Pointer to the underlying GLPK data structure. 137 _solver_bits::VoidPtrlpx() {return lp;}126 LPX *lpx() {return lp;} 138 127 ///Const pointer to the underlying GLPK data structure. 139 _solver_bits::VoidPtrlpx() const {return lp;}128 const LPX *lpx() const {return lp;} 140 129 141 130 ///Returns the constraint identifier understood by GLPK. -
lemon/graph_to_eps.h
r909 r833 685 685 #else 686 686 os << bits::getWinFormattedDate(); 687 os << std::endl;688 687 #endif 689 688 } 689 os << std::endl; 690 690 691 691 if (_autoArcWidthScale) { -
lemon/hartmann_orlin.h
r914 r859 107 107 /// \tparam LEN The type of the length map. The default 108 108 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 109 /// \tparam TR The traits class that defines various types used by the110 /// algorithm. By default, it is \ref HartmannOrlinDefaultTraits111 /// "HartmannOrlinDefaultTraits<GR, LEN>".112 /// In most cases, this parameter should not be set directly,113 /// consider to use the named template parameters instead.114 109 #ifdef DOXYGEN 115 110 template <typename GR, typename LEN, typename TR> … … 133 128 /// 134 129 /// The large value type used for internal computations. 135 /// By default, it is \c long \c long if the \c Value type is integer, 130 /// Using the \ref HartmannOrlinDefaultTraits "default traits class", 131 /// it is \c long \c long if the \c Value type is integer, 136 132 /// otherwise it is \c double. 137 133 typedef typename TR::LargeValue LargeValue; … … 406 402 /// \pre \ref run() or \ref findMinMean() must be called before 407 403 /// using this function. 408 Value cycleLength() const {409 return static_cast<Value>(_best_length);404 LargeValue cycleLength() const { 405 return _best_length; 410 406 } 411 407 -
lemon/howard.h
r914 r818 107 107 /// \tparam LEN The type of the length map. The default 108 108 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 109 /// \tparam TR The traits class that defines various types used by the110 /// algorithm. By default, it is \ref HowardDefaultTraits111 /// "HowardDefaultTraits<GR, LEN>".112 /// In most cases, this parameter should not be set directly,113 /// consider to use the named template parameters instead.114 109 #ifdef DOXYGEN 115 110 template <typename GR, typename LEN, typename TR> … … 133 128 /// 134 129 /// The large value type used for internal computations. 135 /// By default, it is \c long \c long if the \c Value type is integer, 130 /// Using the \ref HowardDefaultTraits "default traits class", 131 /// it is \c long \c long if the \c Value type is integer, 136 132 /// otherwise it is \c double. 137 133 typedef typename TR::LargeValue LargeValue; … … 385 381 /// \pre \ref run() or \ref findMinMean() must be called before 386 382 /// using this function. 387 Value cycleLength() const {388 return static_cast<Value>(_best_length);383 LargeValue cycleLength() const { 384 return _best_length; 389 385 } 390 386 -
lemon/karp.h
r914 r819 105 105 /// \tparam LEN The type of the length map. The default 106 106 /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 107 /// \tparam TR The traits class that defines various types used by the108 /// algorithm. By default, it is \ref KarpDefaultTraits109 /// "KarpDefaultTraits<GR, LEN>".110 /// In most cases, this parameter should not be set directly,111 /// consider to use the named template parameters instead.112 107 #ifdef DOXYGEN 113 108 template <typename GR, typename LEN, typename TR> … … 131 126 /// 132 127 /// The large value type used for internal computations. 133 /// By default, it is \c long \c long if the \c Value type is integer, 128 /// Using the \ref KarpDefaultTraits "default traits class", 129 /// it is \c long \c long if the \c Value type is integer, 134 130 /// otherwise it is \c double. 135 131 typedef typename TR::LargeValue LargeValue; … … 393 389 /// \pre \ref run() or \ref findMinMean() must be called before 394 390 /// using this function. 395 Value cycleLength() const {396 return static_cast<Value>(_cycle_length);391 LargeValue cycleLength() const { 392 return _cycle_length; 397 393 } 398 394 -
lemon/lp_base.h
r903 r833 1230 1230 Row r; 1231 1231 c.expr().simplify(); 1232 r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound() -*c.expr():-INF,1232 r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound():-INF, 1233 1233 ExprIterator(c.expr().comps.begin(), cols), 1234 1234 ExprIterator(c.expr().comps.end(), cols), 1235 c.upperBounded()?c.upperBound() -*c.expr():INF));1235 c.upperBounded()?c.upperBound():INF)); 1236 1236 return r; 1237 1237 } -
lemon/min_cost_arborescence.h
r891 r760 113 113 /// it is necessary. The default map type is \ref 114 114 /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>". 115 /// \tparam TR The traits class that defines various types used by the 116 /// algorithm. By default, it is \ref MinCostArborescenceDefaultTraits 115 /// \param TR Traits class to set various data types used 116 /// by the algorithm. The default traits class is 117 /// \ref MinCostArborescenceDefaultTraits 117 118 /// "MinCostArborescenceDefaultTraits<GR, CM>". 118 /// In most cases, this parameter should not be set directly,119 /// consider to use the named template parameters instead.120 119 #ifndef DOXYGEN 121 120 template <typename GR, … … 124 123 MinCostArborescenceDefaultTraits<GR, CM> > 125 124 #else 126 template <typename GR, typename CM, type nameTR>125 template <typename GR, typename CM, typedef TR> 127 126 #endif 128 127 class MinCostArborescence { -
lemon/network_simplex.h
r911 r878 165 165 166 166 typedef std::vector<int> IntVector; 167 typedef std::vector<char> CharVector; 167 168 typedef std::vector<Value> ValueVector; 168 169 typedef std::vector<Cost> CostVector; 169 typedef std::vector<char> BoolVector;170 // Note: vector<char> is used instead of vector<bool> for efficiency reasons171 170 172 171 // State constants for arcs … … 196 195 IntVector _source; 197 196 IntVector _target; 198 bool _arc_mixing;199 197 200 198 // Node and arc data … … 215 213 IntVector _last_succ; 216 214 IntVector _dirty_revs; 217 BoolVector _forward;218 BoolVector _state;215 CharVector _forward; 216 CharVector _state; 219 217 int _root; 220 218 … … 247 245 const IntVector &_target; 248 246 const CostVector &_cost; 249 const BoolVector &_state;247 const CharVector &_state; 250 248 const CostVector &_pi; 251 249 int &_in_arc; … … 268 266 bool findEnteringArc() { 269 267 Cost c; 270 for (int e = _next_arc; e !=_search_arc_num; ++e) {268 for (int e = _next_arc; e < _search_arc_num; ++e) { 271 269 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 272 270 if (c < 0) { … … 276 274 } 277 275 } 278 for (int e = 0; e !=_next_arc; ++e) {276 for (int e = 0; e < _next_arc; ++e) { 279 277 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 280 278 if (c < 0) { … … 299 297 const IntVector &_target; 300 298 const CostVector &_cost; 301 const BoolVector &_state;299 const CharVector &_state; 302 300 const CostVector &_pi; 303 301 int &_in_arc; … … 316 314 bool findEnteringArc() { 317 315 Cost c, min = 0; 318 for (int e = 0; e !=_search_arc_num; ++e) {316 for (int e = 0; e < _search_arc_num; ++e) { 319 317 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 320 318 if (c < min) { … … 338 336 const IntVector &_target; 339 337 const CostVector &_cost; 340 const BoolVector &_state;338 const CharVector &_state; 341 339 const CostVector &_pi; 342 340 int &_in_arc; … … 357 355 { 358 356 // The main parameters of the pivot rule 359 const double BLOCK_SIZE_FACTOR = 1.0;357 const double BLOCK_SIZE_FACTOR = 0.5; 360 358 const int MIN_BLOCK_SIZE = 10; 361 359 … … 370 368 int cnt = _block_size; 371 369 int e; 372 for (e = _next_arc; e !=_search_arc_num; ++e) {370 for (e = _next_arc; e < _search_arc_num; ++e) { 373 371 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 374 372 if (c < min) { … … 381 379 } 382 380 } 383 for (e = 0; e !=_next_arc; ++e) {381 for (e = 0; e < _next_arc; ++e) { 384 382 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 385 383 if (c < min) { … … 411 409 const IntVector &_target; 412 410 const CostVector &_cost; 413 const BoolVector &_state;411 const CharVector &_state; 414 412 const CostVector &_pi; 415 413 int &_in_arc; … … 472 470 min = 0; 473 471 _curr_length = 0; 474 for (e = _next_arc; e !=_search_arc_num; ++e) {472 for (e = _next_arc; e < _search_arc_num; ++e) { 475 473 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 476 474 if (c < 0) { … … 483 481 } 484 482 } 485 for (e = 0; e !=_next_arc; ++e) {483 for (e = 0; e < _next_arc; ++e) { 486 484 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 487 485 if (c < 0) { … … 514 512 const IntVector &_target; 515 513 const CostVector &_cost; 516 const BoolVector &_state;514 const CharVector &_state; 517 515 const CostVector &_pi; 518 516 int &_in_arc; … … 567 565 // Check the current candidate list 568 566 int e; 569 for (int i = 0; i !=_curr_length; ++i) {567 for (int i = 0; i < _curr_length; ++i) { 570 568 e = _candidates[i]; 571 569 _cand_cost[e] = _state[e] * … … 580 578 int limit = _head_length; 581 579 582 for (e = _next_arc; e !=_search_arc_num; ++e) {580 for (e = _next_arc; e < _search_arc_num; ++e) { 583 581 _cand_cost[e] = _state[e] * 584 582 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); … … 592 590 } 593 591 } 594 for (e = 0; e !=_next_arc; ++e) {592 for (e = 0; e < _next_arc; ++e) { 595 593 _cand_cost[e] = _state[e] * 596 594 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); … … 636 634 NetworkSimplex(const GR& graph, bool arc_mixing = false) : 637 635 _graph(graph), _node_id(graph), _arc_id(graph), 638 _arc_mixing(arc_mixing),639 636 MAX(std::numeric_limits<Value>::max()), 640 637 INF(std::numeric_limits<Value>::has_infinity ? … … 647 644 "The cost type of NetworkSimplex must be signed"); 648 645 649 // Reset data structures 646 // Resize vectors 647 _node_num = countNodes(_graph); 648 _arc_num = countArcs(_graph); 649 int all_node_num = _node_num + 1; 650 int max_arc_num = _arc_num + 2 * _node_num; 651 652 _source.resize(max_arc_num); 653 _target.resize(max_arc_num); 654 655 _lower.resize(_arc_num); 656 _upper.resize(_arc_num); 657 _cap.resize(max_arc_num); 658 _cost.resize(max_arc_num); 659 _supply.resize(all_node_num); 660 _flow.resize(max_arc_num); 661 _pi.resize(all_node_num); 662 663 _parent.resize(all_node_num); 664 _pred.resize(all_node_num); 665 _forward.resize(all_node_num); 666 _thread.resize(all_node_num); 667 _rev_thread.resize(all_node_num); 668 _succ_num.resize(all_node_num); 669 _last_succ.resize(all_node_num); 670 _state.resize(max_arc_num); 671 672 // Copy the graph 673 int i = 0; 674 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 675 _node_id[n] = i; 676 } 677 if (arc_mixing) { 678 // Store the arcs in a mixed order 679 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 680 int i = 0, j = 0; 681 for (ArcIt a(_graph); a != INVALID; ++a) { 682 _arc_id[a] = i; 683 _source[i] = _node_id[_graph.source(a)]; 684 _target[i] = _node_id[_graph.target(a)]; 685 if ((i += k) >= _arc_num) i = ++j; 686 } 687 } else { 688 // Store the arcs in the original order 689 int i = 0; 690 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { 691 _arc_id[a] = i; 692 _source[i] = _node_id[_graph.source(a)]; 693 _target[i] = _node_id[_graph.target(a)]; 694 } 695 } 696 697 // Reset parameters 650 698 reset(); 651 699 } … … 795 843 /// \endcode 796 844 /// 797 /// This function can be called more than once. All the givenparameters798 /// are kept for the next call, unless \ref resetParams() or \ref reset()799 /// is used, thus only the modified parameters have to be set again.800 /// If the underlying digraph was also modified after the construction801 /// of the class (or the last \ref reset() call), then the \ref reset()802 /// function must be called.845 /// This function can be called more than once. All the parameters 846 /// that have been given are kept for the next call, unless 847 /// \ref reset() is called, thus only the modified parameters 848 /// have to be set again. See \ref reset() for examples. 849 /// However, the underlying digraph must not be modified after this 850 /// class have been constructed, since it copies and extends the graph. 803 851 /// 804 852 /// \param pivot_rule The pivot rule that will be used during the … … 814 862 /// 815 863 /// \see ProblemType, PivotRule 816 /// \see resetParams(), reset()817 864 ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) { 818 865 if (!init()) return INFEASIBLE; … … 826 873 /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType(). 827 874 /// 828 /// It is useful for multiple \ref run() calls. Basically, all the given 829 /// parameters are kept for the next \ref run() call, unless 830 /// \ref resetParams() or \ref reset() is used. 831 /// If the underlying digraph was also modified after the construction 832 /// of the class or the last \ref reset() call, then the \ref reset() 833 /// function must be used, otherwise \ref resetParams() is sufficient. 875 /// It is useful for multiple run() calls. If this function is not 876 /// used, all the parameters given before are kept for the next 877 /// \ref run() call. 878 /// However, the underlying digraph must not be modified after this 879 /// class have been constructed, since it copies and extends the graph. 834 880 /// 835 881 /// For example, … … 841 887 /// .supplyMap(sup).run(); 842 888 /// 843 /// // Run again with modified cost map (reset Params() is not called,889 /// // Run again with modified cost map (reset() is not called, 844 890 /// // so only the cost map have to be set again) 845 891 /// cost[e] += 100; 846 892 /// ns.costMap(cost).run(); 847 893 /// 848 /// // Run again from scratch using reset Params()894 /// // Run again from scratch using reset() 849 895 /// // (the lower bounds will be set to zero on all arcs) 850 /// ns.reset Params();896 /// ns.reset(); 851 897 /// ns.upperMap(capacity).costMap(cost) 852 898 /// .supplyMap(sup).run(); … … 854 900 /// 855 901 /// \return <tt>(*this)</tt> 856 /// 857 /// \see reset(), run() 858 NetworkSimplex& resetParams() { 902 NetworkSimplex& reset() { 859 903 for (int i = 0; i != _node_num; ++i) { 860 904 _supply[i] = 0; … … 870 914 } 871 915 872 /// \brief Reset the internal data structures and all the parameters873 /// that have been given before.874 ///875 /// This function resets the internal data structures and all the876 /// paramaters that have been given before using functions \ref lowerMap(),877 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(),878 /// \ref supplyType().879 ///880 /// It is useful for multiple \ref run() calls. Basically, all the given881 /// parameters are kept for the next \ref run() call, unless882 /// \ref resetParams() or \ref reset() is used.883 /// If the underlying digraph was also modified after the construction884 /// of the class or the last \ref reset() call, then the \ref reset()885 /// function must be used, otherwise \ref resetParams() is sufficient.886 ///887 /// See \ref resetParams() for examples.888 ///889 /// \return <tt>(*this)</tt>890 ///891 /// \see resetParams(), run()892 NetworkSimplex& reset() {893 // Resize vectors894 _node_num = countNodes(_graph);895 _arc_num = countArcs(_graph);896 int all_node_num = _node_num + 1;897 int max_arc_num = _arc_num + 2 * _node_num;898 899 _source.resize(max_arc_num);900 _target.resize(max_arc_num);901 902 _lower.resize(_arc_num);903 _upper.resize(_arc_num);904 _cap.resize(max_arc_num);905 _cost.resize(max_arc_num);906 _supply.resize(all_node_num);907 _flow.resize(max_arc_num);908 _pi.resize(all_node_num);909 910 _parent.resize(all_node_num);911 _pred.resize(all_node_num);912 _forward.resize(all_node_num);913 _thread.resize(all_node_num);914 _rev_thread.resize(all_node_num);915 _succ_num.resize(all_node_num);916 _last_succ.resize(all_node_num);917 _state.resize(max_arc_num);918 919 // Copy the graph920 int i = 0;921 for (NodeIt n(_graph); n != INVALID; ++n, ++i) {922 _node_id[n] = i;923 }924 if (_arc_mixing) {925 // Store the arcs in a mixed order926 int k = std::max(int(std::sqrt(double(_arc_num))), 10);927 int i = 0, j = 0;928 for (ArcIt a(_graph); a != INVALID; ++a) {929 _arc_id[a] = i;930 _source[i] = _node_id[_graph.source(a)];931 _target[i] = _node_id[_graph.target(a)];932 if ((i += k) >= _arc_num) i = ++j;933 }934 } else {935 // Store the arcs in the original order936 int i = 0;937 for (ArcIt a(_graph); a != INVALID; ++a, ++i) {938 _arc_id[a] = i;939 _source[i] = _node_id[_graph.source(a)];940 _target[i] = _node_id[_graph.target(a)];941 }942 }943 944 // Reset parameters945 resetParams();946 return *this;947 }948 949 916 /// @} 950 917 … … 1362 1329 1363 1330 // Update _rev_thread using the new _thread values 1364 for (int i = 0; i !=int(_dirty_revs.size()); ++i) {1331 for (int i = 0; i < int(_dirty_revs.size()); ++i) { 1365 1332 u = _dirty_revs[i]; 1366 1333 _rev_thread[_thread[u]] = u; … … 1432 1399 _pi[u] += sigma; 1433 1400 } 1434 }1435 1436 // Heuristic initial pivots1437 bool initialPivots() {1438 Value curr, total = 0;1439 std::vector<Node> supply_nodes, demand_nodes;1440 for (NodeIt u(_graph); u != INVALID; ++u) {1441 curr = _supply[_node_id[u]];1442 if (curr > 0) {1443 total += curr;1444 supply_nodes.push_back(u);1445 }1446 else if (curr < 0) {1447 demand_nodes.push_back(u);1448 }1449 }1450 if (_sum_supply > 0) total -= _sum_supply;1451 if (total <= 0) return true;1452 1453 IntVector arc_vector;1454 if (_sum_supply >= 0) {1455 if (supply_nodes.size() == 1 && demand_nodes.size() == 1) {1456 // Perform a reverse graph search from the sink to the source1457 typename GR::template NodeMap<bool> reached(_graph, false);1458 Node s = supply_nodes[0], t = demand_nodes[0];1459 std::vector<Node> stack;1460 reached[t] = true;1461 stack.push_back(t);1462 while (!stack.empty()) {1463 Node u, v = stack.back();1464 stack.pop_back();1465 if (v == s) break;1466 for (InArcIt a(_graph, v); a != INVALID; ++a) {1467 if (reached[u = _graph.source(a)]) continue;1468 int j = _arc_id[a];1469 if (_cap[j] >= total) {1470 arc_vector.push_back(j);1471 reached[u] = true;1472 stack.push_back(u);1473 }1474 }1475 }1476 } else {1477 // Find the min. cost incomming arc for each demand node1478 for (int i = 0; i != int(demand_nodes.size()); ++i) {1479 Node v = demand_nodes[i];1480 Cost c, min_cost = std::numeric_limits<Cost>::max();1481 Arc min_arc = INVALID;1482 for (InArcIt a(_graph, v); a != INVALID; ++a) {1483 c = _cost[_arc_id[a]];1484 if (c < min_cost) {1485 min_cost = c;1486 min_arc = a;1487 }1488 }1489 if (min_arc != INVALID) {1490 arc_vector.push_back(_arc_id[min_arc]);1491 }1492 }1493 }1494 } else {1495 // Find the min. cost outgoing arc for each supply node1496 for (int i = 0; i != int(supply_nodes.size()); ++i) {1497 Node u = supply_nodes[i];1498 Cost c, min_cost = std::numeric_limits<Cost>::max();1499 Arc min_arc = INVALID;1500 for (OutArcIt a(_graph, u); a != INVALID; ++a) {1501 c = _cost[_arc_id[a]];1502 if (c < min_cost) {1503 min_cost = c;1504 min_arc = a;1505 }1506 }1507 if (min_arc != INVALID) {1508 arc_vector.push_back(_arc_id[min_arc]);1509 }1510 }1511 }1512 1513 // Perform heuristic initial pivots1514 for (int i = 0; i != int(arc_vector.size()); ++i) {1515 in_arc = arc_vector[i];1516 if (_state[in_arc] * (_cost[in_arc] + _pi[_source[in_arc]] -1517 _pi[_target[in_arc]]) >= 0) continue;1518 findJoinNode();1519 bool change = findLeavingArc();1520 if (delta >= MAX) return false;1521 changeFlow(change);1522 if (change) {1523 updateTreeStructure();1524 updatePotential();1525 }1526 }1527 return true;1528 1401 } 1529 1402 … … 1550 1423 PivotRuleImpl pivot(*this); 1551 1424 1552 // Perform heuristic initial pivots1553 if (!initialPivots()) return UNBOUNDED;1554 1555 1425 // Execute the Network Simplex algorithm 1556 1426 while (pivot.findEnteringArc()) { -
lemon/planarity.h
r896 r862 519 519 /// 520 520 /// This function implements the Boyer-Myrvold algorithm for 521 /// planarity checking of an undirected simplegraph. It is a simplified521 /// planarity checking of an undirected graph. It is a simplified 522 522 /// version of the PlanarEmbedding algorithm class because neither 523 /// the embedding nor the Kuratowski subdivisons arecomputed.523 /// the embedding nor the kuratowski subdivisons are not computed. 524 524 template <typename GR> 525 525 bool checkPlanarity(const GR& graph) { … … 533 533 /// 534 534 /// This class implements the Boyer-Myrvold algorithm for planar 535 /// embedding of an undirected simplegraph. The planar embedding is an535 /// embedding of an undirected graph. The planar embedding is an 536 536 /// ordering of the outgoing edges of the nodes, which is a possible 537 537 /// configuration to draw the graph in the plane. If there is not 538 /// such ordering then the graph contains a K<sub>5</sub>(full graph539 /// with 5 nodes) or a K<sub>3,3</sub>(complete bipartite graph on540 /// 3 Red and 3 Blue nodes) subdivision.538 /// such ordering then the graph contains a \f$ K_5 \f$ (full graph 539 /// with 5 nodes) or a \f$ K_{3,3} \f$ (complete bipartite graph on 540 /// 3 ANode and 3 BNode) subdivision. 541 541 /// 542 542 /// The current implementation calculates either an embedding or a 543 /// Kuratowski subdivision. The running time of the algorithm is O(n). 544 /// 545 /// \see PlanarDrawing, checkPlanarity() 543 /// Kuratowski subdivision. The running time of the algorithm is 544 /// \f$ O(n) \f$. 546 545 template <typename Graph> 547 546 class PlanarEmbedding { … … 593 592 public: 594 593 595 /// \brief The map type for storing the embedding 596 /// 597 /// The map type for storing the embedding. 598 /// \see embeddingMap() 594 /// \brief The map for store of embedding 599 595 typedef typename Graph::template ArcMap<Arc> EmbeddingMap; 600 596 601 597 /// \brief Constructor 602 598 /// 603 /// Constructor. 604 /// \pre The graph must be simple, i.e. it should not 605 /// contain parallel or loop arcs. 599 /// \note The graph should be simple, i.e. parallel and loop arc 600 /// free. 606 601 PlanarEmbedding(const Graph& graph) 607 602 : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {} 608 603 609 /// \brief Run the algorithm.604 /// \brief Runs the algorithm. 610 605 /// 611 /// This function runs the algorithm.612 /// \param kuratowski If th is parameter is set to \cfalse, then the606 /// Runs the algorithm. 607 /// \param kuratowski If the parameter is false, then the 613 608 /// algorithm does not compute a Kuratowski subdivision. 614 /// \return \c true ifthe graph is planar.609 ///\return %True when the graph is planar. 615 610 bool run(bool kuratowski = true) { 616 611 typedef _planarity_bits::PlanarityVisitor<Graph> Visitor; … … 705 700 } 706 701 707 /// \brief Give back the successor of an arc702 /// \brief Gives back the successor of an arc 708 703 /// 709 /// This function gives back the successor of an arc. Itmakes704 /// Gives back the successor of an arc. This function makes 710 705 /// possible to query the cyclic order of the outgoing arcs from 711 706 /// a node. … … 714 709 } 715 710 716 /// \brief Give back the calculated embedding map711 /// \brief Gives back the calculated embedding map 717 712 /// 718 /// This function gives back the calculated embedding map, which 719 /// contains the successor of each arc in the cyclic order of the 720 /// outgoing arcs of its source node. 713 /// The returned map contains the successor of each arc in the 714 /// graph. 721 715 const EmbeddingMap& embeddingMap() const { 722 716 return _embedding; 723 717 } 724 718 725 /// \brief Give back \c true if the given edge is in the Kuratowski 719 /// \brief Gives back true if the undirected arc is in the 720 /// kuratowski subdivision 721 /// 722 /// Gives back true if the undirected arc is in the kuratowski 726 723 /// subdivision 727 /// 728 /// This function gives back \c true if the given edge is in the found 729 /// Kuratowski subdivision. 730 /// \pre The \c run() function must be called with \c true parameter 731 /// before using this function. 732 bool kuratowski(const Edge& edge) const { 724 /// \note The \c run() had to be called with true value. 725 bool kuratowski(const Edge& edge) { 733 726 return _kuratowski[edge]; 734 727 } … … 2067 2060 /// 2068 2061 /// The planar drawing algorithm calculates positions for the nodes 2069 /// in the plane . These coordinates satisfy that if the edges are2070 /// represented with straight lines ,then they will not intersect2062 /// in the plane which coordinates satisfy that if the arcs are 2063 /// represented with straight lines then they will not intersect 2071 2064 /// each other. 2072 2065 /// 2073 /// Scnyder's algorithm embeds the graph on an \c (n-2)x(n-2) size grid,2074 /// i.e. each node will be located in the \c [0 ..n-2]x[0..n-2] square.2066 /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid, 2067 /// i.e. each node will be located in the \c [0,n-2]x[0,n-2] square. 2075 2068 /// The time complexity of the algorithm is O(n). 2076 ///2077 /// \see PlanarEmbedding2078 2069 template <typename Graph> 2079 2070 class PlanarDrawing { … … 2082 2073 TEMPLATE_GRAPH_TYPEDEFS(Graph); 2083 2074 2084 /// \brief The point type for stor ingcoordinates2075 /// \brief The point type for store coordinates 2085 2076 typedef dim2::Point<int> Point; 2086 /// \brief The map type for stor ing the coordinates of the nodes2077 /// \brief The map type for store coordinates 2087 2078 typedef typename Graph::template NodeMap<Point> PointMap; 2088 2079 … … 2091 2082 /// 2092 2083 /// Constructor 2093 /// \pre The graph must be simple, i.e. it should not 2094 /// contain parallel or loop arcs. 2084 /// \pre The graph should be simple, i.e. loop and parallel arc free. 2095 2085 PlanarDrawing(const Graph& graph) 2096 2086 : _graph(graph), _point_map(graph) {} … … 2377 2367 public: 2378 2368 2379 /// \brief Calculate the node positions2369 /// \brief Calculates the node positions 2380 2370 /// 2381 /// This function calculates the node positions on the plane.2382 /// \return \c true if the graph is planar.2371 /// This function calculates the node positions. 2372 /// \return %True if the graph is planar. 2383 2373 bool run() { 2384 2374 PlanarEmbedding<Graph> pe(_graph); … … 2389 2379 } 2390 2380 2391 /// \brief Calculate the node positions according to a2381 /// \brief Calculates the node positions according to a 2392 2382 /// combinatorical embedding 2393 2383 /// 2394 /// This function calculates the node positions on the plane. 2395 /// The given \c embedding map should contain a valid combinatorical 2396 /// embedding, i.e. a valid cyclic order of the arcs. 2397 /// It can be computed using PlanarEmbedding. 2384 /// This function calculates the node locations. The \c embedding 2385 /// parameter should contain a valid combinatorical embedding, i.e. 2386 /// a valid cyclic order of the arcs. 2398 2387 template <typename EmbeddingMap> 2399 2388 void run(const EmbeddingMap& embedding) { … … 2435 2424 /// \brief The coordinate of the given node 2436 2425 /// 2437 /// Th is function returns the coordinate of the given node.2426 /// The coordinate of the given node. 2438 2427 Point operator[](const Node& node) const { 2439 2428 return _point_map[node]; 2440 2429 } 2441 2430 2442 /// \brief Return the grid embedding in a node map2431 /// \brief Returns the grid embedding in a \e NodeMap. 2443 2432 /// 2444 /// This function returns the grid embedding in a node map of 2445 /// \c dim2::Point<int> coordinates. 2433 /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> . 2446 2434 const PointMap& coords() const { 2447 2435 return _point_map; … … 2483 2471 /// 2484 2472 /// The graph coloring problem is the coloring of the graph nodes 2485 /// so that there are noadjacent nodes with the same color. The2486 /// planar graphs can always be colored with four colors, whichis2487 /// proved by Appel and Haken . Their proofs provide a quadratic2473 /// that there are not adjacent nodes with the same color. The 2474 /// planar graphs can be always colored with four colors, it is 2475 /// proved by Appel and Haken and their proofs provide a quadratic 2488 2476 /// time algorithm for four coloring, but it could not be used to 2489 /// implement anefficient algorithm. The five and six coloring can be2490 /// made in linear time, but in this class ,the five coloring has2477 /// implement efficient algorithm. The five and six coloring can be 2478 /// made in linear time, but in this class the five coloring has 2491 2479 /// quadratic worst case time complexity. The two coloring (if 2492 2480 /// possible) is solvable with a graph search algorithm and it is 2493 2481 /// implemented in \ref bipartitePartitions() function in LEMON. To 2494 /// decide whether a planar graph is three colorable is NP-complete. 2482 /// decide whether the planar graph is three colorable is 2483 /// NP-complete. 2495 2484 /// 2496 2485 /// This class contains member functions for calculate colorings 2497 2486 /// with five and six colors. The six coloring algorithm is a simple 2498 2487 /// greedy coloring on the backward minimum outgoing order of nodes. 2499 /// This order can be computed by selectingthe node with least2500 /// outgoing arcs to unprocessed nodes i n each phase. This order2488 /// This order can be computed as in each phase the node with least 2489 /// outgoing arcs to unprocessed nodes is chosen. This order 2501 2490 /// guarantees that when a node is chosen for coloring it has at 2502 2491 /// most five already colored adjacents. The five coloring algorithm … … 2511 2500 TEMPLATE_GRAPH_TYPEDEFS(Graph); 2512 2501 2513 /// \brief The map type for stor ing color indices2502 /// \brief The map type for store color indexes 2514 2503 typedef typename Graph::template NodeMap<int> IndexMap; 2515 /// \brief The map type for storing colors 2516 /// 2517 /// The map type for storing colors. 2518 /// \see Palette, Color 2504 /// \brief The map type for store colors 2519 2505 typedef ComposeMap<Palette, IndexMap> ColorMap; 2520 2506 2521 2507 /// \brief Constructor 2522 2508 /// 2523 /// Constructor. 2524 /// \pre The graph must be simple, i.e. it should not 2525 /// contain parallel or loop arcs. 2509 /// Constructor 2510 /// \pre The graph should be simple, i.e. loop and parallel arc free. 2526 2511 PlanarColoring(const Graph& graph) 2527 2512 : _graph(graph), _color_map(graph), _palette(0) { … … 2534 2519 } 2535 2520 2536 /// \brief Return the node map of color indices2521 /// \brief Returns the \e NodeMap of color indexes 2537 2522 /// 2538 /// This function returns the node map of color indices. The values are2539 /// in therange \c [0..4] or \c [0..5] according to the coloring method.2523 /// Returns the \e NodeMap of color indexes. The values are in the 2524 /// range \c [0..4] or \c [0..5] according to the coloring method. 2540 2525 IndexMap colorIndexMap() const { 2541 2526 return _color_map; 2542 2527 } 2543 2528 2544 /// \brief Return the node map of colors2529 /// \brief Returns the \e NodeMap of colors 2545 2530 /// 2546 /// This function returns the node map of colors. The values are among2547 /// five or sixdistinct \ref lemon::Color "colors".2531 /// Returns the \e NodeMap of colors. The values are five or six 2532 /// distinct \ref lemon::Color "colors". 2548 2533 ColorMap colorMap() const { 2549 2534 return composeMap(_palette, _color_map); 2550 2535 } 2551 2536 2552 /// \brief Return the color index of the node2537 /// \brief Returns the color index of the node 2553 2538 /// 2554 /// This function returns the color index of the given node. The value is2555 /// in therange \c [0..4] or \c [0..5] according to the coloring method.2539 /// Returns the color index of the node. The values are in the 2540 /// range \c [0..4] or \c [0..5] according to the coloring method. 2556 2541 int colorIndex(const Node& node) const { 2557 2542 return _color_map[node]; 2558 2543 } 2559 2544 2560 /// \brief Return the color of the node2545 /// \brief Returns the color of the node 2561 2546 /// 2562 /// This function returns the color of the given node. The value is among2563 /// five or sixdistinct \ref lemon::Color "colors".2547 /// Returns the color of the node. The values are five or six 2548 /// distinct \ref lemon::Color "colors". 2564 2549 Color color(const Node& node) const { 2565 2550 return _palette[_color_map[node]]; … … 2567 2552 2568 2553 2569 /// \brief Calculate a coloring with at most six colors2554 /// \brief Calculates a coloring with at most six colors 2570 2555 /// 2571 2556 /// This function calculates a coloring with at most six colors. The time 2572 2557 /// complexity of this variant is linear in the size of the graph. 2573 /// \return \c true if the algorithm could color the graph with six colors.2574 /// If the algorithm fails, then the graph is notplanar.2575 /// \note This function can return \ctrue if the graph is not2576 /// planar , but it can be colored with at most sixcolors.2558 /// \return %True when the algorithm could color the graph with six color. 2559 /// If the algorithm fails, then the graph could not be planar. 2560 /// \note This function can return true if the graph is not 2561 /// planar but it can be colored with 6 colors. 2577 2562 bool runSixColoring() { 2578 2563 … … 2676 2661 public: 2677 2662 2678 /// \brief Calculate a coloring with at most five colors2663 /// \brief Calculates a coloring with at most five colors 2679 2664 /// 2680 2665 /// This function calculates a coloring with at most five 2681 2666 /// colors. The worst case time complexity of this variant is 2682 2667 /// quadratic in the size of the graph. 2683 /// \param embedding This map should contain a valid combinatorical2684 /// embedding, i.e. a valid cyclic order of the arcs.2685 /// It can be computed using PlanarEmbedding.2686 2668 template <typename EmbeddingMap> 2687 2669 void runFiveColoring(const EmbeddingMap& embedding) { … … 2730 2712 } 2731 2713 2732 /// \brief Calculate a coloring with at most five colors2714 /// \brief Calculates a coloring with at most five colors 2733 2715 /// 2734 2716 /// This function calculates a coloring with at most five 2735 2717 /// colors. The worst case time complexity of this variant is 2736 2718 /// quadratic in the size of the graph. 2737 /// \return \c true ifthe graph is planar.2719 /// \return %True when the graph is planar. 2738 2720 bool runFiveColoring() { 2739 2721 PlanarEmbedding<Graph> pe(_graph); -
lemon/preflow.h
r891 r835 114 114 /// second phase constructs a feasible maximum flow on each arc. 115 115 /// 116 /// \warning This implementation cannot handle infinite or very large117 /// capacities (e.g. the maximum value of \c CAP::Value).118 ///119 116 /// \tparam GR The type of the digraph the algorithm runs on. 120 117 /// \tparam CAP The type of the capacity map. The default map 121 118 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 122 /// \tparam TR The traits class that defines various types used by the123 /// algorithm. By default, it is \ref PreflowDefaultTraits124 /// "PreflowDefaultTraits<GR, CAP>".125 /// In most cases, this parameter should not be set directly,126 /// consider to use the named template parameters instead.127 119 #ifdef DOXYGEN 128 120 template <typename GR, typename CAP, typename TR> -
scripts/bib2dox.py
r905 r801 1 #! /usr/bin/env python1 #!/usr/bin/env /usr/local/Python/bin/python2.1 2 2 """ 3 3 BibTeX to Doxygen converter 4 4 Usage: python bib2dox.py bibfile.bib > bibfile.dox 5 5 6 This file is a part of LEMON, a generic C++ optimization library.7 8 **********************************************************************9 10 6 This code is the modification of the BibTeX to XML converter 11 by Vidar Bronken Gundersen et al. 12 See the original copyright notices below. 7 by Vidar Bronken Gundersen et al. See the original copyright notices below. 13 8 14 9 ********************************************************************** -
test/bellman_ford_test.cc
r917 r838 105 105 ::SetDistMap<concepts::ReadWriteMap<Node,Value> > 106 106 ::SetOperationTraits<BellmanFordDefaultOperationTraits<Value> > 107 ::SetOperationTraits<BellmanFordToleranceOperationTraits<Value, 0> >108 107 ::Create bf_test(gr,length); 109 108 -
test/min_cost_flow_test.cc
r898 r885 158 158 const MCF& const_mcf = mcf; 159 159 160 b = mcf.reset() .resetParams()160 b = mcf.reset() 161 161 .lowerMap(me.lower) 162 162 .upperMap(me.upper) … … 347 347 checkMcf(mcf1, mcf1.run(param), gr, l2, u, c, s2, 348 348 mcf1.OPTIMAL, true, 8010, test_str + "-4"); 349 mcf1.reset Params().supplyMap(s1);349 mcf1.reset().supplyMap(s1); 350 350 checkMcf(mcf1, mcf1.run(param), gr, l1, cu, cc, s1, 351 351 mcf1.OPTIMAL, true, 74, test_str + "-5"); … … 364 364 365 365 // Tests for the GEQ form 366 mcf1.reset Params().upperMap(u).costMap(c).supplyMap(s5);366 mcf1.reset().upperMap(u).costMap(c).supplyMap(s5); 367 367 checkMcf(mcf1, mcf1.run(param), gr, l1, u, c, s5, 368 368 mcf1.OPTIMAL, true, 3530, test_str + "-10", GEQ); … … 381 381 checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l1, neg1_u2, neg1_c, neg1_s, 382 382 mcf2.OPTIMAL, true, -40000, test_str + "-14"); 383 mcf2.reset Params().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s);383 mcf2.reset().lowerMap(neg1_l2).costMap(neg1_c).supplyMap(neg1_s); 384 384 checkMcf(mcf2, mcf2.run(param), neg1_gr, neg1_l2, neg1_u1, neg1_c, neg1_s, 385 385 mcf2.UNBOUNDED, false, 0, test_str + "-15"); -
tools/dimacs-solver.cc
r919 r691 92 92 } 93 93 94 template<class Value , class LargeValue>94 template<class Value> 95 95 void solve_min(ArgParser &ap, std::istream &is, std::ostream &, 96 96 Value infty, DimacsDescriptor &desc) … … 128 128 std::cerr << "Run NetworkSimplex: " << ti << "\n\n"; 129 129 std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n'; 130 if (res) std::cerr << "Min flow cost: " 131 << ns.template totalCost<LargeValue>() << '\n'; 130 if (res) std::cerr << "Min flow cost: " << ns.totalCost() << '\n'; 132 131 } 133 132 } … … 153 152 154 153 155 template<class Value , class LargeValue>154 template<class Value> 156 155 void solve(ArgParser &ap, std::istream &is, std::ostream &os, 157 156 DimacsDescriptor &desc) … … 171 170 { 172 171 case DimacsDescriptor::MIN: 173 solve_min<Value , LargeValue>(ap,is,os,infty,desc);172 solve_min<Value>(ap,is,os,infty,desc); 174 173 break; 175 174 case DimacsDescriptor::MAX: … … 266 265 267 266 if(ap.given("double")) 268 solve<double , double>(ap,is,os,desc);267 solve<double>(ap,is,os,desc); 269 268 else if(ap.given("ldouble")) 270 solve<long double , long double>(ap,is,os,desc);269 solve<long double>(ap,is,os,desc); 271 270 #ifdef LEMON_HAVE_LONG_LONG 272 271 else if(ap.given("long")) 273 solve<long long, long long>(ap,is,os,desc); 274 else solve<int, long long>(ap,is,os,desc); 275 #else 276 else solve<int, long>(ap,is,os,desc); 272 solve<long long>(ap,is,os,desc); 277 273 #endif 274 else solve<int>(ap,is,os,desc); 278 275 279 276 return 0;
Note: See TracChangeset
for help on using the changeset viewer.