Changeset 263:f24f276e0b6b in lemon0.x for src/work/edmonds_karp.h
 Timestamp:
 03/30/04 09:07:44 (20 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@369
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

src/work/edmonds_karp.h
r259 r263 314 314 } 315 315 316 // template<typename MutableGraph> bool augmentOnBlockingFlow() { 317 // bool _augment=false; 318 319 // AugGraph res_graph(*G, *flow, *capacity); 320 321 // typedef typename AugGraph::NodeMap<bool> ReachedMap; 322 // BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph); 323 324 // bfs.pushAndSetReached(s); 325 // typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 326 // while ( !bfs.finished() ) { 327 // AugOutEdgeIt e=bfs; 328 // if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) { 329 // dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 330 // } 331 332 // ++bfs; 333 // } //computing distances from s in the residual graph 334 335 // MutableGraph F; 336 // typename AugGraph::NodeMap<typename MutableGraph::Node> 337 // res_graph_to_F(res_graph); 338 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { 339 // res_graph_to_F.set(n, F.addNode()); 340 // } 341 342 // typename MutableGraph::Node sF=res_graph_to_F.get(s); 343 // typename MutableGraph::Node tF=res_graph_to_F.get(t); 344 345 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); 346 // typename MutableGraph::EdgeMap<Number> residual_capacity(F); 347 348 // //Making F to the graph containing the edges of the residual graph 349 // //which are in some shortest paths 350 // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 351 // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { 352 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 353 // original_edge.update(); 354 // original_edge.set(f, e); 355 // residual_capacity.update(); 356 // residual_capacity.set(f, res_graph.free(e)); 357 // } 358 // } 359 360 // bool __augment=true; 361 362 // while (__augment) { 363 // __augment=false; 364 // //computing blocking flow with dfs 365 // typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; 366 // DfsIterator5< TrivGraphWrapper<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 417 template<typename GraphWrapper> 418 class DistanceMap { 419 protected: 420 GraphWrapper gw; 421 typename GraphWrapper::NodeMap<int> dist; 422 public: 423 DistanceMap(GraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { } 424 //NodeMap(const ListGraph& _G, T a) : 425 //G(_G), container(G.node_id, a) { } 426 void set(const typename GraphWrapper::Node& n, int a) { dist[n]=a; } 427 int get(const typename GraphWrapper::Node& n) const { return dist[n]; } 428 bool get(const typename GraphWrapper::Edge& e) const { 429 return (dist.get(gw.tail(e))<dist.get(gw.head(e))); 430 } 431 //typename std::vector<T>::reference operator[](Node n) { 432 //return container[/*G.id(n)*/n.node>id]; } 433 //typename std::vector<T>::const_reference operator[](Node n) const { 434 //return container[/*G.id(n)*/n.node>id]; 435 }; 436 316 437 template<typename MutableGraph> bool augmentOnBlockingFlow() { 317 438 bool _augment=false; … … 320 441 321 442 typedef typename AugGraph::NodeMap<bool> ReachedMap; 322 BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);443 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); 323 444 324 445 bfs.pushAndSetReached(s); 325 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 446 //typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's 447 DistanceMap<AugGraph> dist(res_graph); 326 448 while ( !bfs.finished() ) { 327 449 AugOutEdgeIt e=bfs; … … 329 451 dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1); 330 452 } 331 332 453 ++bfs; 333 454 } //computing distances from s in the residual graph 334 455 456 // MutableGraph F; 457 // typename AugGraph::NodeMap<typename MutableGraph::Node> 458 // res_graph_to_F(res_graph); 459 // for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) { 460 // res_graph_to_F.set(n, F.addNode()); 461 // } 462 463 // typename MutableGraph::Node sF=res_graph_to_F.get(s); 464 // typename MutableGraph::Node tF=res_graph_to_F.get(t); 465 466 // typename MutableGraph::EdgeMap<AugEdge> original_edge(F); 467 // typename MutableGraph::EdgeMap<Number> residual_capacity(F); 468 469 // //Making F to the graph containing the edges of the residual graph 470 // //which are in some shortest paths 471 // for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) { 472 // if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) { 473 // typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e))); 474 // original_edge.update(); 475 // original_edge.set(f, e); 476 // residual_capacity.update(); 477 // residual_capacity.set(f, res_graph.free(e)); 478 // } 479 // } 480 335 481 MutableGraph F; 482 typedef SubGraphWrapper<AugGraph, DistanceMap<AugGraph> > FilterResGraph; 483 FilterResGraph filter_res_graph(res_graph, dist); 336 484 typename AugGraph::NodeMap<typename MutableGraph::Node> 337 485 res_graph_to_F(res_graph); … … 364 512 //computing blocking flow with dfs 365 513 typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap; 366 DfsIterator5< TrivGraphWrapper<MutableGraph> /*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);514 DfsIterator5< TrivGraphWrapper<MutableGraph>, BlockingReachedMap > dfs(F); 367 515 typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F); 368 516 pred.set(sF, typename MutableGraph::Edge(INVALID)); … … 414 562 return _augment; 415 563 } 564 416 565 template<typename MutableGraph> bool augmentOnBlockingFlow1() { 417 566 bool _augment=false; … … 421 570 //bfs for distances on the residual graph 422 571 typedef typename AugGraph::NodeMap<bool> ReachedMap; 423 BfsIterator5< AugGraph /*, AugOutEdgeIt*/, ReachedMap > bfs(res_graph);572 BfsIterator5< AugGraph, ReachedMap > bfs(res_graph); 424 573 bfs.pushAndSetReached(s); 425 574 typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
Note: See TracChangeset
for help on using the changeset viewer.