COIN-OR::LEMON - Graph Library

Changeset 148:004fdf703abb in lemon-0.x for src/work/edmonds_karp.hh


Ignore:
Timestamp:
03/03/04 15:30:38 (17 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@208
Message:

G.next(...), G.valid(...), ...

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/edmonds_karp.hh

    r141 r148  
    149149      OldOutEdgeIt out;
    150150      OldInEdgeIt in;
    151       bool out_or_in; //1, iff out
    152     public:
    153       EdgeIt() : out_or_in(1) { }
     151      bool out_or_in; //true, iff out
     152    public:
     153      EdgeIt() : out_or_in(true) { }
    154154      Number free() const {
    155155        if (out_or_in) {
     
    247247
    248248  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    249   class ResGraph3 {
     249  class ResGraphWrapper {
    250250  public:
    251251    typedef typename Graph::NodeIt NodeIt;
    252252    typedef typename Graph::EachNodeIt EachNodeIt;
    253 
    254253  private:
    255     //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
    256254    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
    257255    typedef typename Graph::InEdgeIt OldInEdgeIt;
    258     const Graph& G;
    259     FlowMap& flow;
    260     const CapacityMap& capacity;
    261   public:
    262     ResGraph3(const Graph& _G, FlowMap& _flow,
     256    const Graph* G;
     257    FlowMap* flow;
     258    const CapacityMap* capacity;
     259  public:
     260    ResGraphWrapper(const Graph& _G, FlowMap& _flow,
    263261             const CapacityMap& _capacity) :
    264       G(_G), flow(_flow), capacity(_capacity) { }
    265 
     262      G(&_G), flow(&_flow), capacity(&_capacity) { }
     263//     ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
     264//       G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
    266265    class EdgeIt;
    267266    class OutEdgeIt;
     
    270269
    271270    class EdgeIt {
    272       friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
     271      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    273272    protected:
    274273      //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
     
    279278      OldOutEdgeIt out;
    280279      OldInEdgeIt in;
    281       bool out_or_in; //1, iff out
    282     public:
    283       EdgeIt() : out_or_in(1) { }
     280      bool out_or_in; //true, iff out
     281    public:
     282      EdgeIt() : out_or_in(true) { }
     283      EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :
     284        G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
    284285      //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
    285286      Number free() const {
     
    318319    };
    319320
     321    Number free(OldOutEdgeIt out) const {
     322      return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
     323    }
     324    Number free(OldInEdgeIt in) const {
     325      return (/*resG->*/flow->get(in));
     326    }
     327
    320328    class OutEdgeIt : public EdgeIt {
    321       friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
     329      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    322330    public:
    323331      OutEdgeIt() { }
    324332    private:
    325       OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) {
    326         G=&_G;
    327         flow=&_flow;
    328         capacity=&_capacity;
     333      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
    329334        //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
    330335        G->getFirst(out, v);
    331         while( out.valid() && !(free()>0) ) { ++out; }
     336        while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    332337        if (!out.valid()) {
    333338          out_or_in=0;
    334339          //in=/*resG->*/G->template first<OldInEdgeIt>(v);
    335340          G->getFirst(in, v);
    336           while( in.valid() && !(free()>0) ) { ++in; }
     341          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    337342        }
    338343      }
     
    342347          NodeIt v=/*resG->*/G->aNode(out);
    343348          ++out;
    344           while( out.valid() && !(free()>0) ) { ++out; }
     349          while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    345350          if (!out.valid()) {
    346351            out_or_in=0;
    347352            G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
    348             while( in.valid() && !(free()>0) ) { ++in; }
     353            while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    349354          }
    350355        } else {
    351356          ++in;
    352           while( in.valid() && !(free()>0) ) { ++in; }
     357          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    353358        }
    354359        return *this;
     
    357362
    358363    class EachEdgeIt : public EdgeIt {
     364      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    359365      typename Graph::EachNodeIt v;
    360366    public:
    361367      EachEdgeIt() { }
    362368      //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
    363       EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) {
    364         G=&_G;
    365         flow=&_flow;
    366         capacity=&_capacity;
    367         out_or_in=1;
     369      EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
     370        out_or_in=true;
    368371        G->getFirst(v);
    369372        if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
    370         while (out.valid() && !(free()>0) ) { ++out; }
     373        while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    371374        while (v.valid() && !out.valid()) {
    372375          ++v;
    373376          if (v.valid()) G->getFirst(out, v);
    374           while (out.valid() && !(free()>0) ) { ++out; }
     377          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    375378        }
    376379        if (!out.valid()) {
     
    378381          G->getFirst(v);
    379382          if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
    380           while (in.valid() && !(free()>0) ) { ++in; }
     383          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    381384          while (v.valid() && !in.valid()) {
    382385            ++v;
    383386            if (v.valid()) G->getFirst(in, v);
    384             while (in.valid() && !(free()>0) ) { ++in; }
     387            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    385388          }
    386389        }
     
    389392        if (out_or_in) {
    390393          ++out;
    391           while (out.valid() && !(free()>0) ) { ++out; }
     394          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    392395          while (v.valid() && !out.valid()) {
    393396            ++v;
    394397            if (v.valid()) G->getFirst(out, v);
    395             while (out.valid() && !(free()>0) ) { ++out; }
     398            while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    396399          }
    397400          if (!out.valid()) {
     
    399402            G->getFirst(v);
    400403            if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
    401             while (in.valid() && !(free()>0) ) { ++in; }
     404            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    402405            while (v.valid() && !in.valid()) {
    403406              ++v;
    404407              if (v.valid()) G->getFirst(in, v);
    405               while (in.valid() && !(free()>0) ) { ++in; }
     408              while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    406409            } 
    407410          }
    408411        } else {
    409412          ++in;
    410           while (in.valid() && !(free()>0) ) { ++in; }
     413          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    411414          while (v.valid() && !in.valid()) {
    412415            ++v;
    413416            if (v.valid()) G->getFirst(in, v);
    414             while (in.valid() && !(free()>0) ) { ++in; }
     417            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    415418          }
    416419        }
     
    419422    };
    420423
     424    void getFirst(EachNodeIt& v) const { G->getFirst(v); }
    421425    void getFirst(OutEdgeIt& e, NodeIt v) const {
    422       e=OutEdgeIt(G, v, flow, capacity);
     426      e=OutEdgeIt(*G, v, *flow, *capacity);
    423427    }
    424428    void getFirst(EachEdgeIt& e) const {
    425       e=EachEdgeIt(G, flow, capacity);
    426     }
    427     void getFirst(EachNodeIt& v) const { G.getFirst(v); }
     429      e=EachEdgeIt(*G, *flow, *capacity);
     430    }
     431   
     432    EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
     433
     434    OutEdgeIt& next(OutEdgeIt& e) const {
     435      if (e.out_or_in) {
     436        NodeIt v=G->aNode(e.out);
     437        ++(e.out);
     438        while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
     439        if (!G->valid(e.out)) {
     440          e.out_or_in=0;
     441          G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
     442          while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     443        }
     444      } else {
     445        ++(e.in);
     446        while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     447      }
     448      return e;
     449    }
     450
     451    EachEdgeIt& next(EachEdgeIt& e) const {
     452      if (e.out_or_in) {
     453        ++(e.out);
     454        while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
     455          while (G->valid(e.v) && !G->valid(e.out)) {
     456            ++(e.v);
     457            if (G->valid(e.v)) G->getFirst(e.out, e.v);
     458            while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
     459          }
     460          if (!G->valid(e.out)) {
     461            e.out_or_in=0;
     462            G->getFirst(e.v);
     463            if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
     464            while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     465            while (G->valid(e.v) && !G->valid(e.in)) {
     466              ++(e.v);
     467              if (G->valid(e.v)) G->getFirst(e.in, e.v);
     468              while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     469            } 
     470          }
     471        } else {
     472          ++(e.in);
     473          while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     474          while (G->valid(e.v) && !G->valid(e.in)) {
     475            ++(e.v);
     476            if (G->valid(e.v)) G->getFirst(e.in, e.v);
     477            while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     478          }
     479        }
     480        return e;
     481      }
    428482   
     483
    429484    template< typename It >
    430485    It first() const {
     
    442497
    443498    NodeIt tail(EdgeIt e) const {
    444       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
     499      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
    445500    NodeIt head(EdgeIt e) const {
    446       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
     501      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
    447502
    448503    NodeIt aNode(OutEdgeIt e) const {
    449       return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
     504      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
    450505    NodeIt bNode(OutEdgeIt e) const {
    451       return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
    452 
    453     int id(NodeIt v) const { return G.id(v); }
     506      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
     507
     508    int id(NodeIt v) const { return G->id(v); }
     509
     510    bool valid(NodeIt n) const { return G->valid(n); }
     511    bool valid(EdgeIt e) const {
     512      return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
    454513
    455514    template <typename T>
     
    457516      typename Graph::NodeMap<T> node_map;
    458517    public:
    459       NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
    460       NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(_G.G, a) { }
     518      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }
     519      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }
    461520      void set(NodeIt nit, T a) { node_map.set(nit, a); }
    462521      T get(NodeIt nit) const { return node_map.get(nit); }
     
    467526      typename Graph::EdgeMap<T> forward_map, backward_map;
    468527    public:
    469       EdgeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(_G.G), backward_map(_G.G) { }
    470       EdgeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(_G.G, a), backward_map(_G.G, a) { }
     528      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { }
     529      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { }
    471530      void set(EdgeIt e, T a) {
    472531        if (e.out_or_in)
     
    495554
    496555  private:
    497     const Graph& G;
     556    const Graph* G;
    498557    NodeIt s;
    499558    NodeIt t;
    500     FlowMap& flow;
    501     const CapacityMap& capacity;
    502     typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;
     559    FlowMap* flow;
     560    const CapacityMap* capacity;
     561    typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
    503562    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    504563    typedef typename AugGraph::EdgeIt AugEdgeIt;
     
    510569  public:
    511570    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
    512       G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //, 
     571      G(&_G), s(_s), t(_t), flow(&_flow), capacity(&_capacity) //, 
    513572      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
    514573      { }
    515574    bool augmentOnShortestPath() {
    516       AugGraph res_graph(G, flow, capacity);
     575      AugGraph res_graph(*G, *flow, *capacity);
    517576      bool _augment=false;
    518577     
    519578      typedef typename AugGraph::NodeMap<bool> ReachedMap;
    520       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
     579      BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
    521580      res_bfs.pushAndSetReached(s);
    522581       
     
    530589      while ( !res_bfs.finished() ) {
    531590        AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
    532         if (e.valid() && res_bfs.isBNodeNewlyReached()) {
     591        if (res_graph.valid(e) && res_bfs.isBNodeNewlyReached()) {
    533592          NodeIt v=res_graph.tail(e);
    534593          NodeIt w=res_graph.head(e);
    535594          pred.set(w, e);
    536           if (pred.get(v).valid()) {
     595          if (res_graph.valid(pred.get(v))) {
    537596            free.set(w, std::min(free.get(v), e.free()));
    538597          } else {
     
    548607        NodeIt n=t;
    549608        Number augment_value=free.get(t);
    550         while (pred.get(n).valid()) {
     609        while (res_graph.valid(pred.get(n))) {
    551610          AugEdgeIt e=pred.get(n);
    552611          e.augment(augment_value);
     
    561620      bool _augment=false;
    562621
    563       AugGraph res_graph(G, flow, capacity);
     622      AugGraph res_graph(*G, *flow, *capacity);
    564623
    565624      typedef typename AugGraph::NodeMap<bool> ReachedMap;
     
    570629      while ( !bfs.finished() ) {
    571630        AugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
    572         if (e.valid() && bfs.isBNodeNewlyReached()) {
     631        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    573632          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    574633        }
     
    579638      MutableGraph F;
    580639      typename AugGraph::NodeMap<NodeIt> res_graph_to_F(res_graph);
    581       for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); n.valid(); ++n) {
     640      for(typename AugGraph::EachNodeIt n=res_graph.template first<typename AugGraph::EachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
    582641        res_graph_to_F.set(n, F.addNode());
    583642      }
     
    587646
    588647      typename MutableGraph::EdgeMap<AugEdgeIt> original_edge(F);
    589       typename MutableGraph::EdgeMap<Number> free_on_edge(F);
     648      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
    590649
    591650      //Making F to the graph containing the edges of the residual graph
    592651      //which are in some shortest paths
    593       for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); e.valid(); ++e) {
     652      for(typename AugGraph::EachEdgeIt e=res_graph.template first<typename AugGraph::EachEdgeIt>(); res_graph.valid(e); res_graph.next(e)) {
    594653        if (dist.get(res_graph.head(e))==dist.get(res_graph.tail(e))+1) {
    595654          typename MutableGraph::EdgeIt f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    596655          original_edge.update();
    597656          original_edge.set(f, e);
    598           free_on_edge.update();
    599           free_on_edge.set(f, e.free());
     657          residual_capacity.update();
     658          residual_capacity.set(f, e.free());
    600659        }
    601660      }
     
    614673        while (!dfs.finished()) {
    615674          ++dfs;
    616           if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
     675          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
    617676            //std::cout << "OutEdgeIt: " << dfs;
    618677            //std::cout << " aNode: " << F.aNode(dfs);
     
    622681            typename MutableGraph::NodeIt w=F.bNode(dfs);
    623682            pred.set(w, dfs);
    624             if (pred.get(v).valid()) {
    625               free.set(w, std::min(free.get(v), free_on_edge.get(dfs)));
     683            if (F.valid(pred.get(v))) {
     684              free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
    626685            } else {
    627               free.set(w, free_on_edge.get(dfs)/*original_edge.get(dfs).free()*/);
     686              free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/);
    628687            }
    629688            if (w==tF) {
     
    658717          typename MutableGraph::NodeIt n=tF;
    659718          Number augment_value=free.get(tF);
    660           while (pred.get(n).valid()) {
     719          while (F.valid(pred.get(n))) {
    661720            typename MutableGraph::EdgeIt e=pred.get(n);
    662721            original_edge.get(e).augment(augment_value);
    663722            n=F.tail(e);
    664             if (free_on_edge.get(e)==augment_value)
     723            if (residual_capacity.get(e)==augment_value)
    665724              F.erase(e);
    666725            else
    667               free_on_edge.set(e, free_on_edge.get(e)-augment_value);
     726              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
    668727          }
    669728        }
     
    691750    Number flowValue() {
    692751      Number a=0;
    693       for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
    694         a+=flow.get(i);
     752      OutEdgeIt e;
     753      for(G->getFirst(e, s); G->valid(e); G->next(e)) {
     754        a+=flow->get(e);
    695755      }
    696756      return a;
    697757    }
    698758  };
    699 
    700 
    701 /*
    702   template <typename Graph>
    703   class IteratorBoolNodeMap {
    704     typedef typename Graph::NodeIt NodeIt;
    705     typedef typename Graph::EachNodeIt EachNodeIt;
    706     class BoolItem {
    707     public:
    708       bool value;
    709       NodeIt prev;
    710       NodeIt next;
    711       BoolItem() : value(false), prev(), next() {}
    712     };
    713     NodeIt first_true;
    714     //NodeIt last_true;
    715     NodeIt first_false;
    716     //NodeIt last_false;
    717     const Graph& G;
    718     typename Graph::NodeMap<BoolItem> container;
    719   public:
    720     typedef bool ValueType;
    721     typedef NodeIt KeyType;
    722     IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) {
    723       //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
    724       //BoolItem b=container.get(e);
    725       //b.me=e;
    726       //container.set(b);
    727       //}
    728       G.getFirst(first_false);
    729       NodeIt e_prev;
    730       for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
    731         container[e].prev=e_prev;
    732         if (e_prev.valid()) container[e_prev].next=e;
    733         e_prev=e;
    734       }
    735     }
    736     //NodeMap(const Graph& _G, T a) :
    737     //  G(_G), container(G.node_id, a) { }
    738     //FIXME
    739     void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
    740     T get(NodeIt nit) const { return container[G.id(nit)]; }
    741     //void update() { container.resize(G.node_id); }
    742     //void update(T a) { container.resize(G.node_id, a); }
    743   };
    744 */
    745759
    746760 
Note: See TracChangeset for help on using the changeset viewer.