Changeset 206:47f62d789fe7 in lemon0.x for src/work/edmonds_karp.h
 Timestamp:
 03/19/04 10:09:20 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@298
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.h
r198 r206 357 357 } 358 358 } 359 360 bool __augment=true; 361 362 while (__augment) { 363 __augment=false; 364 //computing blocking flow with dfs 365 typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap; 366 DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F); 367 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); 368 pred.set(sF, typename MutableGraph::Edge(INVALID)); 369 //invalid iterators for sources 370 371 typename MutableGraph::NodeMap<Number> free(F); 372 373 dfs.pushAndSetReached(sF); 374 while (!dfs.finished()) { 375 ++dfs; 376 if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) { 377 if (dfs.isBNodeNewlyReached()) { 378 typename MutableGraph::Node v=F.aNode(dfs); 379 typename MutableGraph::Node w=F.bNode(dfs); 380 pred.set(w, dfs); 381 if (F.valid(pred.get(v))) { 382 free.set(w, std::min(free.get(v), residual_capacity.get(dfs))); 383 } else { 384 free.set(w, residual_capacity.get(dfs)); 385 } 386 if (w==tF) { 387 __augment=true; 388 _augment=true; 389 break; 390 } 391 392 } else { 393 F.erase(typename MutableGraph::OutEdgeIt(dfs)); 394 } 395 } 396 } 397 398 if (__augment) { 399 typename MutableGraph::Node n=tF; 400 Number augment_value=free.get(tF); 401 while (F.valid(pred.get(n))) { 402 typename MutableGraph::Edge e=pred.get(n); 403 res_graph.augment(original_edge.get(e), augment_value); 404 n=F.tail(e); 405 if (residual_capacity.get(e)==augment_value) 406 F.erase(e); 407 else 408 residual_capacity.set(e, residual_capacity.get(e)augment_value); 409 } 410 } 411 412 } 413 414 return _augment; 415 } 416 template<typename MutableGraph> bool augmentOnBlockingFlow1() { 417 bool _augment=false; 418 419 AugGraph res_graph(*G, *flow, *capacity); 420 421 //bfs for distances on the residual graph 422 typedef typename AugGraph::NodeMap<bool> ReachedMap; 423 BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph); 424 bfs.pushAndSetReached(s); 425 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 426 427 //F will contain the physical copy of the residual graph 428 //with the set of edges which areon shortest paths 429 MutableGraph F; 430 typename AugGraph::NodeMap<typename MutableGraph::Node> 431 res_graph_to_F(res_graph); 432 for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { 433 res_graph_to_F.set(n, F.addNode()); 434 } 435 typename MutableGraph::Node sF=res_graph_to_F.get(s); 436 typename MutableGraph::Node tF=res_graph_to_F.get(t); 437 typename MutableGraph::EdgeMap<AugEdge> original_edge(F); 438 typename MutableGraph::EdgeMap<Number> residual_capacity(F); 439 440 while ( !bfs.finished() ) { 441 AugOutEdgeIt e=bfs; 442 if (res_graph.valid(e)) { 443 if (bfs.isBNodeNewlyReached()) { 444 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 445 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 446 original_edge.update(); 447 original_edge.set(f, e); 448 residual_capacity.update(); 449 residual_capacity.set(f, res_graph.free(e)); 450 } else { 451 if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) { 452 typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 453 original_edge.update(); 454 original_edge.set(f, e); 455 residual_capacity.update(); 456 residual_capacity.set(f, res_graph.free(e)); 457 } 458 } 459 } 460 ++bfs; 461 } //computing distances from s in the residual graph 359 462 360 463 bool __augment=true;
Note: See TracChangeset
for help on using the changeset viewer.