r854:9a7e4e606f83
Fri, 16 Oct 2009 02:32:30
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -28,8 +28,9 @@ |
| 28 | 28 |
#include <limits> |
| 29 | 29 |
#include <lemon/bin_heap.h> |
| 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 {
|
| 35 | 36 |
|
| ... | ... |
@@ -96,18 +97,18 @@ |
| 96 | 97 |
typedef SimplePath<GR> Path; |
| 97 | 98 |
|
| 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 |
| 102 | 106 |
// residual network with respect to the reduced arc lengths |
| 103 | 107 |
// and modifying the node potentials according to the |
| 104 | 108 |
// distance of the nodes. |
| 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 |
|
| 112 | 113 |
const Digraph &_graph; |
| 113 | 114 |
const LengthMap &_length; |
| ... | ... |
@@ -277,8 +278,13 @@ |
| 277 | 278 |
int _path_num; |
| 278 | 279 |
|
| 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: |
| 283 | 289 |
|
| 284 | 290 |
/// \brief Constructor. |
| ... | ... |
@@ -289,15 +295,18 @@ |
| 289 | 295 |
/// \param length The length (cost) values of the arcs. |
| 290 | 296 |
Suurballe( const Digraph &graph, |
| 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 |
|
| 296 | 303 |
/// Destructor. |
| 297 | 304 |
~Suurballe() {
|
| 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 |
|
| 302 | 311 |
/// \brief Set the flow map. |
| 303 | 312 |
/// |
| ... | ... |
@@ -340,12 +349,15 @@ |
| 340 | 349 |
} |
| 341 | 350 |
|
| 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 |
|
| 358 |
/// arc-disjoint paths, then you may call findFlow() instead of |
|
| 359 |
/// start(). |
|
| 348 | 360 |
|
| 349 | 361 |
/// @{
|
| 350 | 362 |
|
| 351 | 363 |
/// \brief Run the algorithm. |
| ... | ... |
@@ -363,21 +375,19 @@ |
| 363 | 375 |
/// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is |
| 364 | 376 |
/// just a shortcut of the following code. |
| 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 |
} |
| 376 | 386 |
|
| 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. |
| 382 | 392 |
void init(const Node& s) {
|
| 383 | 393 |
_s = s; |
| ... | ... |
@@ -390,10 +400,65 @@ |
| 390 | 400 |
if (!_potential) {
|
| 391 | 401 |
_potential = new PotentialMap(_graph); |
| 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 |
|
| 398 | 463 |
/// \brief Execute the algorithm to find an optimal flow. |
| 399 | 464 |
/// |
| ... | ... |
@@ -411,11 +476,32 @@ |
| 411 | 476 |
/// \pre \ref init() must be called before using this function. |
| 412 | 477 |
int findFlow(const Node& t, int k = 2) {
|
| 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 |
| 420 | 506 |
if (!dijkstra.run(_path_num)) break; |
| 421 | 507 |
++_path_num; |
| ... | ... |
@@ -100,8 +100,11 @@ |
| 100 | 100 |
int k; |
| 101 | 101 |
k = suurb_test.run(n, n); |
| 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); |
| 106 | 109 |
suurb_test.findPaths(); |
| 107 | 110 |
|
0 comments (0 inline)