Changeset 1107:2b6bffe0e7e8 in lemon for lemon
- Timestamp:
- 12/20/11 18:15:14 (12 years ago)
- Branch:
- default
- Parents:
- 1106:7c4ba7daaf5f (diff), 1057:633956ca9421 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent. - Phase:
- public
- Location:
- lemon
- Files:
-
- 19 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/Makefile.am
r953 r1107 1 1 EXTRA_DIST += \ 2 2 lemon/lemon.pc.in \ 3 lemon/lemon.pc.cmake \ 3 4 lemon/CMakeLists.txt \ 4 5 lemon/config.h.cmake -
lemon/Makefile.am
r1106 r1107 59 59 lemon/arg_parser.h \ 60 60 lemon/assert.h \ 61 lemon/bellman_ford.h \ 61 62 lemon/bfs.h \ 62 63 lemon/bin_heap.h \ 64 lemon/binomial_heap.h \ 63 65 lemon/bucket_heap.h \ 66 lemon/capacity_scaling.h \ 64 67 lemon/cbc.h \ 65 68 lemon/circulation.h \ … … 68 71 lemon/concept_check.h \ 69 72 lemon/connectivity.h \ 73 lemon/core.h \ 74 lemon/cost_scaling.h \ 70 75 lemon/counter.h \ 71 lemon/core.h \72 76 lemon/cplex.h \ 77 lemon/cycle_canceling.h \ 73 78 lemon/dfs.h \ 79 lemon/dheap.h \ 74 80 lemon/dijkstra.h \ 75 81 lemon/dim2.h \ … … 80 86 lemon/euler.h \ 81 87 lemon/fib_heap.h \ 88 lemon/fractional_matching.h \ 82 89 lemon/full_graph.h \ 83 90 lemon/glpk.h \ … … 85 92 lemon/graph_to_eps.h \ 86 93 lemon/grid_graph.h \ 94 lemon/hartmann_orlin_mmc.h \ 95 lemon/howard_mmc.h \ 87 96 lemon/hypercube_graph.h \ 97 lemon/karp_mmc.h \ 88 98 lemon/kruskal.h \ 89 99 lemon/hao_orlin.h \ … … 100 110 lemon/nauty_reader.h \ 101 111 lemon/network_simplex.h \ 112 lemon/pairing_heap.h \ 102 113 lemon/path.h \ 114 lemon/planarity.h \ 103 115 lemon/preflow.h \ 116 lemon/quad_heap.h \ 104 117 lemon/radix_heap.h \ 105 118 lemon/radix_sort.h \ … … 107 120 lemon/smart_graph.h \ 108 121 lemon/soplex.h \ 122 lemon/static_graph.h \ 109 123 lemon/suurballe.h \ 110 124 lemon/time_measure.h \ -
lemon/bits/edge_set_extender.h
r956 r1107 281 281 typedef EdgeSetExtender Graph; 282 282 283 typedef True UndirectedTag; 284 283 285 typedef typename Parent::Node Node; 284 286 typedef typename Parent::Arc Arc; -
lemon/bits/edge_set_extender.h
r967 r1107 1 /* -*- C++-*-1 /* -*- mode: C++; indent-tabs-mode: nil; -*- 2 2 * 3 * This file is a part of LEMON, a generic C++ optimization library 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 64 64 Node oppositeNode(const Node &n, const Arc &e) const { 65 65 if (n == Parent::source(e)) 66 66 return Parent::target(e); 67 67 else if(n==Parent::target(e)) 68 68 return Parent::source(e); 69 69 else 70 70 return INVALID; 71 71 } 72 72 … … 92 92 // Iterable extensions 93 93 94 class NodeIt : public Node { 94 class NodeIt : public Node { 95 95 const Digraph* digraph; 96 96 public: … … 101 101 102 102 explicit NodeIt(const Digraph& _graph) : digraph(&_graph) { 103 104 } 105 106 NodeIt(const Digraph& _graph, const Node& node) 107 108 109 NodeIt& operator++() { 110 111 return *this; 112 } 113 114 }; 115 116 117 class ArcIt : public Arc { 103 _graph.first(static_cast<Node&>(*this)); 104 } 105 106 NodeIt(const Digraph& _graph, const Node& node) 107 : Node(node), digraph(&_graph) {} 108 109 NodeIt& operator++() { 110 digraph->next(*this); 111 return *this; 112 } 113 114 }; 115 116 117 class ArcIt : public Arc { 118 118 const Digraph* digraph; 119 119 public: … … 124 124 125 125 explicit ArcIt(const Digraph& _graph) : digraph(&_graph) { 126 127 } 128 129 ArcIt(const Digraph& _graph, const Arc& e) : 130 131 132 ArcIt& operator++() { 133 134 return *this; 135 } 136 137 }; 138 139 140 class OutArcIt : public Arc { 126 _graph.first(static_cast<Arc&>(*this)); 127 } 128 129 ArcIt(const Digraph& _graph, const Arc& e) : 130 Arc(e), digraph(&_graph) { } 131 132 ArcIt& operator++() { 133 digraph->next(*this); 134 return *this; 135 } 136 137 }; 138 139 140 class OutArcIt : public Arc { 141 141 const Digraph* digraph; 142 142 public: … … 146 146 OutArcIt(Invalid i) : Arc(i) { } 147 147 148 OutArcIt(const Digraph& _graph, const Node& node) 149 150 151 } 152 153 OutArcIt(const Digraph& _graph, const Arc& arc) 154 155 156 OutArcIt& operator++() { 157 158 return *this; 159 } 160 161 }; 162 163 164 class InArcIt : public Arc { 148 OutArcIt(const Digraph& _graph, const Node& node) 149 : digraph(&_graph) { 150 _graph.firstOut(*this, node); 151 } 152 153 OutArcIt(const Digraph& _graph, const Arc& arc) 154 : Arc(arc), digraph(&_graph) {} 155 156 OutArcIt& operator++() { 157 digraph->nextOut(*this); 158 return *this; 159 } 160 161 }; 162 163 164 class InArcIt : public Arc { 165 165 const Digraph* digraph; 166 166 public: … … 170 170 InArcIt(Invalid i) : Arc(i) { } 171 171 172 InArcIt(const Digraph& _graph, const Node& node) 173 174 175 } 176 177 InArcIt(const Digraph& _graph, const Arc& arc) : 178 179 180 InArcIt& operator++() { 181 182 return *this; 172 InArcIt(const Digraph& _graph, const Node& node) 173 : digraph(&_graph) { 174 _graph.firstIn(*this, node); 175 } 176 177 InArcIt(const Digraph& _graph, const Arc& arc) : 178 Arc(arc), digraph(&_graph) {} 179 180 InArcIt& operator++() { 181 digraph->nextIn(*this); 182 return *this; 183 183 } 184 184 … … 216 216 217 217 // Mappable extension 218 218 219 219 template <typename _Value> 220 class ArcMap 220 class ArcMap 221 221 : public MapExtender<DefaultMap<Digraph, Arc, _Value> > { 222 222 typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent; 223 223 224 224 public: 225 explicit ArcMap(const Digraph& _g) 226 227 ArcMap(const Digraph& _g, const _Value& _v) 228 225 explicit ArcMap(const Digraph& _g) 226 : Parent(_g) {} 227 ArcMap(const Digraph& _g, const _Value& _v) 228 : Parent(_g, _v) {} 229 229 230 230 ArcMap& operator=(const ArcMap& cmap) { 231 231 return operator=<ArcMap>(cmap); 232 232 } 233 233 … … 235 235 ArcMap& operator=(const CMap& cmap) { 236 236 Parent::operator=(cmap); 237 237 return *this; 238 238 } 239 239 … … 248 248 return arc; 249 249 } 250 250 251 251 void clear() { 252 252 notifier(Arc()).clear(); … … 313 313 Node oppositeNode(const Node &n, const Edge &e) const { 314 314 if( n == Parent::u(e)) 315 315 return Parent::v(e); 316 316 else if( n == Parent::v(e)) 317 317 return Parent::u(e); 318 318 else 319 319 return INVALID; 320 320 } 321 321 … … 341 341 342 342 using Parent::notifier; 343 343 344 344 ArcNotifier& notifier(Arc) const { 345 345 return arc_notifier; … … 351 351 352 352 353 class NodeIt : public Node { 353 class NodeIt : public Node { 354 354 const Graph* graph; 355 355 public: … … 360 360 361 361 explicit NodeIt(const Graph& _graph) : graph(&_graph) { 362 363 } 364 365 NodeIt(const Graph& _graph, const Node& node) 366 367 368 NodeIt& operator++() { 369 370 return *this; 371 } 372 373 }; 374 375 376 class ArcIt : public Arc { 362 _graph.first(static_cast<Node&>(*this)); 363 } 364 365 NodeIt(const Graph& _graph, const Node& node) 366 : Node(node), graph(&_graph) {} 367 368 NodeIt& operator++() { 369 graph->next(*this); 370 return *this; 371 } 372 373 }; 374 375 376 class ArcIt : public Arc { 377 377 const Graph* graph; 378 378 public: … … 383 383 384 384 explicit ArcIt(const Graph& _graph) : graph(&_graph) { 385 386 } 387 388 ArcIt(const Graph& _graph, const Arc& e) : 389 390 391 ArcIt& operator++() { 392 393 return *this; 394 } 395 396 }; 397 398 399 class OutArcIt : public Arc { 385 _graph.first(static_cast<Arc&>(*this)); 386 } 387 388 ArcIt(const Graph& _graph, const Arc& e) : 389 Arc(e), graph(&_graph) { } 390 391 ArcIt& operator++() { 392 graph->next(*this); 393 return *this; 394 } 395 396 }; 397 398 399 class OutArcIt : public Arc { 400 400 const Graph* graph; 401 401 public: … … 405 405 OutArcIt(Invalid i) : Arc(i) { } 406 406 407 OutArcIt(const Graph& _graph, const Node& node) 408 409 410 } 411 412 OutArcIt(const Graph& _graph, const Arc& arc) 413 414 415 OutArcIt& operator++() { 416 417 return *this; 418 } 419 420 }; 421 422 423 class InArcIt : public Arc { 407 OutArcIt(const Graph& _graph, const Node& node) 408 : graph(&_graph) { 409 _graph.firstOut(*this, node); 410 } 411 412 OutArcIt(const Graph& _graph, const Arc& arc) 413 : Arc(arc), graph(&_graph) {} 414 415 OutArcIt& operator++() { 416 graph->nextOut(*this); 417 return *this; 418 } 419 420 }; 421 422 423 class InArcIt : public Arc { 424 424 const Graph* graph; 425 425 public: … … 429 429 InArcIt(Invalid i) : Arc(i) { } 430 430 431 InArcIt(const Graph& _graph, const Node& node) 432 433 434 } 435 436 InArcIt(const Graph& _graph, const Arc& arc) : 437 438 439 InArcIt& operator++() { 440 441 return *this; 442 } 443 444 }; 445 446 447 class EdgeIt : public Parent::Edge { 431 InArcIt(const Graph& _graph, const Node& node) 432 : graph(&_graph) { 433 _graph.firstIn(*this, node); 434 } 435 436 InArcIt(const Graph& _graph, const Arc& arc) : 437 Arc(arc), graph(&_graph) {} 438 439 InArcIt& operator++() { 440 graph->nextIn(*this); 441 return *this; 442 } 443 444 }; 445 446 447 class EdgeIt : public Parent::Edge { 448 448 const Graph* graph; 449 449 public: … … 454 454 455 455 explicit EdgeIt(const Graph& _graph) : graph(&_graph) { 456 457 } 458 459 EdgeIt(const Graph& _graph, const Edge& e) : 460 461 462 EdgeIt& operator++() { 463 464 return *this; 456 _graph.first(static_cast<Edge&>(*this)); 457 } 458 459 EdgeIt(const Graph& _graph, const Edge& e) : 460 Edge(e), graph(&_graph) { } 461 462 EdgeIt& operator++() { 463 graph->next(*this); 464 return *this; 465 465 } 466 466 … … 478 478 479 479 IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) { 480 480 _graph.firstInc(*this, direction, n); 481 481 } 482 482 483 483 IncEdgeIt(const Graph& _graph, const Edge &ue, const Node &n) 484 485 484 : graph(&_graph), Edge(ue) { 485 direction = (_graph.source(ue) == n); 486 486 } 487 487 488 488 IncEdgeIt& operator++() { 489 490 return *this; 489 graph->nextInc(*this, direction); 490 return *this; 491 491 } 492 492 }; … … 535 535 536 536 template <typename _Value> 537 class ArcMap 537 class ArcMap 538 538 : public MapExtender<DefaultMap<Graph, Arc, _Value> > { 539 539 typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent; 540 540 541 541 public: 542 explicit ArcMap(const Graph& _g) 543 544 ArcMap(const Graph& _g, const _Value& _v) 545 542 explicit ArcMap(const Graph& _g) 543 : Parent(_g) {} 544 ArcMap(const Graph& _g, const _Value& _v) 545 : Parent(_g, _v) {} 546 546 547 547 ArcMap& operator=(const ArcMap& cmap) { 548 548 return operator=<ArcMap>(cmap); 549 549 } 550 550 … … 552 552 ArcMap& operator=(const CMap& cmap) { 553 553 Parent::operator=(cmap); 554 554 return *this; 555 555 } 556 556 … … 559 559 560 560 template <typename _Value> 561 class EdgeMap 561 class EdgeMap 562 562 : public MapExtender<DefaultMap<Graph, Edge, _Value> > { 563 563 typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent; 564 564 565 565 public: 566 explicit EdgeMap(const Graph& _g) 567 568 569 EdgeMap(const Graph& _g, const _Value& _v) 570 566 explicit EdgeMap(const Graph& _g) 567 : Parent(_g) {} 568 569 EdgeMap(const Graph& _g, const _Value& _v) 570 : Parent(_g, _v) {} 571 571 572 572 EdgeMap& operator=(const EdgeMap& cmap) { 573 573 return operator=<EdgeMap>(cmap); 574 574 } 575 575 … … 577 577 EdgeMap& operator=(const CMap& cmap) { 578 578 Parent::operator=(cmap); 579 579 return *this; 580 580 } 581 581 … … 594 594 return edge; 595 595 } 596 596 597 597 void clear() { 598 598 notifier(Arc()).clear(); … … 620 620 arc_notifier.clear(); 621 621 } 622 622 623 623 }; 624 624 -
lemon/bits/windows.cc
r956 r1055 41 41 #include <unistd.h> 42 42 #include <ctime> 43 #ifndef WIN32 43 44 #include <sys/times.h> 45 #endif 44 46 #include <sys/time.h> 45 47 #endif -
lemon/bits/windows.cc
r1053 r1055 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 99 99 GetSystemTime(&time); 100 100 char buf1[11], buf2[9], buf3[5]; 101 101 if (GetDateFormat(MY_LOCALE, 0, &time, 102 102 ("ddd MMM dd"), buf1, 11) && 103 103 GetTimeFormat(MY_LOCALE, 0, &time, -
lemon/core.h
r956 r1107 395 395 static void copy(const From& from, Digraph &to, 396 396 NodeRefMap& nodeRefMap, ArcRefMap& arcRefMap) { 397 to.clear(); 397 398 for (typename From::NodeIt it(from); it != INVALID; ++it) { 398 399 nodeRefMap[it] = to.addNode(); … … 422 423 static void copy(const From& from, Graph &to, 423 424 NodeRefMap& nodeRefMap, EdgeRefMap& edgeRefMap) { 425 to.clear(); 424 426 for (typename From::NodeIt it(from); it != INVALID; ++it) { 425 427 nodeRefMap[it] = to.addNode(); -
lemon/core.h
r984 r1107 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 1242 1242 protected: 1243 1243 1244 class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type { 1244 class AutoNodeMap : public ItemSetTraits<GR, Node>::template Map<Arc>::Type 1245 { 1245 1246 typedef typename ItemSetTraits<GR, Node>::template Map<Arc>::Type Parent; 1246 1247 … … 1281 1282 }; 1282 1283 1283 protected: 1284 protected: 1284 1285 1285 1286 const Digraph &_g; -
lemon/dfs.h
r956 r1107 566 566 void start(Node t) 567 567 { 568 while ( !emptyQueue() && G->target(_stack[_stack_head])!=t)568 while ( !emptyQueue() && !(*_reached)[t] ) 569 569 processNextArc(); 570 570 } … … 1513 1513 /// with addSource() before using this function. 1514 1514 void start(Node t) { 1515 while ( !emptyQueue() && _digraph->target(_stack[_stack_head]) != t)1515 while ( !emptyQueue() && !(*_reached)[t] ) 1516 1516 processNextArc(); 1517 1517 } -
lemon/dfs.h
r1009 r1107 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 48 48 ///The type of the map that stores the predecessor 49 49 ///arcs of the %DFS paths. 50 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.50 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 51 51 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 52 52 ///Instantiates a \c PredMap. … … 63 63 64 64 ///The type of the map that indicates which nodes are processed. 65 ///It must meet the \ref concepts::WriteMap "WriteMap" concept. 65 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 66 ///By default, it is a NullMap. 66 67 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 67 68 ///Instantiates a \c ProcessedMap. … … 82 83 83 84 ///The type of the map that indicates which nodes are reached. 84 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 ///It must conform to 86 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 85 87 typedef typename Digraph::template NodeMap<bool> ReachedMap; 86 88 ///Instantiates a \c ReachedMap. … … 97 99 98 100 ///The type of the map that stores the distances of the nodes. 99 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.101 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 100 102 typedef typename Digraph::template NodeMap<int> DistMap; 101 103 ///Instantiates a \c DistMap. … … 121 123 ///\tparam GR The type of the digraph the algorithm runs on. 122 124 ///The default type is \ref ListDigraph. 125 ///\tparam TR The traits class that defines various types used by the 126 ///algorithm. By default, it is \ref DfsDefaultTraits 127 ///"DfsDefaultTraits<GR>". 128 ///In most cases, this parameter should not be set directly, 129 ///consider to use the named template parameters instead. 123 130 #ifdef DOXYGEN 124 131 template <typename GR, … … 225 232 ///\ref named-templ-param "Named parameter" for setting 226 233 ///\c PredMap type. 227 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.234 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 228 235 template <class T> 229 236 struct SetPredMap : public Dfs<Digraph, SetPredMapTraits<T> > { … … 245 252 ///\ref named-templ-param "Named parameter" for setting 246 253 ///\c DistMap type. 247 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.254 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 248 255 template <class T> 249 256 struct SetDistMap : public Dfs< Digraph, SetDistMapTraits<T> > { … … 265 272 ///\ref named-templ-param "Named parameter" for setting 266 273 ///\c ReachedMap type. 267 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 274 ///It must conform to 275 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 268 276 template <class T> 269 277 struct SetReachedMap : public Dfs< Digraph, SetReachedMapTraits<T> > { … … 285 293 ///\ref named-templ-param "Named parameter" for setting 286 294 ///\c ProcessedMap type. 287 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.295 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 288 296 template <class T> 289 297 struct SetProcessedMap : public Dfs< Digraph, SetProcessedMapTraits<T> > { … … 412 420 ///The simplest way to execute the DFS algorithm is to use one of the 413 421 ///member functions called \ref run(Node) "run()".\n 414 ///If you need more control on the execution, firstyou have to call415 ///\ref init() , then you can add a source node with \ref addSource()422 ///If you need better control on the execution, you have to call 423 ///\ref init() first, then you can add a source node with \ref addSource() 416 424 ///and perform the actual computation with \ref start(). 417 425 ///This procedure can be repeated if there are nodes that have not … … 633 641 ///Runs the algorithm to visit all nodes in the digraph. 634 642 635 ///This method runs the %DFS algorithm in order to compute the 636 ///%DFS path to each node. 637 /// 638 ///The algorithm computes 639 ///- the %DFS tree (forest), 640 ///- the distance of each node from the root(s) in the %DFS tree. 643 ///This method runs the %DFS algorithm in order to visit all nodes 644 ///in the digraph. 641 645 /// 642 646 ///\note <tt>d.run()</tt> is just a shortcut of the following code. … … 670 674 ///@{ 671 675 672 ///The DFS path to anode.673 674 ///Returns the DFS path to a node.676 ///The DFS path to the given node. 677 678 ///Returns the DFS path to the given node from the root(s). 675 679 /// 676 680 ///\warning \c t should be reached from the root(s). … … 680 684 Path path(Node t) const { return Path(*G, *_pred, t); } 681 685 682 ///The distance of anode from the root(s).683 684 ///Returns the distance of anode from the root(s).686 ///The distance of the given node from the root(s). 687 688 ///Returns the distance of the given node from the root(s). 685 689 /// 686 690 ///\warning If node \c v is not reached from the root(s), then … … 691 695 int dist(Node v) const { return (*_dist)[v]; } 692 696 693 ///Returns the 'previous arc' of the %DFS tree for anode.697 ///Returns the 'previous arc' of the %DFS tree for the given node. 694 698 695 699 ///This function returns the 'previous arc' of the %DFS tree for the … … 699 703 /// 700 704 ///The %DFS tree used here is equal to the %DFS tree used in 701 ///\ref predNode() .705 ///\ref predNode() and \ref predMap(). 702 706 /// 703 707 ///\pre Either \ref run(Node) "run()" or \ref init() … … 705 709 Arc predArc(Node v) const { return (*_pred)[v];} 706 710 707 ///Returns the 'previous node' of the %DFS tree .711 ///Returns the 'previous node' of the %DFS tree for the given node. 708 712 709 713 ///This function returns the 'previous node' of the %DFS 710 714 ///tree for the node \c v, i.e. it returns the last but one node 711 /// froma %DFS path from a root to \c v. It is \c INVALID715 ///of a %DFS path from a root to \c v. It is \c INVALID 712 716 ///if \c v is not reached from the root(s) or if \c v is a root. 713 717 /// 714 718 ///The %DFS tree used here is equal to the %DFS tree used in 715 ///\ref predArc() .719 ///\ref predArc() and \ref predMap(). 716 720 /// 717 721 ///\pre Either \ref run(Node) "run()" or \ref init() … … 734 738 /// 735 739 ///Returns a const reference to the node map that stores the predecessor 736 ///arcs, which form the DFS tree .740 ///arcs, which form the DFS tree (forest). 737 741 /// 738 742 ///\pre Either \ref run(Node) "run()" or \ref init() … … 740 744 const PredMap &predMap() const { return *_pred;} 741 745 742 ///Checks if anode is reached from the root(s).746 ///Checks if the given node. node is reached from the root(s). 743 747 744 748 ///Returns \c true if \c v is reached from the root(s). … … 766 770 ///The type of the map that stores the predecessor 767 771 ///arcs of the %DFS paths. 768 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.772 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 769 773 typedef typename Digraph::template NodeMap<typename Digraph::Arc> PredMap; 770 774 ///Instantiates a PredMap. … … 781 785 782 786 ///The type of the map that indicates which nodes are processed. 783 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.784 ///By default it is a NullMap.787 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 788 ///By default, it is a NullMap. 785 789 typedef NullMap<typename Digraph::Node,bool> ProcessedMap; 786 790 ///Instantiates a ProcessedMap. … … 801 805 802 806 ///The type of the map that indicates which nodes are reached. 803 ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 807 ///It must conform to 808 ///the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 804 809 typedef typename Digraph::template NodeMap<bool> ReachedMap; 805 810 ///Instantiates a ReachedMap. … … 816 821 817 822 ///The type of the map that stores the distances of the nodes. 818 ///It must meetthe \ref concepts::WriteMap "WriteMap" concept.823 ///It must conform to the \ref concepts::WriteMap "WriteMap" concept. 819 824 typedef typename Digraph::template NodeMap<int> DistMap; 820 825 ///Instantiates a DistMap. … … 831 836 832 837 ///The type of the DFS paths. 833 ///It must meetthe \ref concepts::Path "Path" concept.838 ///It must conform to the \ref concepts::Path "Path" concept. 834 839 typedef lemon::Path<Digraph> Path; 835 840 }; … … 837 842 /// Default traits class used by DfsWizard 838 843 839 /// To make it easier to use Dfs algorithm 840 /// we have created a wizard class. 841 /// This \ref DfsWizard class needs default traits, 842 /// as well as the \ref Dfs class. 843 /// The \ref DfsWizardBase is a class to be the default traits of the 844 /// \ref DfsWizard class. 844 /// Default traits class used by DfsWizard. 845 /// \tparam GR The type of the digraph. 845 846 template<class GR> 846 847 class DfsWizardBase : public DfsWizardDefaultTraits<GR> … … 870 871 /// Constructor. 871 872 872 /// This constructor does not require parameters, thereforeit initiates873 /// This constructor does not require parameters, it initiates 873 874 /// all of the attributes to \c 0. 874 875 DfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0), … … 895 896 /// This class should only be used through the \ref dfs() function, 896 897 /// which makes it easier to use the algorithm. 898 /// 899 /// \tparam TR The traits class that defines various types used by the 900 /// algorithm. 897 901 template<class TR> 898 902 class DfsWizard : public TR … … 900 904 typedef TR Base; 901 905 902 ///The type of the digraph the algorithm runs on.903 906 typedef typename TR::Digraph Digraph; 904 907 … … 908 911 typedef typename Digraph::OutArcIt OutArcIt; 909 912 910 ///\brief The type of the map that stores the predecessor911 ///arcs of the DFS paths.912 913 typedef typename TR::PredMap PredMap; 913 ///\brief The type of the map that stores the distances of the nodes.914 914 typedef typename TR::DistMap DistMap; 915 ///\brief The type of the map that indicates which nodes are reached.916 915 typedef typename TR::ReachedMap ReachedMap; 917 ///\brief The type of the map that indicates which nodes are processed.918 916 typedef typename TR::ProcessedMap ProcessedMap; 919 ///The type of the DFS paths920 917 typedef typename TR::Path Path; 921 918 … … 987 984 ///Runs DFS algorithm to visit all nodes in the digraph. 988 985 989 ///This method runs DFS algorithm in order to compute990 /// the DFS path to each node.986 ///This method runs DFS algorithm in order to visit all nodes 987 ///in the digraph. 991 988 void run() 992 989 { … … 1000 997 SetPredMapBase(const TR &b) : TR(b) {} 1001 998 }; 1002 ///\brief \ref named-func-param "Named parameter" 1003 ///for setting PredMap object. 1004 /// 1005 ///\ref named-func-param "Named parameter" 1006 ///for setting PredMap object. 999 1000 ///\brief \ref named-templ-param "Named parameter" for setting 1001 ///the predecessor map. 1002 /// 1003 ///\ref named-templ-param "Named parameter" function for setting 1004 ///the map that stores the predecessor arcs of the nodes. 1007 1005 template<class T> 1008 1006 DfsWizard<SetPredMapBase<T> > predMap(const T &t) … … 1018 1016 SetReachedMapBase(const TR &b) : TR(b) {} 1019 1017 }; 1020 ///\brief \ref named-func-param "Named parameter" 1021 ///for setting ReachedMap object. 1022 /// 1023 /// \ref named-func-param "Named parameter" 1024 ///for setting ReachedMap object. 1018 1019 ///\brief \ref named-templ-param "Named parameter" for setting 1020 ///the reached map. 1021 /// 1022 ///\ref named-templ-param "Named parameter" function for setting 1023 ///the map that indicates which nodes are reached. 1025 1024 template<class T> 1026 1025 DfsWizard<SetReachedMapBase<T> > reachedMap(const T &t) … … 1036 1035 SetDistMapBase(const TR &b) : TR(b) {} 1037 1036 }; 1038 ///\brief \ref named-func-param "Named parameter" 1039 ///for setting DistMap object. 1040 /// 1041 /// \ref named-func-param "Named parameter" 1042 ///for setting DistMap object. 1037 1038 ///\brief \ref named-templ-param "Named parameter" for setting 1039 ///the distance map. 1040 /// 1041 ///\ref named-templ-param "Named parameter" function for setting 1042 ///the map that stores the distances of the nodes calculated 1043 ///by the algorithm. 1043 1044 template<class T> 1044 1045 DfsWizard<SetDistMapBase<T> > distMap(const T &t) … … 1054 1055 SetProcessedMapBase(const TR &b) : TR(b) {} 1055 1056 }; 1056 ///\brief \ref named-func-param "Named parameter" 1057 ///for setting ProcessedMap object. 1058 /// 1059 /// \ref named-func-param "Named parameter" 1060 ///for setting ProcessedMap object. 1057 1058 ///\brief \ref named-func-param "Named parameter" for setting 1059 ///the processed map. 1060 /// 1061 ///\ref named-templ-param "Named parameter" function for setting 1062 ///the map that indicates which nodes are processed. 1061 1063 template<class T> 1062 1064 DfsWizard<SetProcessedMapBase<T> > processedMap(const T &t) … … 1209 1211 /// 1210 1212 /// The type of the map that indicates which nodes are reached. 1211 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1213 /// It must conform to the 1214 /// \ref concepts::ReadWriteMap "ReadWriteMap" concept. 1212 1215 typedef typename Digraph::template NodeMap<bool> ReachedMap; 1213 1216 … … 1247 1250 /// does not observe the DFS events. If you want to observe the DFS 1248 1251 /// events, you should implement your own visitor class. 1249 /// \tparam TR T raits class to set various datatypes used by the1250 /// algorithm. The default traits class is1251 /// \ref DfsVisitDefaultTraits"DfsVisitDefaultTraits<GR>".1252 /// See \ref DfsVisitDefaultTraits for the documentation of1253 /// a DFS visit traits class.1252 /// \tparam TR The traits class that defines various types used by the 1253 /// algorithm. By default, it is \ref DfsVisitDefaultTraits 1254 /// "DfsVisitDefaultTraits<GR>". 1255 /// In most cases, this parameter should not be set directly, 1256 /// consider to use the named template parameters instead. 1254 1257 #ifdef DOXYGEN 1255 1258 template <typename GR, typename VS, typename TR> … … 1370 1373 /// The simplest way to execute the DFS algorithm is to use one of the 1371 1374 /// member functions called \ref run(Node) "run()".\n 1372 /// If you need more control on the execution, firstyou have to call1373 /// \ref init() , then you can add a source node with \ref addSource()1375 /// If you need better control on the execution, you have to call 1376 /// \ref init() first, then you can add a source node with \ref addSource() 1374 1377 /// and perform the actual computation with \ref start(). 1375 1378 /// This procedure can be repeated if there are nodes that have not … … 1584 1587 /// \brief Runs the algorithm to visit all nodes in the digraph. 1585 1588 1586 /// This method runs the %DFS algorithm in order to 1587 /// compute the %DFS path to each node. 1588 /// 1589 /// The algorithm computes 1590 /// - the %DFS tree (forest), 1591 /// - the distance of each node from the root(s) in the %DFS tree. 1589 /// This method runs the %DFS algorithm in order to visit all nodes 1590 /// in the digraph. 1592 1591 /// 1593 1592 /// \note <tt>d.run()</tt> is just a shortcut of the following code. … … 1621 1620 ///@{ 1622 1621 1623 /// \brief Checks if anode is reached from the root(s).1622 /// \brief Checks if the given node is reached from the root(s). 1624 1623 /// 1625 1624 /// Returns \c true if \c v is reached from the root(s). -
lemon/graph_to_eps.h
r908 r1107 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 143 143 ///\param gr Reference to the graph to be printed. 144 144 ///\param ost Reference to the output stream. 145 ///By default it is <tt>std::cout</tt>.145 ///By default, it is <tt>std::cout</tt>. 146 146 ///\param pros If it is \c true, then the \c ostream referenced by \c os 147 147 ///will be explicitly deallocated by the destructor. … … 513 513 ///Turn on/off pre-scaling 514 514 515 ///By default graphToEps() rescales the whole image in order to avoid515 ///By default, graphToEps() rescales the whole image in order to avoid 516 516 ///very big or very small bounding boxes. 517 517 /// … … 1115 1115 ///\param g Reference to the graph to be printed. 1116 1116 ///\param os Reference to the output stream. 1117 ///By default it is <tt>std::cout</tt>.1117 ///By default, it is <tt>std::cout</tt>. 1118 1118 /// 1119 1119 ///This function also has a lot of … … 1127 1127 ///\endcode 1128 1128 /// 1129 ///For more detailed examples see the \ref graph_to_eps_demo.cc demo file.1129 ///For more detailed examples, see the \ref graph_to_eps_demo.cc demo file. 1130 1130 /// 1131 1131 ///\warning Don't forget to put the \ref GraphToEps::run() "run()" -
lemon/lgf_reader.h
r956 r1107 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-201 05 * Copyright (C) 2003-2011 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 965 965 int index = 0; 966 966 while (_reader_bits::readToken(line, map)) { 967 if(map == "-") { 968 if(index!=0) 969 throw FormatError("'-' is not allowed as a map name"); 970 else if (line >> std::ws >> c) 971 throw FormatError("Extra character at the end of line"); 972 else break; 973 } 967 974 if (maps.find(map) != maps.end()) { 968 975 std::ostringstream msg; … … 1835 1842 int index = 0; 1836 1843 while (_reader_bits::readToken(line, map)) { 1844 if(map == "-") { 1845 if(index!=0) 1846 throw FormatError("'-' is not allowed as a map name"); 1847 else if (line >> std::ws >> c) 1848 throw FormatError("Extra character at the end of line"); 1849 else break; 1850 } 1837 1851 if (maps.find(map) != maps.end()) { 1838 1852 std::ostringstream msg; -
lemon/lgf_reader.h
r1069 r1107 428 428 ///\endcode 429 429 /// 430 /// By default the reader uses the first section in the file of the430 /// By default, the reader uses the first section in the file of the 431 431 /// proper type. If a section has an optional name, then it can be 432 432 /// selected for reading by giving an optional name parameter to the … … 563 563 friend DigraphReader<TDGR> digraphReader(TDGR& digraph, std::istream& is); 564 564 template <typename TDGR> 565 friend DigraphReader<TDGR> digraphReader(TDGR& digraph, 565 friend DigraphReader<TDGR> digraphReader(TDGR& digraph, 566 566 const std::string& fn); 567 567 template <typename TDGR> … … 1195 1195 1196 1196 }; 1197 1197 1198 1198 /// \ingroup lemon_io 1199 1199 /// … … 1202 1202 /// This function just returns a \ref DigraphReader class. 1203 1203 /// 1204 /// With this function a digraph can be read from an 1204 /// With this function a digraph can be read from an 1205 1205 /// \ref lgf-format "LGF" file or input stream with several maps and 1206 1206 /// attributes. For example, there is network flow problem on a … … 1257 1257 template <typename GR> 1258 1258 class GraphReader; 1259 1259 1260 1260 template <typename TGR> 1261 1261 GraphReader<TGR> graphReader(TGR& graph, std::istream& is = std::cin); … … 1394 1394 friend GraphReader<TGR> graphReader(TGR& graph, std::istream& is); 1395 1395 template <typename TGR> 1396 friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn); 1396 friend GraphReader<TGR> graphReader(TGR& graph, const std::string& fn); 1397 1397 template <typename TGR> 1398 1398 friend GraphReader<TGR> graphReader(TGR& graph, const char *fn); … … 2078 2078 /// \brief Return a \ref GraphReader class 2079 2079 /// 2080 /// This function just returns a \ref GraphReader class. 2081 /// 2082 /// With this function a graph can be read from an 2080 /// This function just returns a \ref GraphReader class. 2081 /// 2082 /// With this function a graph can be read from an 2083 2083 /// \ref lgf-format "LGF" file or input stream with several maps and 2084 2084 /// attributes. For example, there is weighted matching problem on a … … 2236 2236 /// whitespaces are trimmed from each processed string. 2237 2237 /// 2238 /// For example let's see a section, which contain several2238 /// For example, let's see a section, which contain several 2239 2239 /// integers, which should be inserted into a vector. 2240 2240 ///\code -
lemon/lp_base.h
r956 r1094 1619 1619 inline LpBase::Constr operator<=(const LpBase::Expr &e, 1620 1620 const LpBase::Expr &f) { 1621 return LpBase::Constr(0, f - e, LpBase:: INF);1621 return LpBase::Constr(0, f - e, LpBase::NaN); 1622 1622 } 1623 1623 … … 1637 1637 inline LpBase::Constr operator<=(const LpBase::Expr &e, 1638 1638 const LpBase::Value &f) { 1639 return LpBase::Constr( - LpBase::INF, e, f);1639 return LpBase::Constr(LpBase::NaN, e, f); 1640 1640 } 1641 1641 … … 1646 1646 inline LpBase::Constr operator>=(const LpBase::Expr &e, 1647 1647 const LpBase::Expr &f) { 1648 return LpBase::Constr(0, e - f, LpBase:: INF);1648 return LpBase::Constr(0, e - f, LpBase::NaN); 1649 1649 } 1650 1650 … … 1666 1666 inline LpBase::Constr operator>=(const LpBase::Expr &e, 1667 1667 const LpBase::Value &f) { 1668 return LpBase::Constr(f, e, LpBase:: INF);1668 return LpBase::Constr(f, e, LpBase::NaN); 1669 1669 } 1670 1670 -
lemon/lp_base.h
r1092 r1094 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 085 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 83 83 MESSAGE_VERBOSE 84 84 }; 85 85 86 86 87 87 ///The floating point type used by the solver … … 115 115 typedef True LpCol; 116 116 /// Default constructor 117 117 118 118 /// \warning The default constructor sets the Col to an 119 119 /// undefined value. 120 120 Col() {} 121 121 /// Invalid constructor \& conversion. 122 122 123 123 /// This constructor initializes the Col to be invalid. 124 /// \sa Invalid for more details. 124 /// \sa Invalid for more details. 125 125 Col(const Invalid&) : _id(-1) {} 126 126 /// Equality operator … … 147 147 ///Iterator for iterate over the columns of an LP problem 148 148 149 /// Its usage is quite simple, for example you can count the number149 /// Its usage is quite simple, for example, you can count the number 150 150 /// of columns in an LP \c lp: 151 151 ///\code … … 157 157 public: 158 158 /// Default constructor 159 159 160 160 /// \warning The default constructor sets the iterator 161 161 /// to an undefined value. 162 162 ColIt() {} 163 163 /// Sets the iterator to the first Col 164 164 165 165 /// Sets the iterator to the first Col. 166 166 /// … … 170 170 } 171 171 /// Invalid constructor \& conversion 172 172 173 173 /// Initialize the iterator to be invalid. 174 174 /// \sa Invalid for more details. 175 175 ColIt(const Invalid&) : Col(INVALID) {} 176 176 /// Next column 177 177 178 178 /// Assign the iterator to the next column. 179 179 /// … … 210 210 typedef True LpRow; 211 211 /// Default constructor 212 212 213 213 /// \warning The default constructor sets the Row to an 214 214 /// undefined value. 215 215 Row() {} 216 216 /// Invalid constructor \& conversion. 217 217 218 218 /// This constructor initializes the Row to be invalid. 219 /// \sa Invalid for more details. 219 /// \sa Invalid for more details. 220 220 Row(const Invalid&) : _id(-1) {} 221 221 /// Equality operator … … 225 225 bool operator==(Row r) const {return _id == r._id;} 226 226 /// Inequality operator 227 227 228 228 /// \sa operator==(Row r) 229 229 /// … … 242 242 ///Iterator for iterate over the rows of an LP problem 243 243 244 /// Its usage is quite simple, for example you can count the number244 /// Its usage is quite simple, for example, you can count the number 245 245 /// of rows in an LP \c lp: 246 246 ///\code … … 252 252 public: 253 253 /// Default constructor 254 254 255 255 /// \warning The default constructor sets the iterator 256 256 /// to an undefined value. 257 257 RowIt() {} 258 258 /// Sets the iterator to the first Row 259 259 260 260 /// Sets the iterator to the first Row. 261 261 /// … … 265 265 } 266 266 /// Invalid constructor \& conversion 267 267 268 268 /// Initialize the iterator to be invalid. 269 269 /// \sa Invalid for more details. 270 270 RowIt(const Invalid&) : Row(INVALID) {} 271 271 /// Next row 272 272 273 273 /// Assign the iterator to the next row. 274 274 /// … … 348 348 typedef True SolverExpr; 349 349 /// Default constructor 350 350 351 351 /// Construct an empty expression, the coefficients and 352 352 /// the constant component are initialized to zero. … … 449 449 450 450 ///Iterator over the expression 451 452 ///The iterator iterates over the terms of the expression. 453 /// 451 452 ///The iterator iterates over the terms of the expression. 453 /// 454 454 ///\code 455 455 ///double s=0; … … 465 465 466 466 /// Sets the iterator to the first term 467 467 468 468 /// Sets the iterator to the first term of the expression. 469 469 /// … … 482 482 const Value& operator*() const { return _it->second; } 483 483 /// Next term 484 484 485 485 /// Assign the iterator to the next term. 486 486 /// … … 494 494 495 495 /// Const iterator over the expression 496 497 ///The iterator iterates over the terms of the expression. 498 /// 496 497 ///The iterator iterates over the terms of the expression. 498 /// 499 499 ///\code 500 500 ///double s=0; … … 510 510 511 511 /// Sets the iterator to the first term 512 512 513 513 /// Sets the iterator to the first term of the expression. 514 514 /// … … 525 525 526 526 /// Next term 527 527 528 528 /// Assign the iterator to the next term. 529 529 /// … … 674 674 typedef True SolverExpr; 675 675 /// Default constructor 676 676 677 677 /// Construct an empty expression, the coefficients are 678 678 /// initialized to zero. … … 709 709 } 710 710 /// \brief Removes the coefficients which's absolute value does 711 /// not exceed \c epsilon. 711 /// not exceed \c epsilon. 712 712 void simplify(Value epsilon = 0.0) { 713 713 std::map<int, Value>::iterator it=comps.begin(); … … 758 758 759 759 ///Iterator over the expression 760 761 ///The iterator iterates over the terms of the expression. 762 /// 760 761 ///The iterator iterates over the terms of the expression. 762 /// 763 763 ///\code 764 764 ///double s=0; … … 774 774 775 775 /// Sets the iterator to the first term 776 776 777 777 /// Sets the iterator to the first term of the expression. 778 778 /// … … 792 792 793 793 /// Next term 794 794 795 795 /// Assign the iterator to the next term. 796 796 /// … … 804 804 805 805 ///Iterator over the expression 806 807 ///The iterator iterates over the terms of the expression. 808 /// 806 807 ///The iterator iterates over the terms of the expression. 808 /// 809 809 ///\code 810 810 ///double s=0; … … 820 820 821 821 /// Sets the iterator to the first term 822 822 823 823 /// Sets the iterator to the first term of the expression. 824 824 /// … … 835 835 836 836 /// Next term 837 837 838 838 /// Assign the iterator to the next term. 839 839 /// … … 943 943 virtual int _addCol() = 0; 944 944 virtual int _addRow() = 0; 945 946 virtual int _addRow(Value l, ExprIterator b, ExprIterator e, Value u) { 947 int row = _addRow(); 948 _setRowCoeffs(row, b, e); 949 _setRowLowerBound(row, l); 950 _setRowUpperBound(row, u); 951 return row; 952 } 945 953 946 954 virtual void _eraseCol(int col) = 0; … … 1208 1216 ///\return The created row. 1209 1217 Row addRow(Value l,const Expr &e, Value u) { 1210 Row r=addRow(); 1211 row(r,l,e,u); 1218 Row r; 1219 e.simplify(); 1220 r._id = _addRowId(_addRow(l - *e, ExprIterator(e.comps.begin(), cols), 1221 ExprIterator(e.comps.end(), cols), u - *e)); 1212 1222 return r; 1213 1223 } … … 1218 1228 ///\return The created row. 1219 1229 Row addRow(const Constr &c) { 1220 Row r=addRow(); 1221 row(r,c); 1230 Row r; 1231 c.expr().simplify(); 1232 r._id = _addRowId(_addRow(c.lowerBounded()?c.lowerBound()-*c.expr():-INF, 1233 ExprIterator(c.expr().comps.begin(), cols), 1234 ExprIterator(c.expr().comps.end(), cols), 1235 c.upperBounded()?c.upperBound()-*c.expr():INF)); 1222 1236 return r; 1223 1237 } … … 1804 1818 enum VarStatus { 1805 1819 /// The variable is in the basis 1806 BASIC, 1820 BASIC, 1807 1821 /// The variable is free, but not basic 1808 1822 FREE, 1809 /// The variable has active lower bound 1823 /// The variable has active lower bound 1810 1824 LOWER, 1811 1825 /// The variable has active upper bound … … 1886 1900 } 1887 1901 /// Returns a component of the primal ray 1888 1902 1889 1903 /// The primal ray is solution of the modified primal problem, 1890 1904 /// where we change each finite bound to 0, and we looking for a … … 1920 1934 1921 1935 /// Returns a component of the dual ray 1922 1936 1923 1937 /// The dual ray is solution of the modified primal problem, where 1924 1938 /// we change each finite bound to 0 (i.e. the objective function … … 2062 2076 } 2063 2077 ///The value of the objective function 2064 2078 2065 2079 ///\return 2066 2080 ///- \ref INF or -\ref INF means either infeasibility or unboundedness -
lemon/network_simplex.h
r956 r978 1078 1078 ART_COST = std::numeric_limits<Cost>::max() / 2 + 1; 1079 1079 } else { 1080 ART_COST = std::numeric_limits<Cost>::min();1080 ART_COST = 0; 1081 1081 for (int i = 0; i != _arc_num; ++i) { 1082 1082 if (_cost[i] > ART_COST) ART_COST = _cost[i]; … … 1590 1590 if (_sum_supply == 0) { 1591 1591 if (_stype == GEQ) { 1592 Cost max_pot = std::numeric_limits<Cost>::min();1592 Cost max_pot = -std::numeric_limits<Cost>::max(); 1593 1593 for (int i = 0; i != _node_num; ++i) { 1594 1594 if (_pi[i] > max_pot) max_pot = _pi[i]; -
lemon/network_simplex.h
r976 r978 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 41 41 /// 42 42 /// \ref NetworkSimplex implements the primal Network Simplex algorithm 43 /// for finding a \ref min_cost_flow "minimum cost flow". 44 /// This algorithm is a specialized version of the linear programming 45 /// simplex method directly for the minimum cost flow problem. 46 /// It is one of the most efficient solution methods. 43 /// for finding a \ref min_cost_flow "minimum cost flow" 44 /// \ref amo93networkflows, \ref dantzig63linearprog, 45 /// \ref kellyoneill91netsimplex. 46 /// This algorithm is a highly efficient specialized version of the 47 /// linear programming simplex method directly for the minimum cost 48 /// flow problem. 47 49 /// 48 /// In general this classis the fastest implementation available49 /// in LEMON for th e minimum cost flowproblem.50 /// Moreover it supports both directions of the supply/demand inequality51 /// constraints. For more information see \ref SupplyType.50 /// In general, %NetworkSimplex is the fastest implementation available 51 /// in LEMON for this problem. 52 /// Moreover, it supports both directions of the supply/demand inequality 53 /// constraints. For more information, see \ref SupplyType. 52 54 /// 53 55 /// Most of the parameters of the problem (except for the digraph) … … 57 59 /// 58 60 /// \tparam GR The digraph type the algorithm runs on. 59 /// \tparam V The valuetype used for flow amounts, capacity bounds60 /// and supply values in the algorithm. By default it is \c int.61 /// \tparam C The valuetype used for costs and potentials in the62 /// algorithm. By default it is the same as \c V.61 /// \tparam V The number type used for flow amounts, capacity bounds 62 /// and supply values in the algorithm. By default, it is \c int. 63 /// \tparam C The number type used for costs and potentials in the 64 /// algorithm. By default, it is the same as \c V. 63 65 /// 64 /// \warning Both valuetypes must be signed and all input data must66 /// \warning Both number types must be signed and all input data must 65 67 /// be integer. 66 68 /// 67 69 /// \note %NetworkSimplex provides five different pivot rule 68 70 /// implementations, from which the most efficient one is used 69 /// by default. For more information see \ref PivotRule.71 /// by default. For more information, see \ref PivotRule. 70 72 template <typename GR, typename V = int, typename C = V> 71 73 class NetworkSimplex … … 96 98 UNBOUNDED 97 99 }; 98 100 99 101 /// \brief Constants for selecting the type of the supply constraints. 100 102 /// … … 114 116 LEQ 115 117 }; 116 118 117 119 /// \brief Constants for selecting the pivot rule. 118 120 /// … … 123 125 /// implementations that significantly affect the running time 124 126 /// of the algorithm. 125 /// By default \ref BLOCK_SEARCH "Block Search" is used, which127 /// By default, \ref BLOCK_SEARCH "Block Search" is used, which 126 128 /// proved to be the most efficient and the most robust on various 127 /// test inputs according to our benchmark tests.128 /// However another pivot rule can be selected using the \ref run()129 /// test inputs. 130 /// However, another pivot rule can be selected using the \ref run() 129 131 /// function with the proper parameter. 130 132 enum PivotRule { 131 133 132 /// The FirstEligible pivot rule.134 /// The \e First \e Eligible pivot rule. 133 135 /// The next eligible arc is selected in a wraparound fashion 134 136 /// in every iteration. 135 137 FIRST_ELIGIBLE, 136 138 137 /// The BestEligible pivot rule.139 /// The \e Best \e Eligible pivot rule. 138 140 /// The best eligible arc is selected in every iteration. 139 141 BEST_ELIGIBLE, 140 142 141 /// The BlockSearch pivot rule.143 /// The \e Block \e Search pivot rule. 142 144 /// A specified number of arcs are examined in every iteration 143 145 /// in a wraparound fashion and the best eligible arc is selected … … 145 147 BLOCK_SEARCH, 146 148 147 /// The Candidate List pivot rule.149 /// The \e Candidate \e List pivot rule. 148 150 /// In a major iteration a candidate list is built from eligible arcs 149 151 /// in a wraparound fashion and in the following minor iterations … … 151 153 CANDIDATE_LIST, 152 154 153 /// The Altering Candidate List pivot rule.155 /// The \e Altering \e Candidate \e List pivot rule. 154 156 /// It is a modified version of the Candidate List method. 155 157 /// It keeps only the several best eligible arcs from the former … … 157 159 ALTERING_LIST 158 160 }; 159 161 160 162 private: 161 163 162 164 TEMPLATE_DIGRAPH_TYPEDEFS(GR); 163 165 164 typedef std::vector<Arc> ArcVector;165 typedef std::vector<Node> NodeVector;166 166 typedef std::vector<int> IntVector; 167 typedef std::vector<bool> BoolVector;168 167 typedef std::vector<Value> ValueVector; 169 168 typedef std::vector<Cost> CostVector; 169 typedef std::vector<char> BoolVector; 170 // Note: vector<char> is used instead of vector<bool> for efficiency reasons 170 171 171 172 // State constants for arcs 172 enum ArcState Enum{173 enum ArcState { 173 174 STATE_UPPER = -1, 174 175 STATE_TREE = 0, 175 176 STATE_LOWER = 1 176 177 }; 178 179 typedef std::vector<signed char> StateVector; 180 // Note: vector<signed char> is used instead of vector<ArcState> for 181 // efficiency reasons 177 182 178 183 private: … … 195 200 IntVector _source; 196 201 IntVector _target; 202 bool _arc_mixing; 197 203 198 204 // Node and arc data … … 214 220 IntVector _dirty_revs; 215 221 BoolVector _forward; 216 IntVector _state;222 StateVector _state; 217 223 int _root; 218 224 … … 223 229 Value delta; 224 230 231 const Value MAX; 232 225 233 public: 226 234 227 235 /// \brief Constant for infinite upper bounds (capacities). 228 236 /// … … 243 251 const IntVector &_target; 244 252 const CostVector &_cost; 245 const IntVector&_state;253 const StateVector &_state; 246 254 const CostVector &_pi; 247 255 int &_in_arc; … … 264 272 bool findEnteringArc() { 265 273 Cost c; 266 for (int e = _next_arc; e <_search_arc_num; ++e) {274 for (int e = _next_arc; e != _search_arc_num; ++e) { 267 275 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 268 276 if (c < 0) { … … 272 280 } 273 281 } 274 for (int e = 0; e <_next_arc; ++e) {282 for (int e = 0; e != _next_arc; ++e) { 275 283 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 276 284 if (c < 0) { … … 295 303 const IntVector &_target; 296 304 const CostVector &_cost; 297 const IntVector&_state;305 const StateVector &_state; 298 306 const CostVector &_pi; 299 307 int &_in_arc; … … 312 320 bool findEnteringArc() { 313 321 Cost c, min = 0; 314 for (int e = 0; e <_search_arc_num; ++e) {322 for (int e = 0; e != _search_arc_num; ++e) { 315 323 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 316 324 if (c < min) { … … 334 342 const IntVector &_target; 335 343 const CostVector &_cost; 336 const IntVector&_state;344 const StateVector &_state; 337 345 const CostVector &_pi; 338 346 int &_in_arc; … … 353 361 { 354 362 // The main parameters of the pivot rule 355 const double BLOCK_SIZE_FACTOR = 0.5;363 const double BLOCK_SIZE_FACTOR = 1.0; 356 364 const int MIN_BLOCK_SIZE = 10; 357 365 … … 365 373 Cost c, min = 0; 366 374 int cnt = _block_size; 367 int e , min_arc = _next_arc;368 for (e = _next_arc; e <_search_arc_num; ++e) {375 int e; 376 for (e = _next_arc; e != _search_arc_num; ++e) { 369 377 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 370 378 if (c < min) { 371 379 min = c; 372 min_arc = e;380 _in_arc = e; 373 381 } 374 382 if (--cnt == 0) { 375 if (min < 0) break;383 if (min < 0) goto search_end; 376 384 cnt = _block_size; 377 385 } 378 386 } 379 if (min == 0 || cnt > 0) { 380 for (e = 0; e < _next_arc; ++e) { 381 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 382 if (c < min) { 383 min = c; 384 min_arc = e; 385 } 386 if (--cnt == 0) { 387 if (min < 0) break; 388 cnt = _block_size; 389 } 387 for (e = 0; e != _next_arc; ++e) { 388 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 389 if (c < min) { 390 min = c; 391 _in_arc = e; 392 } 393 if (--cnt == 0) { 394 if (min < 0) goto search_end; 395 cnt = _block_size; 390 396 } 391 397 } 392 398 if (min >= 0) return false; 393 _in_arc = min_arc; 399 400 search_end: 394 401 _next_arc = e; 395 402 return true; … … 408 415 const IntVector &_target; 409 416 const CostVector &_cost; 410 const IntVector&_state;417 const StateVector &_state; 411 418 const CostVector &_pi; 412 419 int &_in_arc; … … 429 436 { 430 437 // The main parameters of the pivot rule 431 const double LIST_LENGTH_FACTOR = 1.0;438 const double LIST_LENGTH_FACTOR = 0.25; 432 439 const int MIN_LIST_LENGTH = 10; 433 440 const double MINOR_LIMIT_FACTOR = 0.1; … … 446 453 bool findEnteringArc() { 447 454 Cost min, c; 448 int e , min_arc = _next_arc;455 int e; 449 456 if (_curr_length > 0 && _minor_count < _minor_limit) { 450 457 // Minor iteration: select the best eligible arc from the … … 457 464 if (c < min) { 458 465 min = c; 459 min_arc = e;466 _in_arc = e; 460 467 } 461 if (c >= 0) {468 else if (c >= 0) { 462 469 _candidates[i--] = _candidates[--_curr_length]; 463 470 } 464 471 } 465 if (min < 0) { 466 _in_arc = min_arc; 467 return true; 468 } 472 if (min < 0) return true; 469 473 } 470 474 … … 472 476 min = 0; 473 477 _curr_length = 0; 474 for (e = _next_arc; e <_search_arc_num; ++e) {478 for (e = _next_arc; e != _search_arc_num; ++e) { 475 479 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 476 480 if (c < 0) { … … 478 482 if (c < min) { 479 483 min = c; 480 min_arc = e;484 _in_arc = e; 481 485 } 482 if (_curr_length == _list_length) break; 483 } 484 } 485 if (_curr_length < _list_length) { 486 for (e = 0; e < _next_arc; ++e) { 487 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 488 if (c < 0) { 489 _candidates[_curr_length++] = e; 490 if (c < min) { 491 min = c; 492 min_arc = e; 493 } 494 if (_curr_length == _list_length) break; 486 if (_curr_length == _list_length) goto search_end; 487 } 488 } 489 for (e = 0; e != _next_arc; ++e) { 490 c = _state[e] * (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 491 if (c < 0) { 492 _candidates[_curr_length++] = e; 493 if (c < min) { 494 min = c; 495 _in_arc = e; 495 496 } 497 if (_curr_length == _list_length) goto search_end; 496 498 } 497 499 } 498 500 if (_curr_length == 0) return false; 501 502 search_end: 499 503 _minor_count = 1; 500 _in_arc = min_arc;501 504 _next_arc = e; 502 505 return true; … … 515 518 const IntVector &_target; 516 519 const CostVector &_cost; 517 const IntVector&_state;520 const StateVector &_state; 518 521 const CostVector &_pi; 519 522 int &_in_arc; … … 550 553 { 551 554 // The main parameters of the pivot rule 552 const double BLOCK_SIZE_FACTOR = 1. 5;555 const double BLOCK_SIZE_FACTOR = 1.0; 553 556 const int MIN_BLOCK_SIZE = 10; 554 557 const double HEAD_LENGTH_FACTOR = 0.1; … … 568 571 // Check the current candidate list 569 572 int e; 570 for (int i = 0; i <_curr_length; ++i) {573 for (int i = 0; i != _curr_length; ++i) { 571 574 e = _candidates[i]; 572 575 _cand_cost[e] = _state[e] * … … 579 582 // Extend the list 580 583 int cnt = _block_size; 581 int last_arc = 0;582 584 int limit = _head_length; 583 585 584 for ( int e = _next_arc; e <_search_arc_num; ++e) {586 for (e = _next_arc; e != _search_arc_num; ++e) { 585 587 _cand_cost[e] = _state[e] * 586 588 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 587 589 if (_cand_cost[e] < 0) { 588 590 _candidates[_curr_length++] = e; 589 last_arc = e;590 591 } 591 592 if (--cnt == 0) { 592 if (_curr_length > limit) break;593 if (_curr_length > limit) goto search_end; 593 594 limit = 0; 594 595 cnt = _block_size; 595 596 } 596 597 } 597 if (_curr_length <= limit) { 598 for (int e = 0; e < _next_arc; ++e) { 599 _cand_cost[e] = _state[e] * 600 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 601 if (_cand_cost[e] < 0) { 602 _candidates[_curr_length++] = e; 603 last_arc = e; 604 } 605 if (--cnt == 0) { 606 if (_curr_length > limit) break; 607 limit = 0; 608 cnt = _block_size; 609 } 598 for (e = 0; e != _next_arc; ++e) { 599 _cand_cost[e] = _state[e] * 600 (_cost[e] + _pi[_source[e]] - _pi[_target[e]]); 601 if (_cand_cost[e] < 0) { 602 _candidates[_curr_length++] = e; 603 } 604 if (--cnt == 0) { 605 if (_curr_length > limit) goto search_end; 606 limit = 0; 607 cnt = _block_size; 610 608 } 611 609 } 612 610 if (_curr_length == 0) return false; 613 _next_arc = last_arc + 1; 611 612 search_end: 614 613 615 614 // Make heap of the candidate list (approximating a partial sort) … … 619 618 // Pop the first element of the heap 620 619 _in_arc = _candidates[0]; 620 _next_arc = e; 621 621 pop_heap( _candidates.begin(), _candidates.begin() + _curr_length, 622 622 _sort_func ); … … 634 634 /// 635 635 /// \param graph The digraph the algorithm runs on. 636 NetworkSimplex(const GR& graph) : 636 /// \param arc_mixing Indicate if the arcs have to be stored in a 637 /// mixed order in the internal data structure. 638 /// In special cases, it could lead to better overall performance, 639 /// but it is usually slower. Therefore it is disabled by default. 640 NetworkSimplex(const GR& graph, bool arc_mixing = false) : 637 641 _graph(graph), _node_id(graph), _arc_id(graph), 642 _arc_mixing(arc_mixing), 643 MAX(std::numeric_limits<Value>::max()), 638 644 INF(std::numeric_limits<Value>::has_infinity ? 639 std::numeric_limits<Value>::infinity() : 640 std::numeric_limits<Value>::max()) 645 std::numeric_limits<Value>::infinity() : MAX) 641 646 { 642 // Check the valuetypes647 // Check the number types 643 648 LEMON_ASSERT(std::numeric_limits<Value>::is_signed, 644 649 "The flow type of NetworkSimplex must be signed"); 645 650 LEMON_ASSERT(std::numeric_limits<Cost>::is_signed, 646 651 "The cost type of NetworkSimplex must be signed"); 647 652 653 // Reset data structures 654 reset(); 655 } 656 657 /// \name Parameters 658 /// The parameters of the algorithm can be specified using these 659 /// functions. 660 661 /// @{ 662 663 /// \brief Set the lower bounds on the arcs. 664 /// 665 /// This function sets the lower bounds on the arcs. 666 /// If it is not used before calling \ref run(), the lower bounds 667 /// will be set to zero on all arcs. 668 /// 669 /// \param map An arc map storing the lower bounds. 670 /// Its \c Value type must be convertible to the \c Value type 671 /// of the algorithm. 672 /// 673 /// \return <tt>(*this)</tt> 674 template <typename LowerMap> 675 NetworkSimplex& lowerMap(const LowerMap& map) { 676 _have_lower = true; 677 for (ArcIt a(_graph); a != INVALID; ++a) { 678 _lower[_arc_id[a]] = map[a]; 679 } 680 return *this; 681 } 682 683 /// \brief Set the upper bounds (capacities) on the arcs. 684 /// 685 /// This function sets the upper bounds (capacities) on the arcs. 686 /// If it is not used before calling \ref run(), the upper bounds 687 /// will be set to \ref INF on all arcs (i.e. the flow value will be 688 /// unbounded from above). 689 /// 690 /// \param map An arc map storing the upper bounds. 691 /// Its \c Value type must be convertible to the \c Value type 692 /// of the algorithm. 693 /// 694 /// \return <tt>(*this)</tt> 695 template<typename UpperMap> 696 NetworkSimplex& upperMap(const UpperMap& map) { 697 for (ArcIt a(_graph); a != INVALID; ++a) { 698 _upper[_arc_id[a]] = map[a]; 699 } 700 return *this; 701 } 702 703 /// \brief Set the costs of the arcs. 704 /// 705 /// This function sets the costs of the arcs. 706 /// If it is not used before calling \ref run(), the costs 707 /// will be set to \c 1 on all arcs. 708 /// 709 /// \param map An arc map storing the costs. 710 /// Its \c Value type must be convertible to the \c Cost type 711 /// of the algorithm. 712 /// 713 /// \return <tt>(*this)</tt> 714 template<typename CostMap> 715 NetworkSimplex& costMap(const CostMap& map) { 716 for (ArcIt a(_graph); a != INVALID; ++a) { 717 _cost[_arc_id[a]] = map[a]; 718 } 719 return *this; 720 } 721 722 /// \brief Set the supply values of the nodes. 723 /// 724 /// This function sets the supply values of the nodes. 725 /// If neither this function nor \ref stSupply() is used before 726 /// calling \ref run(), the supply of each node will be set to zero. 727 /// 728 /// \param map A node map storing the supply values. 729 /// Its \c Value type must be convertible to the \c Value type 730 /// of the algorithm. 731 /// 732 /// \return <tt>(*this)</tt> 733 template<typename SupplyMap> 734 NetworkSimplex& supplyMap(const SupplyMap& map) { 735 for (NodeIt n(_graph); n != INVALID; ++n) { 736 _supply[_node_id[n]] = map[n]; 737 } 738 return *this; 739 } 740 741 /// \brief Set single source and target nodes and a supply value. 742 /// 743 /// This function sets a single source node and a single target node 744 /// and the required flow value. 745 /// If neither this function nor \ref supplyMap() is used before 746 /// calling \ref run(), the supply of each node will be set to zero. 747 /// 748 /// Using this function has the same effect as using \ref supplyMap() 749 /// with such a map in which \c k is assigned to \c s, \c -k is 750 /// assigned to \c t and all other nodes have zero supply value. 751 /// 752 /// \param s The source node. 753 /// \param t The target node. 754 /// \param k The required amount of flow from node \c s to node \c t 755 /// (i.e. the supply of \c s and the demand of \c t). 756 /// 757 /// \return <tt>(*this)</tt> 758 NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) { 759 for (int i = 0; i != _node_num; ++i) { 760 _supply[i] = 0; 761 } 762 _supply[_node_id[s]] = k; 763 _supply[_node_id[t]] = -k; 764 return *this; 765 } 766 767 /// \brief Set the type of the supply constraints. 768 /// 769 /// This function sets the type of the supply/demand constraints. 770 /// If it is not used before calling \ref run(), the \ref GEQ supply 771 /// type will be used. 772 /// 773 /// For more information, see \ref SupplyType. 774 /// 775 /// \return <tt>(*this)</tt> 776 NetworkSimplex& supplyType(SupplyType supply_type) { 777 _stype = supply_type; 778 return *this; 779 } 780 781 /// @} 782 783 /// \name Execution Control 784 /// The algorithm can be executed using \ref run(). 785 786 /// @{ 787 788 /// \brief Run the algorithm. 789 /// 790 /// This function runs the algorithm. 791 /// The paramters can be specified using functions \ref lowerMap(), 792 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), 793 /// \ref supplyType(). 794 /// For example, 795 /// \code 796 /// NetworkSimplex<ListDigraph> ns(graph); 797 /// ns.lowerMap(lower).upperMap(upper).costMap(cost) 798 /// .supplyMap(sup).run(); 799 /// \endcode 800 /// 801 /// This function can be called more than once. All the given parameters 802 /// are kept for the next call, unless \ref resetParams() or \ref reset() 803 /// is used, thus only the modified parameters have to be set again. 804 /// If the underlying digraph was also modified after the construction 805 /// of the class (or the last \ref reset() call), then the \ref reset() 806 /// function must be called. 807 /// 808 /// \param pivot_rule The pivot rule that will be used during the 809 /// algorithm. For more information, see \ref PivotRule. 810 /// 811 /// \return \c INFEASIBLE if no feasible flow exists, 812 /// \n \c OPTIMAL if the problem has optimal solution 813 /// (i.e. it is feasible and bounded), and the algorithm has found 814 /// optimal flow and node potentials (primal and dual solutions), 815 /// \n \c UNBOUNDED if the objective function of the problem is 816 /// unbounded, i.e. there is a directed cycle having negative total 817 /// cost and infinite upper bound. 818 /// 819 /// \see ProblemType, PivotRule 820 /// \see resetParams(), reset() 821 ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) { 822 if (!init()) return INFEASIBLE; 823 return start(pivot_rule); 824 } 825 826 /// \brief Reset all the parameters that have been given before. 827 /// 828 /// This function resets all the paramaters that have been given 829 /// before using functions \ref lowerMap(), \ref upperMap(), 830 /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType(). 831 /// 832 /// It is useful for multiple \ref run() calls. Basically, all the given 833 /// parameters are kept for the next \ref run() call, unless 834 /// \ref resetParams() or \ref reset() is used. 835 /// If the underlying digraph was also modified after the construction 836 /// of the class or the last \ref reset() call, then the \ref reset() 837 /// function must be used, otherwise \ref resetParams() is sufficient. 838 /// 839 /// For example, 840 /// \code 841 /// NetworkSimplex<ListDigraph> ns(graph); 842 /// 843 /// // First run 844 /// ns.lowerMap(lower).upperMap(upper).costMap(cost) 845 /// .supplyMap(sup).run(); 846 /// 847 /// // Run again with modified cost map (resetParams() is not called, 848 /// // so only the cost map have to be set again) 849 /// cost[e] += 100; 850 /// ns.costMap(cost).run(); 851 /// 852 /// // Run again from scratch using resetParams() 853 /// // (the lower bounds will be set to zero on all arcs) 854 /// ns.resetParams(); 855 /// ns.upperMap(capacity).costMap(cost) 856 /// .supplyMap(sup).run(); 857 /// \endcode 858 /// 859 /// \return <tt>(*this)</tt> 860 /// 861 /// \see reset(), run() 862 NetworkSimplex& resetParams() { 863 for (int i = 0; i != _node_num; ++i) { 864 _supply[i] = 0; 865 } 866 for (int i = 0; i != _arc_num; ++i) { 867 _lower[i] = 0; 868 _upper[i] = INF; 869 _cost[i] = 1; 870 } 871 _have_lower = false; 872 _stype = GEQ; 873 return *this; 874 } 875 876 /// \brief Reset the internal data structures and all the parameters 877 /// that have been given before. 878 /// 879 /// This function resets the internal data structures and all the 880 /// paramaters that have been given before using functions \ref lowerMap(), 881 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), 882 /// \ref supplyType(). 883 /// 884 /// It is useful for multiple \ref run() calls. Basically, all the given 885 /// parameters are kept for the next \ref run() call, unless 886 /// \ref resetParams() or \ref reset() is used. 887 /// If the underlying digraph was also modified after the construction 888 /// of the class or the last \ref reset() call, then the \ref reset() 889 /// function must be used, otherwise \ref resetParams() is sufficient. 890 /// 891 /// See \ref resetParams() for examples. 892 /// 893 /// \return <tt>(*this)</tt> 894 /// 895 /// \see resetParams(), run() 896 NetworkSimplex& reset() { 648 897 // Resize vectors 649 898 _node_num = countNodes(_graph); … … 672 921 _state.resize(max_arc_num); 673 922 674 // Copy the graph (store the arcs in a mixed order)923 // Copy the graph 675 924 int i = 0; 676 925 for (NodeIt n(_graph); n != INVALID; ++n, ++i) { 677 926 _node_id[n] = i; 678 927 } 679 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 680 i = 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 = (i % k) + 1; 686 } 687 688 // Initialize maps 689 for (int i = 0; i != _node_num; ++i) { 690 _supply[i] = 0; 691 } 692 for (int i = 0; i != _arc_num; ++i) { 693 _lower[i] = 0; 694 _upper[i] = INF; 695 _cost[i] = 1; 696 } 697 _have_lower = false; 698 _stype = GEQ; 699 } 700 701 /// \name Parameters 702 /// The parameters of the algorithm can be specified using these 703 /// functions. 704 705 /// @{ 706 707 /// \brief Set the lower bounds on the arcs. 708 /// 709 /// This function sets the lower bounds on the arcs. 710 /// If it is not used before calling \ref run(), the lower bounds 711 /// will be set to zero on all arcs. 712 /// 713 /// \param map An arc map storing the lower bounds. 714 /// Its \c Value type must be convertible to the \c Value type 715 /// of the algorithm. 716 /// 717 /// \return <tt>(*this)</tt> 718 template <typename LowerMap> 719 NetworkSimplex& lowerMap(const LowerMap& map) { 720 _have_lower = true; 721 for (ArcIt a(_graph); a != INVALID; ++a) { 722 _lower[_arc_id[a]] = map[a]; 723 } 724 return *this; 725 } 726 727 /// \brief Set the upper bounds (capacities) on the arcs. 728 /// 729 /// This function sets the upper bounds (capacities) on the arcs. 730 /// If it is not used before calling \ref run(), the upper bounds 731 /// will be set to \ref INF on all arcs (i.e. the flow value will be 732 /// unbounded from above on each arc). 733 /// 734 /// \param map An arc map storing the upper bounds. 735 /// Its \c Value type must be convertible to the \c Value type 736 /// of the algorithm. 737 /// 738 /// \return <tt>(*this)</tt> 739 template<typename UpperMap> 740 NetworkSimplex& upperMap(const UpperMap& map) { 741 for (ArcIt a(_graph); a != INVALID; ++a) { 742 _upper[_arc_id[a]] = map[a]; 743 } 744 return *this; 745 } 746 747 /// \brief Set the costs of the arcs. 748 /// 749 /// This function sets the costs of the arcs. 750 /// If it is not used before calling \ref run(), the costs 751 /// will be set to \c 1 on all arcs. 752 /// 753 /// \param map An arc map storing the costs. 754 /// Its \c Value type must be convertible to the \c Cost type 755 /// of the algorithm. 756 /// 757 /// \return <tt>(*this)</tt> 758 template<typename CostMap> 759 NetworkSimplex& costMap(const CostMap& map) { 760 for (ArcIt a(_graph); a != INVALID; ++a) { 761 _cost[_arc_id[a]] = map[a]; 762 } 763 return *this; 764 } 765 766 /// \brief Set the supply values of the nodes. 767 /// 768 /// This function sets the supply values of the nodes. 769 /// If neither this function nor \ref stSupply() is used before 770 /// calling \ref run(), the supply of each node will be set to zero. 771 /// (It makes sense only if non-zero lower bounds are given.) 772 /// 773 /// \param map A node map storing the supply values. 774 /// Its \c Value type must be convertible to the \c Value type 775 /// of the algorithm. 776 /// 777 /// \return <tt>(*this)</tt> 778 template<typename SupplyMap> 779 NetworkSimplex& supplyMap(const SupplyMap& map) { 780 for (NodeIt n(_graph); n != INVALID; ++n) { 781 _supply[_node_id[n]] = map[n]; 782 } 783 return *this; 784 } 785 786 /// \brief Set single source and target nodes and a supply value. 787 /// 788 /// This function sets a single source node and a single target node 789 /// and the required flow value. 790 /// If neither this function nor \ref supplyMap() is used before 791 /// calling \ref run(), the supply of each node will be set to zero. 792 /// (It makes sense only if non-zero lower bounds are given.) 793 /// 794 /// Using this function has the same effect as using \ref supplyMap() 795 /// with such a map in which \c k is assigned to \c s, \c -k is 796 /// assigned to \c t and all other nodes have zero supply value. 797 /// 798 /// \param s The source node. 799 /// \param t The target node. 800 /// \param k The required amount of flow from node \c s to node \c t 801 /// (i.e. the supply of \c s and the demand of \c t). 802 /// 803 /// \return <tt>(*this)</tt> 804 NetworkSimplex& stSupply(const Node& s, const Node& t, Value k) { 805 for (int i = 0; i != _node_num; ++i) { 806 _supply[i] = 0; 807 } 808 _supply[_node_id[s]] = k; 809 _supply[_node_id[t]] = -k; 810 return *this; 811 } 812 813 /// \brief Set the type of the supply constraints. 814 /// 815 /// This function sets the type of the supply/demand constraints. 816 /// If it is not used before calling \ref run(), the \ref GEQ supply 817 /// type will be used. 818 /// 819 /// For more information see \ref SupplyType. 820 /// 821 /// \return <tt>(*this)</tt> 822 NetworkSimplex& supplyType(SupplyType supply_type) { 823 _stype = supply_type; 824 return *this; 825 } 826 827 /// @} 828 829 /// \name Execution Control 830 /// The algorithm can be executed using \ref run(). 831 832 /// @{ 833 834 /// \brief Run the algorithm. 835 /// 836 /// This function runs the algorithm. 837 /// The paramters can be specified using functions \ref lowerMap(), 838 /// \ref upperMap(), \ref costMap(), \ref supplyMap(), \ref stSupply(), 839 /// \ref supplyType(). 840 /// For example, 841 /// \code 842 /// NetworkSimplex<ListDigraph> ns(graph); 843 /// ns.lowerMap(lower).upperMap(upper).costMap(cost) 844 /// .supplyMap(sup).run(); 845 /// \endcode 846 /// 847 /// This function can be called more than once. All the parameters 848 /// that have been given are kept for the next call, unless 849 /// \ref reset() is called, thus only the modified parameters 850 /// have to be set again. See \ref reset() for examples. 851 /// However the underlying digraph must not be modified after this 852 /// class have been constructed, since it copies and extends the graph. 853 /// 854 /// \param pivot_rule The pivot rule that will be used during the 855 /// algorithm. For more information see \ref PivotRule. 856 /// 857 /// \return \c INFEASIBLE if no feasible flow exists, 858 /// \n \c OPTIMAL if the problem has optimal solution 859 /// (i.e. it is feasible and bounded), and the algorithm has found 860 /// optimal flow and node potentials (primal and dual solutions), 861 /// \n \c UNBOUNDED if the objective function of the problem is 862 /// unbounded, i.e. there is a directed cycle having negative total 863 /// cost and infinite upper bound. 864 /// 865 /// \see ProblemType, PivotRule 866 ProblemType run(PivotRule pivot_rule = BLOCK_SEARCH) { 867 if (!init()) return INFEASIBLE; 868 return start(pivot_rule); 869 } 870 871 /// \brief Reset all the parameters that have been given before. 872 /// 873 /// This function resets all the paramaters that have been given 874 /// before using functions \ref lowerMap(), \ref upperMap(), 875 /// \ref costMap(), \ref supplyMap(), \ref stSupply(), \ref supplyType(). 876 /// 877 /// It is useful for multiple run() calls. If this function is not 878 /// used, all the parameters given before are kept for the next 879 /// \ref run() call. 880 /// However the underlying digraph must not be modified after this 881 /// class have been constructed, since it copies and extends the graph. 882 /// 883 /// For example, 884 /// \code 885 /// NetworkSimplex<ListDigraph> ns(graph); 886 /// 887 /// // First run 888 /// ns.lowerMap(lower).upperMap(upper).costMap(cost) 889 /// .supplyMap(sup).run(); 890 /// 891 /// // Run again with modified cost map (reset() is not called, 892 /// // so only the cost map have to be set again) 893 /// cost[e] += 100; 894 /// ns.costMap(cost).run(); 895 /// 896 /// // Run again from scratch using reset() 897 /// // (the lower bounds will be set to zero on all arcs) 898 /// ns.reset(); 899 /// ns.upperMap(capacity).costMap(cost) 900 /// .supplyMap(sup).run(); 901 /// \endcode 902 /// 903 /// \return <tt>(*this)</tt> 904 NetworkSimplex& reset() { 905 for (int i = 0; i != _node_num; ++i) { 906 _supply[i] = 0; 907 } 908 for (int i = 0; i != _arc_num; ++i) { 909 _lower[i] = 0; 910 _upper[i] = INF; 911 _cost[i] = 1; 912 } 913 _have_lower = false; 914 _stype = GEQ; 928 if (_arc_mixing) { 929 // Store the arcs in a mixed order 930 int k = std::max(int(std::sqrt(double(_arc_num))), 10); 931 int i = 0, j = 0; 932 for (ArcIt a(_graph); a != INVALID; ++a) { 933 _arc_id[a] = i; 934 _source[i] = _node_id[_graph.source(a)]; 935 _target[i] = _node_id[_graph.target(a)]; 936 if ((i += k) >= _arc_num) i = ++j; 937 } 938 } else { 939 // Store the arcs in the original order 940 int i = 0; 941 for (ArcIt a(_graph); a != INVALID; ++a, ++i) { 942 _arc_id[a] = i; 943 _source[i] = _node_id[_graph.source(a)]; 944 _target[i] = _node_id[_graph.target(a)]; 945 } 946 } 947 948 // Reset parameters 949 resetParams(); 915 950 return *this; 916 951 } … … 1025 1060 Value c = _lower[i]; 1026 1061 if (c >= 0) { 1027 _cap[i] = _upper[i] < INF? _upper[i] - c : INF;1062 _cap[i] = _upper[i] < MAX ? _upper[i] - c : INF; 1028 1063 } else { 1029 _cap[i] = _upper[i] < INF+ c ? _upper[i] - c : INF;1064 _cap[i] = _upper[i] < MAX + c ? _upper[i] - c : INF; 1030 1065 } 1031 1066 _supply[_source[i]] -= c; … … 1055 1090 _state[i] = STATE_LOWER; 1056 1091 } 1057 1092 1058 1093 // Set data for the artificial root node 1059 1094 _root = _node_num; … … 1219 1254 e = _pred[u]; 1220 1255 d = _forward[u] ? 1221 _flow[e] : (_cap[e] == INF? INF : _cap[e] - _flow[e]);1256 _flow[e] : (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]); 1222 1257 if (d < delta) { 1223 1258 delta = d; … … 1229 1264 for (int u = second; u != join; u = _parent[u]) { 1230 1265 e = _pred[u]; 1231 d = _forward[u] ? 1232 (_cap[e] == INF? INF : _cap[e] - _flow[e]) : _flow[e];1266 d = _forward[u] ? 1267 (_cap[e] >= MAX ? INF : _cap[e] - _flow[e]) : _flow[e]; 1233 1268 if (d <= delta) { 1234 1269 delta = d; … … 1331 1366 1332 1367 // Update _rev_thread using the new _thread values 1333 for (int i = 0; i <int(_dirty_revs.size()); ++i) {1368 for (int i = 0; i != int(_dirty_revs.size()); ++i) { 1334 1369 u = _dirty_revs[i]; 1335 1370 _rev_thread[_thread[u]] = u; … … 1401 1436 _pi[u] += sigma; 1402 1437 } 1438 } 1439 1440 // Heuristic initial pivots 1441 bool initialPivots() { 1442 Value curr, total = 0; 1443 std::vector<Node> supply_nodes, demand_nodes; 1444 for (NodeIt u(_graph); u != INVALID; ++u) { 1445 curr = _supply[_node_id[u]]; 1446 if (curr > 0) { 1447 total += curr; 1448 supply_nodes.push_back(u); 1449 } 1450 else if (curr < 0) { 1451 demand_nodes.push_back(u); 1452 } 1453 } 1454 if (_sum_supply > 0) total -= _sum_supply; 1455 if (total <= 0) return true; 1456 1457 IntVector arc_vector; 1458 if (_sum_supply >= 0) { 1459 if (supply_nodes.size() == 1 && demand_nodes.size() == 1) { 1460 // Perform a reverse graph search from the sink to the source 1461 typename GR::template NodeMap<bool> reached(_graph, false); 1462 Node s = supply_nodes[0], t = demand_nodes[0]; 1463 std::vector<Node> stack; 1464 reached[t] = true; 1465 stack.push_back(t); 1466 while (!stack.empty()) { 1467 Node u, v = stack.back(); 1468 stack.pop_back(); 1469 if (v == s) break; 1470 for (InArcIt a(_graph, v); a != INVALID; ++a) { 1471 if (reached[u = _graph.source(a)]) continue; 1472 int j = _arc_id[a]; 1473 if (_cap[j] >= total) { 1474 arc_vector.push_back(j); 1475 reached[u] = true; 1476 stack.push_back(u); 1477 } 1478 } 1479 } 1480 } else { 1481 // Find the min. cost incomming arc for each demand node 1482 for (int i = 0; i != int(demand_nodes.size()); ++i) { 1483 Node v = demand_nodes[i]; 1484 Cost c, min_cost = std::numeric_limits<Cost>::max(); 1485 Arc min_arc = INVALID; 1486 for (InArcIt a(_graph, v); a != INVALID; ++a) { 1487 c = _cost[_arc_id[a]]; 1488 if (c < min_cost) { 1489 min_cost = c; 1490 min_arc = a; 1491 } 1492 } 1493 if (min_arc != INVALID) { 1494 arc_vector.push_back(_arc_id[min_arc]); 1495 } 1496 } 1497 } 1498 } else { 1499 // Find the min. cost outgoing arc for each supply node 1500 for (int i = 0; i != int(supply_nodes.size()); ++i) { 1501 Node u = supply_nodes[i]; 1502 Cost c, min_cost = std::numeric_limits<Cost>::max(); 1503 Arc min_arc = INVALID; 1504 for (OutArcIt a(_graph, u); a != INVALID; ++a) { 1505 c = _cost[_arc_id[a]]; 1506 if (c < min_cost) { 1507 min_cost = c; 1508 min_arc = a; 1509 } 1510 } 1511 if (min_arc != INVALID) { 1512 arc_vector.push_back(_arc_id[min_arc]); 1513 } 1514 } 1515 } 1516 1517 // Perform heuristic initial pivots 1518 for (int i = 0; i != int(arc_vector.size()); ++i) { 1519 in_arc = arc_vector[i]; 1520 if (_state[in_arc] * (_cost[in_arc] + _pi[_source[in_arc]] - 1521 _pi[_target[in_arc]]) >= 0) continue; 1522 findJoinNode(); 1523 bool change = findLeavingArc(); 1524 if (delta >= MAX) return false; 1525 changeFlow(change); 1526 if (change) { 1527 updateTreeStructure(); 1528 updatePotential(); 1529 } 1530 } 1531 return true; 1403 1532 } 1404 1533 … … 1425 1554 PivotRuleImpl pivot(*this); 1426 1555 1556 // Perform heuristic initial pivots 1557 if (!initialPivots()) return UNBOUNDED; 1558 1427 1559 // Execute the Network Simplex algorithm 1428 1560 while (pivot.findEnteringArc()) { 1429 1561 findJoinNode(); 1430 1562 bool change = findLeavingArc(); 1431 if (delta >= INF) return UNBOUNDED;1563 if (delta >= MAX) return UNBOUNDED; 1432 1564 changeFlow(change); 1433 1565 if (change) { … … 1436 1568 } 1437 1569 } 1438 1570 1439 1571 // Check feasibility 1440 1572 for (int e = _search_arc_num; e != _all_arc_num; ++e) { … … 1453 1585 } 1454 1586 } 1455 1587 1456 1588 // Shift potentials to meet the requirements of the GEQ/LEQ type 1457 1589 // optimality conditions -
lemon/preflow.h
r956 r1107 544 544 _flow->set(e, (*_capacity)[e]); 545 545 (*_excess)[u] += rem; 546 if (u != _target && !_level->active(u)) {547 _level->activate(u);548 }549 546 } 550 547 } … … 556 553 _flow->set(e, 0); 557 554 (*_excess)[v] += rem; 558 if (v != _target && !_level->active(v)) { 559 _level->activate(v); 560 } 561 } 562 } 555 } 556 } 557 for (NodeIt n(_graph); n != INVALID; ++n) 558 if(n!=_source && n!=_target && _tolerance.positive((*_excess)[n])) 559 _level->activate(n); 560 563 561 return true; 564 562 } … … 577 575 _phase = true; 578 576 579 Node n = _level->highestActive(); 580 int level = _level->highestActiveLevel(); 581 while (n != INVALID) { 577 while (true) { 582 578 int num = _node_num; 583 579 584 while (num > 0 && n != INVALID) { 580 Node n = INVALID; 581 int level = -1; 582 583 while (num > 0) { 584 n = _level->highestActive(); 585 if (n == INVALID) goto first_phase_done; 586 level = _level->highestActiveLevel(); 587 --num; 588 585 589 Value excess = (*_excess)[n]; 586 590 int new_level = _level->maxLevel(); … … 648 652 _level->deactivate(n); 649 653 } 650 651 n = _level->highestActive(); 652 level = _level->highestActiveLevel(); 654 } 655 656 num = _node_num * 20; 657 while (num > 0) { 658 while (level >= 0 && _level->activeFree(level)) { 659 --level; 660 } 661 if (level == -1) { 662 n = _level->highestActive(); 663 level = _level->highestActiveLevel(); 664 if (n == INVALID) goto first_phase_done; 665 } else { 666 n = _level->activeOn(level); 667 } 653 668 --num; 654 } 655 656 num = _node_num * 20; 657 while (num > 0 && n != INVALID) { 669 658 670 Value excess = (*_excess)[n]; 659 671 int new_level = _level->maxLevel(); … … 721 733 _level->deactivate(n); 722 734 } 723 724 while (level >= 0 && _level->activeFree(level)) { 725 --level; 726 } 727 if (level == -1) { 728 n = _level->highestActive(); 729 level = _level->highestActiveLevel(); 730 } else { 731 n = _level->activeOn(level); 732 } 733 --num; 734 } 735 } 735 } 736 } 737 first_phase_done:; 736 738 } 737 739 -
lemon/preflow.h
r1027 r1107 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003-20 095 * Copyright (C) 2003-2010 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 53 53 /// The type of the map that stores the flow values. 54 54 /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept. 55 #ifdef DOXYGEN 56 typedef GR::ArcMap<Value> FlowMap; 57 #else 55 58 typedef typename Digraph::template ArcMap<Value> FlowMap; 59 #endif 56 60 57 61 /// \brief Instantiates a FlowMap. … … 68 72 /// The elevator type used by Preflow algorithm. 69 73 /// 70 /// \sa Elevator 71 /// \sa LinkedElevator 72 typedef LinkedElevator<Digraph, typename Digraph::Node> Elevator; 74 /// \sa Elevator, LinkedElevator 75 #ifdef DOXYGEN 76 typedef lemon::Elevator<GR, GR::Node> Elevator; 77 #else 78 typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator; 79 #endif 73 80 74 81 /// \brief Instantiates an Elevator. … … 96 103 /// This class provides an implementation of Goldberg-Tarjan's \e preflow 97 104 /// \e push-relabel algorithm producing a \ref max_flow 98 /// "flow of maximum value" in a digraph. 105 /// "flow of maximum value" in a digraph \ref clrs01algorithms, 106 /// \ref amo93networkflows, \ref goldberg88newapproach. 99 107 /// The preflow algorithms are the fastest known maximum 100 /// flow algorithms. The current implementation use a mixture of the108 /// flow algorithms. The current implementation uses a mixture of the 101 109 /// \e "highest label" and the \e "bound decrease" heuristics. 102 110 /// The worst case time complexity of the algorithm is \f$O(n^2\sqrt{e})\f$. … … 106 114 /// second phase constructs a feasible maximum flow on each arc. 107 115 /// 116 /// \warning This implementation cannot handle infinite or very large 117 /// capacities (e.g. the maximum value of \c CAP::Value). 118 /// 108 119 /// \tparam GR The type of the digraph the algorithm runs on. 109 120 /// \tparam CAP The type of the capacity map. The default map 110 121 /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>". 122 /// \tparam TR The traits class that defines various types used by the 123 /// algorithm. By default, it is \ref PreflowDefaultTraits 124 /// "PreflowDefaultTraits<GR, CAP>". 125 /// In most cases, this parameter should not be set directly, 126 /// consider to use the named template parameters instead. 111 127 #ifdef DOXYGEN 112 128 template <typename GR, typename CAP, typename TR> … … 258 274 /// able to automatically created by the algorithm (i.e. the 259 275 /// digraph and the maximum level should be passed to it). 260 /// However an external elevator object could also be passed to the276 /// However, an external elevator object could also be passed to the 261 277 /// algorithm with the \ref elevator(Elevator&) "elevator()" function 262 278 /// before calling \ref run() or \ref init(). … … 372 388 } 373 389 374 /// \brief Sets the tolerance used by algorithm. 375 /// 376 /// Sets the tolerance used by algorithm. 390 /// \brief Sets the tolerance used by the algorithm. 391 /// 392 /// Sets the tolerance object used by the algorithm. 393 /// \return <tt>(*this)</tt> 377 394 Preflow& tolerance(const Tolerance& tolerance) { 378 395 _tolerance = tolerance; … … 382 399 /// \brief Returns a const reference to the tolerance. 383 400 /// 384 /// Returns a const reference to the tolerance. 401 /// Returns a const reference to the tolerance object used by 402 /// the algorithm. 385 403 const Tolerance& tolerance() const { 386 404 return _tolerance; … … 390 408 /// The simplest way to execute the preflow algorithm is to use 391 409 /// \ref run() or \ref runMinCut().\n 392 /// If you need morecontrol on the initial solution or the execution,393 /// first you have to call one of the \ref init() functions, then410 /// If you need better control on the initial solution or the execution, 411 /// you have to call one of the \ref init() functions first, then 394 412 /// \ref startFirstPhase() and if you need it \ref startSecondPhase(). 395 413
Note: See TracChangeset
for help on using the changeset viewer.