COIN-OR::LEMON - Graph Library

Changeset 193:84c19824322a in lemon-0.x for src/work


Ignore:
Timestamp:
03/17/04 16:01:04 (21 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@270
Message:

.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/edmonds_karp.h

    r191 r193  
    527527    }
    528528  };
     529
     530
     531  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     532  class MaxMatching {
     533  public:
     534    typedef typename Graph::Node Node;
     535    typedef typename Graph::Edge Edge;
     536    typedef typename Graph::EdgeIt EdgeIt;
     537    typedef typename Graph::OutEdgeIt OutEdgeIt;
     538    typedef typename Graph::InEdgeIt InEdgeIt;
     539
     540    typedef typename Graph::NodeMap<bool> SMap;
     541    typedef typename Graph::NodeMap<bool> TMap;
     542  private:
     543    const Graph* G;
     544    SMap* S;
     545    TMap* T;
     546    //Node s;
     547    //Node t;
     548    FlowMap* flow;
     549    const CapacityMap* capacity;
     550    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
     551    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
     552    typedef typename AugGraph::Edge AugEdge;
     553
     554  public:
     555    MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
     556      G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { }
     557    bool augmentOnShortestPath() {
     558      AugGraph res_graph(*G, *flow, *capacity);
     559      bool _augment=false;
     560     
     561      typedef typename AugGraph::NodeMap<bool> ReachedMap;
     562      BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
     563      typename AugGraph::NodeMap<AugEdge> pred(res_graph);
     564      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
     565        Number f=0;
     566        for(OutEdgeIt e=G->template first<OutEdgeIt>(); G->valid(e); G->next(e))
     567          f+=flow->get(e);
     568        if (f<1) {
     569          res_bfs.pushAndSetReached(s);
     570          pred.set(s, AugEdge(INVALID));
     571        }
     572      }
     573     
     574      typename AugGraph::NodeMap<Number> free(res_graph);
     575       
     576      Node n;
     577      //searching for augmenting path
     578      while ( !res_bfs.finished() ) {
     579        AugOutEdgeIt e=res_bfs;
     580        if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
     581          Node v=res_graph.tail(e);
     582          Node w=res_graph.head(e);
     583          pred.set(w, e);
     584          if (res_graph.valid(pred.get(v))) {
     585            free.set(w, std::min(free.get(v), res_graph.free(e)));
     586          } else {
     587            free.set(w, res_graph.free(e));
     588          }
     589          if (TMap(res_graph.head(e))) {
     590            n=res_graph.head(e);
     591            _augment=true;
     592            break;
     593          }
     594        }
     595       
     596        ++res_bfs;
     597      } //end of searching augmenting path
     598
     599      if (_augment) {
     600        //Node n=t;
     601        Number augment_value=free.get(t);
     602        while (res_graph.valid(pred.get(n))) {
     603          AugEdge e=pred.get(n);
     604          res_graph.augment(e, augment_value);
     605          n=res_graph.tail(e);
     606        }
     607      }
     608
     609      return _augment;
     610    }
     611
     612//     template<typename MutableGraph> bool augmentOnBlockingFlow() {     
     613//       bool _augment=false;
     614
     615//       AugGraph res_graph(*G, *flow, *capacity);
     616
     617//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
     618//       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
     619
     620//       bfs.pushAndSetReached(s);
     621//       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
     622//       while ( !bfs.finished() ) {
     623//      AugOutEdgeIt e=bfs;
     624//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     625//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     626//      }
     627       
     628//      ++bfs;
     629//       } //computing distances from s in the residual graph
     630
     631//       MutableGraph F;
     632//       typename AugGraph::NodeMap<typename MutableGraph::Node>
     633//      res_graph_to_F(res_graph);
     634//       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
     635//      res_graph_to_F.set(n, F.addNode());
     636//       }
     637     
     638//       typename MutableGraph::Node sF=res_graph_to_F.get(s);
     639//       typename MutableGraph::Node tF=res_graph_to_F.get(t);
     640
     641//       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
     642//       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
     643
     644//       //Making F to the graph containing the edges of the residual graph
     645//       //which are in some shortest paths
     646//       for(typename AugGraph::EdgeIt e=res_graph.template first<typename AugGraph::EdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
     647//      if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
     648//        typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     649//        original_edge.update();
     650//        original_edge.set(f, e);
     651//        residual_capacity.update();
     652//        residual_capacity.set(f, res_graph.free(e));
     653//      }
     654//       }
     655
     656//       bool __augment=true;
     657
     658//       while (__augment) {
     659//      __augment=false;
     660//      //computing blocking flow with dfs
     661//      typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
     662//      DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
     663//      typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
     664//      pred.set(sF, typename MutableGraph::Edge(INVALID));
     665//      //invalid iterators for sources
     666
     667//      typename MutableGraph::NodeMap<Number> free(F);
     668
     669//      dfs.pushAndSetReached(sF);     
     670//      while (!dfs.finished()) {
     671//        ++dfs;
     672//        if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
     673//          if (dfs.isBNodeNewlyReached()) {
     674//            typename MutableGraph::Node v=F.aNode(dfs);
     675//            typename MutableGraph::Node w=F.bNode(dfs);
     676//            pred.set(w, dfs);
     677//            if (F.valid(pred.get(v))) {
     678//              free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
     679//            } else {
     680//              free.set(w, residual_capacity.get(dfs));
     681//            }
     682//            if (w==tF) {
     683//              __augment=true;
     684//              _augment=true;
     685//              break;
     686//            }
     687             
     688//          } else {
     689//            F.erase(typename MutableGraph::OutEdgeIt(dfs));
     690//          }
     691//        }
     692//      }
     693
     694//      if (__augment) {
     695//        typename MutableGraph::Node n=tF;
     696//        Number augment_value=free.get(tF);
     697//        while (F.valid(pred.get(n))) {
     698//          typename MutableGraph::Edge e=pred.get(n);
     699//          res_graph.augment(original_edge.get(e), augment_value);
     700//          n=F.tail(e);
     701//          if (residual_capacity.get(e)==augment_value)
     702//            F.erase(e);
     703//          else
     704//            residual_capacity.set(e, residual_capacity.get(e)-augment_value);
     705//        }
     706//      }
     707       
     708//       }
     709           
     710//       return _augment;
     711//     }
     712//     bool augmentOnBlockingFlow2() {
     713//       bool _augment=false;
     714
     715//       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
     716//       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
     717//       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
     718//       typedef typename EAugGraph::Edge EAugEdge;
     719
     720//       EAugGraph res_graph(*G, *flow, *capacity);
     721
     722//       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
     723//       BfsIterator4<
     724//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
     725//      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
     726//      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
     727     
     728//       bfs.pushAndSetReached(s);
     729
     730//       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
     731//      NodeMap<int>& dist=res_graph.dist;
     732
     733//       while ( !bfs.finished() ) {
     734//      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
     735//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     736//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     737//      }
     738//      ++bfs; 
     739//       } //computing distances from s in the residual graph
     740
     741//       bool __augment=true;
     742
     743//       while (__augment) {
     744
     745//      __augment=false;
     746//      //computing blocking flow with dfs
     747//      typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
     748//      DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
     749//        dfs(res_graph);
     750//      typename EAugGraph::NodeMap<EAugEdge> pred(res_graph);
     751//      pred.set(s, EAugEdge(INVALID));
     752//      //invalid iterators for sources
     753
     754//      typename EAugGraph::NodeMap<Number> free(res_graph);
     755
     756//      dfs.pushAndSetReached(s);
     757//      while (!dfs.finished()) {
     758//        ++dfs;
     759//        if (res_graph.valid(EAugOutEdgeIt(dfs))) {
     760//          if (dfs.isBNodeNewlyReached()) {
     761         
     762//            typename EAugGraph::Node v=res_graph.aNode(dfs);
     763//            typename EAugGraph::Node w=res_graph.bNode(dfs);
     764
     765//            pred.set(w, EAugOutEdgeIt(dfs));
     766//            if (res_graph.valid(pred.get(v))) {
     767//              free.set(w, std::min(free.get(v), res_graph.free(dfs)));
     768//            } else {
     769//              free.set(w, res_graph.free(dfs));
     770//            }
     771             
     772//            if (w==t) {
     773//              __augment=true;
     774//              _augment=true;
     775//              break;
     776//            }
     777//          } else {
     778//            res_graph.erase(dfs);
     779//          }
     780//        }
     781
     782//      }
     783
     784//      if (__augment) {
     785//        typename EAugGraph::Node n=t;
     786//        Number augment_value=free.get(t);
     787//        while (res_graph.valid(pred.get(n))) {
     788//          EAugEdge e=pred.get(n);
     789//          res_graph.augment(e, augment_value);
     790//          n=res_graph.tail(e);
     791//          if (res_graph.free(e)==0)
     792//            res_graph.erase(e);
     793//        }
     794//      }
     795     
     796//       }
     797           
     798//       return _augment;
     799//     }
     800    void run() {
     801      //int num_of_augmentations=0;
     802      while (augmentOnShortestPath()) {
     803        //while (augmentOnBlockingFlow<MutableGraph>()) {
     804        //std::cout << ++num_of_augmentations << " ";
     805        //std::cout<<std::endl;
     806      }
     807    }
     808    template<typename MutableGraph> void run() {
     809      //int num_of_augmentations=0;
     810      //while (augmentOnShortestPath()) {
     811        while (augmentOnBlockingFlow<MutableGraph>()) {
     812        //std::cout << ++num_of_augmentations << " ";
     813        //std::cout<<std::endl;
     814      }
     815    }
     816    Number flowValue() {
     817      Number a=0;
     818      OutEdgeIt e;
     819      for(G->/*getF*/first(e, s); G->valid(e); G->next(e)) {
     820        a+=flow->get(e);
     821      }
     822      return a;
     823    }
     824  };
     825
     826
     827
     828
    529829
    530830 
Note: See TracChangeset for help on using the changeset viewer.