COIN-OR::LEMON - Graph Library

Changeset 198:5cec393baade in lemon-0.x for src/work/edmonds_karp.h


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

max cardinality bipartite matching demo, something to play with it

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/edmonds_karp.h

    r197 r198  
    552552    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    553553    typedef typename AugGraph::Edge AugEdge;
     554    typename Graph::NodeMap<int> used; //0
    554555
    555556  public:
    556557    MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
    557       G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity) { }
     558      G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
    558559    bool augmentOnShortestPath() {
    559560      AugGraph res_graph(*G, *flow, *capacity);
     
    564565      typename AugGraph::NodeMap<AugEdge> pred(res_graph);
    565566      for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
    566         if (S->get(s)) {
    567           Number u=0;
    568           for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
    569             u+=flow->get(e);
    570           if (u<1) {
     567        if ((S->get(s)) && (used.get(s)<1) ) {
     568          //Number u=0;
     569          //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
     570          //u+=flow->get(e);
     571          //if (u<1) {
    571572            res_bfs.pushAndSetReached(s);
    572573            pred.set(s, AugEdge(INVALID));
    573           }
     574            //}
    574575        }
    575576      }
     
    591592          }
    592593          n=res_graph.head(e);
    593           if (T->get(n)) {
    594             Number u=0;
    595             for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
    596               u+=flow->get(f);
    597             if (u<1) {
     594          if (T->get(n) && (used.get(n)<1) ) {
     595            //Number u=0;
     596            //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
     597            //u+=flow->get(f);
     598            //if (u<1) {
    598599              _augment=true;
    599600              break;
    600             }
     601              //}
    601602          }
    602603        }
     
    607608      if (_augment) {
    608609        //Node n=t;
     610        used.set(n, 1); //mind2 vegen jav
    609611        Number augment_value=free.get(n);
    610612        while (res_graph.valid(pred.get(n))) {
     
    613615          n=res_graph.tail(e);
    614616        }
     617        used.set(n, 1); //mind2 vegen jav
    615618      }
    616619
Note: See TracChangeset for help on using the changeset viewer.