Changes in lemon/suurballe.h [670:7c1324b35d89:931:abb95d48e89e] in lemon
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/suurballe.h
r670 r931 30 30 #include <lemon/path.h> 31 31 #include <lemon/list_graph.h> 32 #include <lemon/dijkstra.h> 32 33 #include <lemon/maps.h> 33 34 34 35 namespace lemon { 36 37 /// \brief Default traits class of Suurballe algorithm. 38 /// 39 /// Default traits class of Suurballe algorithm. 40 /// \tparam GR The digraph type the algorithm runs on. 41 /// \tparam LEN The type of the length map. 42 /// The default value is <tt>GR::ArcMap<int></tt>. 43 #ifdef DOXYGEN 44 template <typename GR, typename LEN> 45 #else 46 template < typename GR, 47 typename LEN = typename GR::template ArcMap<int> > 48 #endif 49 struct SuurballeDefaultTraits 50 { 51 /// The type of the digraph. 52 typedef GR Digraph; 53 /// The type of the length map. 54 typedef LEN LengthMap; 55 /// The type of the lengths. 56 typedef typename LEN::Value Length; 57 /// The type of the flow map. 58 typedef typename GR::template ArcMap<int> FlowMap; 59 /// The type of the potential map. 60 typedef typename GR::template NodeMap<Length> PotentialMap; 61 62 /// \brief The path type 63 /// 64 /// The type used for storing the found arcdisjoint paths. 65 /// It must conform to the \ref lemon::concepts::Path "Path" concept 66 /// and it must have an \c addBack() function. 67 typedef lemon::Path<Digraph> Path; 68 69 /// The cross reference type used for the heap. 70 typedef typename GR::template NodeMap<int> HeapCrossRef; 71 72 /// \brief The heap type used for internal Dijkstra computations. 73 /// 74 /// The type of the heap used for internal Dijkstra computations. 75 /// It must conform to the \ref lemon::concepts::Heap "Heap" concept 76 /// and its priority type must be \c Length. 77 typedef BinHeap<Length, HeapCrossRef> Heap; 78 }; 35 79 36 80 /// \addtogroup shortest_path … … 47 91 /// "minimum cost flow problem". This implementation is actually an 48 92 /// efficient specialized version of the \ref CapacityScaling 49 /// " Successive Shortest Path" algorithm directly for this problem.93 /// "successive shortest path" algorithm directly for this problem. 50 94 /// Therefore this class provides query functions for flow values and 51 95 /// node potentials (the dual solution) just like the minimum cost flow … … 56 100 /// The default value is <tt>GR::ArcMap<int></tt>. 57 101 /// 58 /// \warning Length values should be \e nonnegative \e integers.102 /// \warning Length values should be \e nonnegative. 59 103 /// 60 /// \note For finding nodedisjoint pathsthis algorithm can be used104 /// \note For finding \e nodedisjoint paths, this algorithm can be used 61 105 /// along with the \ref SplitNodes adaptor. 62 106 #ifdef DOXYGEN 63 template <typename GR, typename LEN >107 template <typename GR, typename LEN, typename TR> 64 108 #else 65 109 template < typename GR, 66 typename LEN = typename GR::template ArcMap<int> > 110 typename LEN = typename GR::template ArcMap<int>, 111 typename TR = SuurballeDefaultTraits<GR, LEN> > 67 112 #endif 68 113 class Suurballe … … 75 120 public: 76 121 77 /// The type of the digraph the algorithm runs on.78 typedef GRDigraph;122 /// The type of the digraph. 123 typedef typename TR::Digraph Digraph; 79 124 /// The type of the length map. 80 typedef LENLengthMap;125 typedef typename TR::LengthMap LengthMap; 81 126 /// The type of the lengths. 82 typedef typename LengthMap::ValueLength;83 #ifdef DOXYGEN 127 typedef typename TR::Length Length; 128 84 129 /// The type of the flow map. 85 typedef GR::ArcMap<int>FlowMap;130 typedef typename TR::FlowMap FlowMap; 86 131 /// The type of the potential map. 87 typedef GR::NodeMap<Length> PotentialMap; 88 #else 89 /// The type of the flow map. 90 typedef typename Digraph::template ArcMap<int> FlowMap; 91 /// The type of the potential map. 92 typedef typename Digraph::template NodeMap<Length> PotentialMap; 93 #endif 94 132 typedef typename TR::PotentialMap PotentialMap; 95 133 /// The type of the path structures. 96 typedef SimplePath<GR> Path; 134 typedef typename TR::Path Path; 135 /// The cross reference type used for the heap. 136 typedef typename TR::HeapCrossRef HeapCrossRef; 137 /// The heap type used for internal Dijkstra computations. 138 typedef typename TR::Heap Heap; 139 140 /// The \ref SuurballeDefaultTraits "traits class" of the algorithm. 141 typedef TR Traits; 97 142 98 143 private: … … 105 150 class ResidualDijkstra 106 151 { 107 typedef typename Digraph::template NodeMap<int> HeapCrossRef;108 typedef BinHeap<Length, HeapCrossRef> Heap;109 110 152 private: 111 153 112 // The digraph the algorithm runs on113 154 const Digraph &_graph; 114 115 // The main maps 155 const LengthMap &_length; 116 156 const FlowMap &_flow; 117 const LengthMap &_length; 118 PotentialMap &_potential; 119 120 // The distance map 121 PotentialMap _dist; 122 // The pred arc map 157 PotentialMap &_pi; 123 158 PredMap &_pred; 124 // The processed (i.e. permanently labeled) nodes125 std::vector<Node> _proc_nodes;126 127 159 Node _s; 128 160 Node _t; 161 162 PotentialMap _dist; 163 std::vector<Node> _proc_nodes; 129 164 130 165 public: 131 166 132 /// Constructor. 133 ResidualDijkstra( const Digraph &graph, 134 const FlowMap &flow, 135 const LengthMap &length, 136 PotentialMap &potential, 137 PredMap &pred, 138 Node s, Node t ) : 139 _graph(graph), _flow(flow), _length(length), _potential(potential), 140 _dist(graph), _pred(pred), _s(s), _t(t) {} 141 142 /// \brief Run the algorithm. It returns \c true if a path is found 143 /// from the source node to the target node. 144 bool run() { 167 // Constructor 168 ResidualDijkstra(Suurballe &srb) : 169 _graph(srb._graph), _length(srb._length), 170 _flow(*srb._flow), _pi(*srb._potential), _pred(srb._pred), 171 _s(srb._s), _t(srb._t), _dist(_graph) {} 172 173 // Run the algorithm and return true if a path is found 174 // from the source node to the target node. 175 bool run(int cnt) { 176 return cnt == 0 ? startFirst() : start(); 177 } 178 179 private: 180 181 // Execute the algorithm for the first time (the flow and potential 182 // functions have to be identically zero). 183 bool startFirst() { 145 184 HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP); 146 185 Heap heap(heap_cross_ref); … … 152 191 while (!heap.empty() && heap.top() != _t) { 153 192 Node u = heap.top(), v; 154 Length d = heap.prio() + _potential[u], nd;193 Length d = heap.prio(), dn; 155 194 _dist[u] = heap.prio(); 195 _proc_nodes.push_back(u); 156 196 heap.pop(); 197 198 // Traverse outgoing arcs 199 for (OutArcIt e(_graph, u); e != INVALID; ++e) { 200 v = _graph.target(e); 201 switch(heap.state(v)) { 202 case Heap::PRE_HEAP: 203 heap.push(v, d + _length[e]); 204 _pred[v] = e; 205 break; 206 case Heap::IN_HEAP: 207 dn = d + _length[e]; 208 if (dn < heap[v]) { 209 heap.decrease(v, dn); 210 _pred[v] = e; 211 } 212 break; 213 case Heap::POST_HEAP: 214 break; 215 } 216 } 217 } 218 if (heap.empty()) return false; 219 220 // Update potentials of processed nodes 221 Length t_dist = heap.prio(); 222 for (int i = 0; i < int(_proc_nodes.size()); ++i) 223 _pi[_proc_nodes[i]] = _dist[_proc_nodes[i]]  t_dist; 224 return true; 225 } 226 227 // Execute the algorithm. 228 bool start() { 229 HeapCrossRef heap_cross_ref(_graph, Heap::PRE_HEAP); 230 Heap heap(heap_cross_ref); 231 heap.push(_s, 0); 232 _pred[_s] = INVALID; 233 _proc_nodes.clear(); 234 235 // Process nodes 236 while (!heap.empty() && heap.top() != _t) { 237 Node u = heap.top(), v; 238 Length d = heap.prio() + _pi[u], dn; 239 _dist[u] = heap.prio(); 157 240 _proc_nodes.push_back(u); 241 heap.pop(); 158 242 159 243 // Traverse outgoing arcs … … 162 246 v = _graph.target(e); 163 247 switch(heap.state(v)) { 164 case Heap::PRE_HEAP: 165 heap.push(v, d + _length[e]  _potential[v]); 166 _pred[v] = e; 167 break; 168 case Heap::IN_HEAP: 169 nd = d + _length[e]  _potential[v]; 170 if (nd < heap[v]) { 171 heap.decrease(v, nd); 248 case Heap::PRE_HEAP: 249 heap.push(v, d + _length[e]  _pi[v]); 172 250 _pred[v] = e; 173 } 174 break; 175 case Heap::POST_HEAP: 176 break; 251 break; 252 case Heap::IN_HEAP: 253 dn = d + _length[e]  _pi[v]; 254 if (dn < heap[v]) { 255 heap.decrease(v, dn); 256 _pred[v] = e; 257 } 258 break; 259 case Heap::POST_HEAP: 260 break; 177 261 } 178 262 } … … 184 268 v = _graph.source(e); 185 269 switch(heap.state(v)) { 186 case Heap::PRE_HEAP: 187 heap.push(v, d  _length[e]  _potential[v]); 188 _pred[v] = e; 189 break; 190 case Heap::IN_HEAP: 191 nd = d  _length[e]  _potential[v]; 192 if (nd < heap[v]) { 193 heap.decrease(v, nd); 270 case Heap::PRE_HEAP: 271 heap.push(v, d  _length[e]  _pi[v]); 194 272 _pred[v] = e; 195 } 196 break; 197 case Heap::POST_HEAP: 198 break; 273 break; 274 case Heap::IN_HEAP: 275 dn = d  _length[e]  _pi[v]; 276 if (dn < heap[v]) { 277 heap.decrease(v, dn); 278 _pred[v] = e; 279 } 280 break; 281 case Heap::POST_HEAP: 282 break; 199 283 } 200 284 } … … 206 290 Length t_dist = heap.prio(); 207 291 for (int i = 0; i < int(_proc_nodes.size()); ++i) 208 _p otential[_proc_nodes[i]] += _dist[_proc_nodes[i]]  t_dist;292 _pi[_proc_nodes[i]] += _dist[_proc_nodes[i]]  t_dist; 209 293 return true; 210 294 } 211 295 212 296 }; //class ResidualDijkstra 297 298 public: 299 300 /// \name Named Template Parameters 301 /// @{ 302 303 template <typename T> 304 struct SetFlowMapTraits : public Traits { 305 typedef T FlowMap; 306 }; 307 308 /// \brief \ref namedtemplparam "Named parameter" for setting 309 /// \c FlowMap type. 310 /// 311 /// \ref namedtemplparam "Named parameter" for setting 312 /// \c FlowMap type. 313 template <typename T> 314 struct SetFlowMap 315 : public Suurballe<GR, LEN, SetFlowMapTraits<T> > { 316 typedef Suurballe<GR, LEN, SetFlowMapTraits<T> > Create; 317 }; 318 319 template <typename T> 320 struct SetPotentialMapTraits : public Traits { 321 typedef T PotentialMap; 322 }; 323 324 /// \brief \ref namedtemplparam "Named parameter" for setting 325 /// \c PotentialMap type. 326 /// 327 /// \ref namedtemplparam "Named parameter" for setting 328 /// \c PotentialMap type. 329 template <typename T> 330 struct SetPotentialMap 331 : public Suurballe<GR, LEN, SetPotentialMapTraits<T> > { 332 typedef Suurballe<GR, LEN, SetPotentialMapTraits<T> > Create; 333 }; 334 335 template <typename T> 336 struct SetPathTraits : public Traits { 337 typedef T Path; 338 }; 339 340 /// \brief \ref namedtemplparam "Named parameter" for setting 341 /// \c %Path type. 342 /// 343 /// \ref namedtemplparam "Named parameter" for setting \c %Path type. 344 /// It must conform to the \ref lemon::concepts::Path "Path" concept 345 /// and it must have an \c addBack() function. 346 template <typename T> 347 struct SetPath 348 : public Suurballe<GR, LEN, SetPathTraits<T> > { 349 typedef Suurballe<GR, LEN, SetPathTraits<T> > Create; 350 }; 351 352 template <typename H, typename CR> 353 struct SetHeapTraits : public Traits { 354 typedef H Heap; 355 typedef CR HeapCrossRef; 356 }; 357 358 /// \brief \ref namedtemplparam "Named parameter" for setting 359 /// \c Heap and \c HeapCrossRef types. 360 /// 361 /// \ref namedtemplparam "Named parameter" for setting \c Heap 362 /// and \c HeapCrossRef types with automatic allocation. 363 /// They will be used for internal Dijkstra computations. 364 /// The heap type must conform to the \ref lemon::concepts::Heap "Heap" 365 /// concept and its priority type must be \c Length. 366 template <typename H, 367 typename CR = typename Digraph::template NodeMap<int> > 368 struct SetHeap 369 : public Suurballe<GR, LEN, SetHeapTraits<H, CR> > { 370 typedef Suurballe<GR, LEN, SetHeapTraits<H, CR> > Create; 371 }; 372 373 /// @} 213 374 214 375 private: … … 227 388 228 389 // The source node 229 Node _s ource;390 Node _s; 230 391 // The target node 231 Node _t arget;392 Node _t; 232 393 233 394 // Container to store the found paths 234 std::vector< SimplePath<Digraph> >paths;395 std::vector<Path> _paths; 235 396 int _path_num; 236 397 237 398 // The pred arc map 238 399 PredMap _pred; 239 // Implementation of the Dijkstra algorithm for finding augmenting 240 // shortest paths in the residual network 241 ResidualDijkstra *_dijkstra; 400 401 // Data for full init 402 PotentialMap *_init_dist; 403 PredMap *_init_pred; 404 bool _full_init; 242 405 243 406 public: … … 252 415 const LengthMap &length ) : 253 416 _graph(graph), _length(length), _flow(0), _local_flow(false), 254 _potential(0), _local_potential(false), _pred(graph) 255 { 256 LEMON_ASSERT(std::numeric_limits<Length>::is_integer, 257 "The length type of Suurballe must be integer"); 258 } 417 _potential(0), _local_potential(false), _pred(graph), 418 _init_dist(0), _init_pred(0) 419 {} 259 420 260 421 /// Destructor. … … 262 423 if (_local_flow) delete _flow; 263 424 if (_local_potential) delete _potential; 264 delete _dijkstra; 425 delete _init_dist; 426 delete _init_pred; 265 427 } 266 428 … … 307 469 /// \name Execution Control 308 470 /// The simplest way to execute the algorithm is to call the run() 309 /// function. 310 /// \n 471 /// function.\n 472 /// If you need to execute the algorithm many times using the same 473 /// source node, then you may call fullInit() once and start() 474 /// for each target node.\n 311 475 /// If you only need the flow that is the union of the found 312 /// arcdisjoint paths, you may call init() and findFlow(). 476 /// arcdisjoint paths, then you may call findFlow() instead of 477 /// start(). 313 478 314 479 /// @{ … … 330 495 /// \code 331 496 /// s.init(s); 332 /// s.findFlow(t, k); 333 /// s.findPaths(); 497 /// s.start(t, k); 334 498 /// \endcode 335 499 int run(const Node& s, const Node& t, int k = 2) { 336 500 init(s); 337 findFlow(t, k); 338 findPaths(); 501 start(t, k); 339 502 return _path_num; 340 503 } … … 342 505 /// \brief Initialize the algorithm. 343 506 /// 344 /// This function initializes the algorithm .507 /// This function initializes the algorithm with the given source node. 345 508 /// 346 509 /// \param s The source node. 347 510 void init(const Node& s) { 348 _s ource= s;511 _s = s; 349 512 350 513 // Initialize maps … … 357 520 _local_potential = true; 358 521 } 359 for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0; 360 for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0; 522 _full_init = false; 523 } 524 525 /// \brief Initialize the algorithm and perform Dijkstra. 526 /// 527 /// This function initializes the algorithm and performs a full 528 /// Dijkstra search from the given source node. It makes consecutive 529 /// executions of \ref start() "start(t, k)" faster, since they 530 /// have to perform %Dijkstra only k1 times. 531 /// 532 /// This initialization is usually worth using instead of \ref init() 533 /// if the algorithm is executed many times using the same source node. 534 /// 535 /// \param s The source node. 536 void fullInit(const Node& s) { 537 // Initialize maps 538 init(s); 539 if (!_init_dist) { 540 _init_dist = new PotentialMap(_graph); 541 } 542 if (!_init_pred) { 543 _init_pred = new PredMap(_graph); 544 } 545 546 // Run a full Dijkstra 547 typename Dijkstra<Digraph, LengthMap> 548 ::template SetStandardHeap<Heap> 549 ::template SetDistMap<PotentialMap> 550 ::template SetPredMap<PredMap> 551 ::Create dijk(_graph, _length); 552 dijk.distMap(*_init_dist).predMap(*_init_pred); 553 dijk.run(s); 554 555 _full_init = true; 556 } 557 558 /// \brief Execute the algorithm. 559 /// 560 /// This function executes the algorithm. 561 /// 562 /// \param t The target node. 563 /// \param k The number of paths to be found. 564 /// 565 /// \return \c k if there are at least \c k arcdisjoint paths from 566 /// \c s to \c t in the digraph. Otherwise it returns the number of 567 /// arcdisjoint paths found. 568 /// 569 /// \note Apart from the return value, <tt>s.start(t, k)</tt> is 570 /// just a shortcut of the following code. 571 /// \code 572 /// s.findFlow(t, k); 573 /// s.findPaths(); 574 /// \endcode 575 int start(const Node& t, int k = 2) { 576 findFlow(t, k); 577 findPaths(); 578 return _path_num; 361 579 } 362 580 … … 376 594 /// \pre \ref init() must be called before using this function. 377 595 int findFlow(const Node& t, int k = 2) { 378 _target = t; 379 _dijkstra = 380 new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred, 381 _source, _target ); 596 _t = t; 597 ResidualDijkstra dijkstra(*this); 598 599 // Initialization 600 for (ArcIt e(_graph); e != INVALID; ++e) { 601 (*_flow)[e] = 0; 602 } 603 if (_full_init) { 604 for (NodeIt n(_graph); n != INVALID; ++n) { 605 (*_potential)[n] = (*_init_dist)[n]; 606 } 607 Node u = _t; 608 Arc e; 609 while ((e = (*_init_pred)[u]) != INVALID) { 610 (*_flow)[e] = 1; 611 u = _graph.source(e); 612 } 613 _path_num = 1; 614 } else { 615 for (NodeIt n(_graph); n != INVALID; ++n) { 616 (*_potential)[n] = 0; 617 } 618 _path_num = 0; 619 } 382 620 383 621 // Find shortest paths 384 _path_num = 0;385 622 while (_path_num < k) { 386 623 // Run Dijkstra 387 if (! _dijkstra>run()) break;624 if (!dijkstra.run(_path_num)) break; 388 625 ++_path_num; 389 626 390 627 // Set the flow along the found shortest path 391 Node u = _t arget;628 Node u = _t; 392 629 Arc e; 393 630 while ((e = _pred[u]) != INVALID) { … … 406 643 /// \brief Compute the paths from the flow. 407 644 /// 408 /// This function computes the paths from the found minimum cost flow,409 /// which is the union of some arcdisjoint paths.645 /// This function computes arcdisjoint paths from the found minimum 646 /// cost flow, which is the union of them. 410 647 /// 411 648 /// \pre \ref init() and \ref findFlow() must be called before using … … 415 652 for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a]; 416 653 417 paths.clear();418 paths.resize(_path_num);654 _paths.clear(); 655 _paths.resize(_path_num); 419 656 for (int i = 0; i < _path_num; ++i) { 420 Node n = _s ource;421 while (n != _t arget) {657 Node n = _s; 658 while (n != _t) { 422 659 OutArcIt e(_graph, n); 423 660 for ( ; res_flow[e] == 0; ++e) ; 424 661 n = _graph.target(e); 425 paths[i].addBack(e);662 _paths[i].addBack(e); 426 663 res_flow[e] = 0; 427 664 } … … 521 758 /// \pre \ref run() or \ref findPaths() must be called before using 522 759 /// this function. 523 Pathpath(int i) const {524 return paths[i];760 const Path& path(int i) const { 761 return _paths[i]; 525 762 } 526 763
Note: See TracChangeset
for help on using the changeset viewer.