COIN-OR::LEMON - Graph Library

Changeset 303:1b377a730d02 in lemon-0.x for src/work/marci/edmonds_karp.h


Ignore:
Timestamp:
04/05/04 18:52:46 (16 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@421
Message:

konvergalunk, konvergalunk...

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/edmonds_karp.h

    r301 r303  
    99#include <bfs_iterator.h>
    1010#include <invalid.h>
     11#include <graph_wrapper.h>
    1112
    1213namespace hugo {
     
    248249
    249250
    250   template <typename GraphWrapper, typename Number, typename FlowMap, typename CapacityMap>
     251  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    251252  class MaxFlow {
    252253  protected:
    253     typedef GraphWrapper GW;
    254     typedef typename GW::Node Node;
    255     typedef typename GW::Edge Edge;
    256     typedef typename GW::EdgeIt EdgeIt;
    257     typedef typename GW::OutEdgeIt OutEdgeIt;
    258     typedef typename GW::InEdgeIt InEdgeIt;
    259     //const Graph* G;
    260     GW gw;
     254    typedef typename Graph::Node Node;
     255    typedef typename Graph::Edge Edge;
     256    typedef typename Graph::EdgeIt EdgeIt;
     257    typedef typename Graph::OutEdgeIt OutEdgeIt;
     258    typedef typename Graph::InEdgeIt InEdgeIt;
     259    const Graph* g;
    261260    Node s;
    262261    Node t;
    263262    FlowMap* flow;
    264263    const CapacityMap* capacity;
    265     typedef ResGraphWrapper<GW, Number, FlowMap, CapacityMap > ResGW;
     264    typedef ResGraphWrapper<const Graph, Number, FlowMap, CapacityMap > ResGW;
    266265    typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
    267266    typedef typename ResGW::Edge ResGWEdge;
    268267  public:
    269268
    270     MaxFlow(const GW& _gw, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
    271       gw(_gw), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
     269    MaxFlow(const Graph& _g, Node _s, Node _t, FlowMap& _flow, const CapacityMap& _capacity) :
     270      g(&_g), s(_s), t(_t), flow(&_flow), capacity(&_capacity) { }
    272271
    273272    bool augmentOnShortestPath() {
    274       ResGW res_graph(gw, *flow, *capacity);
     273      ResGW res_graph(*g, *flow, *capacity);
    275274      bool _augment=false;
    276275     
     
    291290          Node w=res_graph.head(e);
    292291          pred.set(w, e);
    293           if (res_graph.valid(pred.get(v))) {
    294             free.set(w, std::min(free.get(v), res_graph.resCap(e)));
     292          if (res_graph.valid(pred[v])) {
     293            free.set(w, std::min(free[v], res_graph.resCap(e)));
    295294          } else {
    296295            free.set(w, res_graph.resCap(e));
     
    304303      if (_augment) {
    305304        Node n=t;
    306         Number augment_value=free.get(t);
    307         while (res_graph.valid(pred.get(n))) {
    308           ResGWEdge e=pred.get(n);
     305        Number augment_value=free[t];
     306        while (res_graph.valid(pred[n])) {
     307          ResGWEdge e=pred[n];
    309308          res_graph.augment(e, augment_value);
    310309          n=res_graph.tail(e);
     
    318317    class DistanceMap {
    319318    protected:
    320       MapGraphWrapper gw;
     319      const MapGraphWrapper* g;
    321320      typename MapGraphWrapper::NodeMap<int> dist;
    322321    public:
    323       DistanceMap(MapGraphWrapper& _gw) : gw(_gw), dist(_gw, _gw.nodeNum()) { }
     322      DistanceMap(MapGraphWrapper& _g) : g(&_g), dist(*g, g->nodeNum()) { }
    324323      void set(const typename MapGraphWrapper::Node& n, int a) { dist[n]=a; }
    325       int get(const typename MapGraphWrapper::Node& n) const { return dist[n]; }
    326       bool get(const typename MapGraphWrapper::Edge& e) const {
    327         return (dist.get(gw.tail(e))<dist.get(gw.head(e)));
     324      int operator[](const typename MapGraphWrapper::Node& n)
     325        { return dist[n]; }
     326//       int get(const typename MapGraphWrapper::Node& n) const {
     327//      return dist[n]; }
     328//       bool get(const typename MapGraphWrapper::Edge& e) const {
     329//      return (dist.get(g->tail(e))<dist.get(g->head(e))); }
     330      bool operator[](const typename MapGraphWrapper::Edge& e) const {
     331        return (dist[g->tail(e)]<dist[g->head(e)]);
    328332      }
    329333    };
     
    333337      bool _augment=false;
    334338
    335       ResGW res_graph(gw, *flow, *capacity);
     339      ResGW res_graph(*g, *flow, *capacity);
    336340
    337341      typedef typename ResGW::NodeMap<bool> ReachedMap;
     
    344348        ResGWOutEdgeIt e=bfs;
    345349        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    346           dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     350          dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
    347351        }
    348352        ++bfs;
     
    360364      }
    361365
    362       typename MG::Node sF=res_graph_to_F.get(s);
    363       typename MG::Node tF=res_graph_to_F.get(t);
     366      typename MG::Node sF=res_graph_to_F[s];
     367      typename MG::Node tF=res_graph_to_F[t];
    364368      typename MG::EdgeMap<ResGWEdge> original_edge(F);
    365369      typename MG::EdgeMap<Number> residual_capacity(F);
     
    371375        for(filter_res_graph.first(e); filter_res_graph.valid(e); filter_res_graph.next(e)) {
    372376          //if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
    373           typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     377          typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
    374378          original_edge.update();
    375379          original_edge.set(f, e);
     
    401405              typename MG::Node w=F.bNode(dfs);
    402406              pred.set(w, dfs);
    403               if (F.valid(pred.get(v))) {
    404                 free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
     407              if (F.valid(pred[v])) {
     408                free.set(w, std::min(free[v], residual_capacity[dfs]));
    405409              } else {
    406                 free.set(w, residual_capacity.get(dfs));
     410                free.set(w, residual_capacity[dfs]);
    407411              }
    408412              if (w==tF) {
     
    420424        if (__augment) {
    421425          typename MG::Node n=tF;
    422           Number augment_value=free.get(tF);
    423           while (F.valid(pred.get(n))) {
    424             typename MG::Edge e=pred.get(n);
    425             res_graph.augment(original_edge.get(e), augment_value);
     426          Number augment_value=free[tF];
     427          while (F.valid(pred[n])) {
     428            typename MG::Edge e=pred[n];
     429            res_graph.augment(original_edge[e], augment_value);
    426430            n=F.tail(e);
    427             if (residual_capacity.get(e)==augment_value)
     431            if (residual_capacity[e]==augment_value)
    428432              F.erase(e);
    429433            else
    430               residual_capacity.set(e, residual_capacity.get(e)-augment_value);
     434              residual_capacity.set(e, residual_capacity[e]-augment_value);
    431435          }
    432436        }
     
    441445      bool _augment=false;
    442446
    443       ResGW res_graph(gw, *flow, *capacity);
     447      ResGW res_graph(*g, *flow, *capacity);
    444448
    445449      //bfs for distances on the residual graph
     
    460464      }
    461465
    462       typename MG::Node sF=res_graph_to_F.get(s);
    463       typename MG::Node tF=res_graph_to_F.get(t);
     466      typename MG::Node sF=res_graph_to_F[s];
     467      typename MG::Node tF=res_graph_to_F[t];
    464468      typename MG::EdgeMap<ResGWEdge> original_edge(F);
    465469      typename MG::EdgeMap<Number> residual_capacity(F);
     
    469473        if (res_graph.valid(e)) {
    470474          if (bfs.isBNodeNewlyReached()) {
    471             dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    472             typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     475            dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
     476            typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
    473477            original_edge.update();
    474478            original_edge.set(f, e);
     
    476480            residual_capacity.set(f, res_graph.resCap(e));
    477481          } else {
    478             if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
    479               typename MG::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     482            if (dist[res_graph.head(e)]==(dist[res_graph.tail(e)]+1)) {
     483              typename MG::Edge f=F.addEdge(res_graph_to_F[res_graph.tail(e)], res_graph_to_F[res_graph.head(e)]);
    480484              original_edge.update();
    481485              original_edge.set(f, e);
     
    509513              typename MG::Node w=F.bNode(dfs);
    510514              pred.set(w, dfs);
    511               if (F.valid(pred.get(v))) {
    512                 free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
     515              if (F.valid(pred[v])) {
     516                free.set(w, std::min(free[v], residual_capacity[dfs]));
    513517              } else {
    514                 free.set(w, residual_capacity.get(dfs));
     518                free.set(w, residual_capacity[dfs]);
    515519              }
    516520              if (w==tF) {
     
    528532        if (__augment) {
    529533          typename MG::Node n=tF;
    530           Number augment_value=free.get(tF);
    531           while (F.valid(pred.get(n))) {
    532             typename MG::Edge e=pred.get(n);
    533             res_graph.augment(original_edge.get(e), augment_value);
     534          Number augment_value=free[tF];
     535          while (F.valid(pred[n])) {
     536            typename MG::Edge e=pred[n];
     537            res_graph.augment(original_edge[e], augment_value);
    534538            n=F.tail(e);
    535             if (residual_capacity.get(e)==augment_value)
     539            if (residual_capacity[e]==augment_value)
    536540              F.erase(e);
    537541            else
    538               residual_capacity.set(e, residual_capacity.get(e)-augment_value);
     542              residual_capacity.set(e, residual_capacity[e]-augment_value);
    539543          }
    540544        }
     
    548552      bool _augment=false;
    549553
    550       ResGW res_graph(gw, *flow, *capacity);
     554      ResGW res_graph(*g, *flow, *capacity);
    551555
    552556      typedef typename ResGW::NodeMap<bool> ReachedMap;
     
    558562        ResGWOutEdgeIt e=bfs;
    559563        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    560           dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     564          dist.set(res_graph.head(e), dist[res_graph.tail(e)]+1);
    561565        }
    562566        ++bfs;
     
    611615
    612616              pred.set(w, /*typename ErasingResGW::OutEdgeIt*/(dfs));
    613               if (erasing_res_graph.valid(pred.get(v))) {
    614                 free.set(w, std::min(free.get(v), res_graph.resCap(dfs)));
     617              if (erasing_res_graph.valid(pred[v])) {
     618                free.set(w, std::min(free[v], res_graph.resCap(dfs)));
    615619              } else {
    616620                free.set(w, res_graph.resCap(dfs));
     
    630634        if (__augment) {
    631635          typename ErasingResGW::Node n=t;
    632           Number augment_value=free.get(n);
    633           while (erasing_res_graph.valid(pred.get(n))) {
    634             typename ErasingResGW::OutEdgeIt e=pred.get(n);
     636          Number augment_value=free[n];
     637          while (erasing_res_graph.valid(pred[n])) {
     638            typename ErasingResGW::OutEdgeIt e=pred[n];
    635639            res_graph.augment(e, augment_value);
    636640            n=erasing_res_graph.tail(e);
     
    645649    }
    646650
    647 //     bool augmentOnBlockingFlow2() {
    648 //       bool _augment=false;
    649 
    650 //       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
    651 //       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
    652 //       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
    653 //       typedef typename EAugGraph::Edge EAugEdge;
    654 
    655 //       EAugGraph res_graph(*G, *flow, *capacity);
    656 
    657 //       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
    658 //       BfsIterator5<
    659 //      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
    660 //      /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
    661 //      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
    662      
    663 //       bfs.pushAndSetReached(s);
    664 
    665 //       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
    666 //      NodeMap<int>& dist=res_graph.dist;
    667 
    668 //       while ( !bfs.finished() ) {
    669 //      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
    670 //      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    671 //        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    672 //      }
    673 //      ++bfs; 
    674 //       } //computing distances from s in the residual graph
    675 
    676 //       bool __augment=true;
    677 
    678 //       while (__augment) {
    679 
    680 //      __augment=false;
    681 //      //computing blocking flow with dfs
    682 //      typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
    683 //      DfsIterator5< EAugGraph/*, EAugOutEdgeIt*/, BlockingReachedMap >
    684 //        dfs(res_graph);
    685 //      typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
    686 //      pred.set(s, EAugEdge(INVALID));
    687 //      //invalid iterators for sources
    688 
    689 //      typename EAugGraph::NodeMap<Number> free(res_graph);
    690 
    691 //      dfs.pushAndSetReached(s);
    692 //      while (!dfs.finished()) {
    693 //        ++dfs;
    694 //        if (res_graph.valid(EAugOutEdgeIt(dfs))) {
    695 //          if (dfs.isBNodeNewlyReached()) {
    696          
    697 //            typename EAugGraph::Node v=res_graph.aNode(dfs);
    698 //            typename EAugGraph::Node w=res_graph.bNode(dfs);
    699 
    700 //            pred.set(w, EAugOutEdgeIt(dfs));
    701 //            if (res_graph.valid(pred.get(v))) {
    702 //              free.set(w, std::min(free.get(v), res_graph.free(dfs)));
    703 //            } else {
    704 //              free.set(w, res_graph.free(dfs));
    705 //            }
    706              
    707 //            if (w==t) {
    708 //              __augment=true;
    709 //              _augment=true;
    710 //              break;
    711 //            }
    712 //          } else {
    713 //            res_graph.erase(dfs);
    714 //          }
    715 //        }
    716 
    717 //      }
    718 
    719 //      if (__augment) {
    720 //        typename EAugGraph::Node n=t;
    721 //        Number augment_value=free.get(t);
    722 //        while (res_graph.valid(pred.get(n))) {
    723 //          EAugEdge e=pred.get(n);
    724 //          res_graph.augment(e, augment_value);
    725 //          n=res_graph.tail(e);
    726 //          if (res_graph.free(e)==0)
    727 //            res_graph.erase(e);
    728 //        }
    729 //      }
    730      
    731 //       }
    732            
    733 //       return _augment;
    734 //     }
    735 
    736651    void run() {
    737652      //int num_of_augmentations=0;
     
    755670      Number a=0;
    756671      OutEdgeIt e;
    757       for(gw.first(e, s); gw.valid(e); gw.next(e)) {
    758         a+=flow->get(e);
     672      for(g->first(e, s); g->valid(e); g->next(e)) {
     673        a+=(*flow)[e];
    759674      }
    760675      return a;
Note: See TracChangeset for help on using the changeset viewer.