COIN-OR::LEMON - Graph Library

Changeset 206:47f62d789fe7 in lemon-0.x for src/work/edmonds_karp.h


Ignore:
Timestamp:
03/19/04 10:09:20 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@298
Message:

.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/edmonds_karp.h

    r198 r206  
    357357        }
    358358      }
     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
    359462
    360463      bool __augment=true;
Note: See TracChangeset for help on using the changeset viewer.