Changeset 927:9a7e4e606f83 in lemon
- Timestamp:
- 10/16/09 02:32:30 (15 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/suurballe.h
r926 r927 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 … … 98 99 private: 99 100 101 typedef typename Digraph::template NodeMap<int> HeapCrossRef; 102 typedef BinHeap<Length, HeapCrossRef> Heap; 103 100 104 // ResidualDijkstra is a special implementation of the 101 105 // Dijkstra algorithm for finding shortest paths in the … … 105 109 class ResidualDijkstra 106 110 { 107 typedef typename Digraph::template NodeMap<int> HeapCrossRef;108 typedef BinHeap<Length, HeapCrossRef> Heap;109 110 111 private: 111 112 … … 279 280 // The pred arc map 280 281 PredMap _pred; 282 283 // Data for full init 284 PotentialMap *_init_dist; 285 PredMap *_init_pred; 286 bool _full_init; 281 287 282 288 public: … … 291 297 const LengthMap &length ) : 292 298 _graph(graph), _length(length), _flow(0), _local_flow(false), 293 _potential(0), _local_potential(false), _pred(graph) 299 _potential(0), _local_potential(false), _pred(graph), 300 _init_dist(0), _init_pred(0) 294 301 {} 295 302 … … 298 305 if (_local_flow) delete _flow; 299 306 if (_local_potential) delete _potential; 307 delete _init_dist; 308 delete _init_pred; 300 309 } 301 310 … … 342 351 /// \name Execution Control 343 352 /// The simplest way to execute the algorithm is to call the run() 344 /// function. 345 /// \n 353 /// function.\n 354 /// If you need to execute the algorithm many times using the same 355 /// source node, then you may call fullInit() once and start() 356 /// for each target node.\n 346 357 /// If you only need the flow that is the union of the found 347 /// arc-disjoint paths, you may call init() and findFlow(). 358 /// arc-disjoint paths, then you may call findFlow() instead of 359 /// start(). 348 360 349 361 /// @{ … … 365 377 /// \code 366 378 /// s.init(s); 367 /// s.findFlow(t, k); 368 /// s.findPaths(); 379 /// s.start(t, k); 369 380 /// \endcode 370 381 int run(const Node& s, const Node& t, int k = 2) { 371 382 init(s); 372 findFlow(t, k); 373 findPaths(); 383 start(t, k); 374 384 return _path_num; 375 385 } … … 377 387 /// \brief Initialize the algorithm. 378 388 /// 379 /// This function initializes the algorithm .389 /// This function initializes the algorithm with the given source node. 380 390 /// 381 391 /// \param s The source node. … … 392 402 _local_potential = true; 393 403 } 394 for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0; 395 for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0; 404 _full_init = false; 405 } 406 407 /// \brief Initialize the algorithm and perform Dijkstra. 408 /// 409 /// This function initializes the algorithm and performs a full 410 /// Dijkstra search from the given source node. It makes consecutive 411 /// executions of \ref start() "start(t, k)" faster, since they 412 /// have to perform %Dijkstra only k-1 times. 413 /// 414 /// This initialization is usually worth using instead of \ref init() 415 /// if the algorithm is executed many times using the same source node. 416 /// 417 /// \param s The source node. 418 void fullInit(const Node& s) { 419 // Initialize maps 420 init(s); 421 if (!_init_dist) { 422 _init_dist = new PotentialMap(_graph); 423 } 424 if (!_init_pred) { 425 _init_pred = new PredMap(_graph); 426 } 427 428 // Run a full Dijkstra 429 typename Dijkstra<Digraph, LengthMap> 430 ::template SetStandardHeap<Heap> 431 ::template SetDistMap<PotentialMap> 432 ::template SetPredMap<PredMap> 433 ::Create dijk(_graph, _length); 434 dijk.distMap(*_init_dist).predMap(*_init_pred); 435 dijk.run(s); 436 437 _full_init = true; 438 } 439 440 /// \brief Execute the algorithm. 441 /// 442 /// This function executes the algorithm. 443 /// 444 /// \param t The target node. 445 /// \param k The number of paths to be found. 446 /// 447 /// \return \c k if there are at least \c k arc-disjoint paths from 448 /// \c s to \c t in the digraph. Otherwise it returns the number of 449 /// arc-disjoint paths found. 450 /// 451 /// \note Apart from the return value, <tt>s.start(t, k)</tt> is 452 /// just a shortcut of the following code. 453 /// \code 454 /// s.findFlow(t, k); 455 /// s.findPaths(); 456 /// \endcode 457 int start(const Node& t, int k = 2) { 458 findFlow(t, k); 459 findPaths(); 460 return _path_num; 396 461 } 397 462 … … 413 478 _t = t; 414 479 ResidualDijkstra dijkstra(*this); 480 481 // Initialization 482 for (ArcIt e(_graph); e != INVALID; ++e) { 483 (*_flow)[e] = 0; 484 } 485 if (_full_init) { 486 for (NodeIt n(_graph); n != INVALID; ++n) { 487 (*_potential)[n] = (*_init_dist)[n]; 488 } 489 Node u = _t; 490 Arc e; 491 while ((e = (*_init_pred)[u]) != INVALID) { 492 (*_flow)[e] = 1; 493 u = _graph.source(e); 494 } 495 _path_num = 1; 496 } else { 497 for (NodeIt n(_graph); n != INVALID; ++n) { 498 (*_potential)[n] = 0; 499 } 500 _path_num = 0; 501 } 415 502 416 503 // Find shortest paths 417 _path_num = 0;418 504 while (_path_num < k) { 419 505 // Run Dijkstra -
test/suurballe_test.cc
r670 r927 102 102 k = suurb_test.run(n, n, k); 103 103 suurb_test.init(n); 104 suurb_test.fullInit(n); 105 suurb_test.start(n); 106 suurb_test.start(n, k); 104 107 k = suurb_test.findFlow(n); 105 108 k = suurb_test.findFlow(n, k);
Note: See TracChangeset
for help on using the changeset viewer.