COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 75:87623302a68f in lemon-0.x for src/work/edmonds_karp.hh


Ignore:
Timestamp:
02/16/04 12:29:48 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@98
Message:

.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/work/edmonds_karp.hh

    r69 r75  
    33
    44#include <algorithm>
     5#include <list>
     6#include <iterator>
    57
    68#include <bfs_iterator.hh>
    … …  
    810namespace marci {
    911
    10   template<typename Graph, typename T, typename FlowMap, typename CapacityMap>
     12  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    1113  class ResGraph {
    1214    typedef typename Graph::NodeIt NodeIt;
    … …  
    2729
    2830    class EdgeIt {
    29       friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
     31      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
    3032    protected:
    31       const ResGraph<Graph, T, FlowMap, CapacityMap>* resG;
     33      const ResGraph<Graph, Number, FlowMap, CapacityMap>* resG;
    3234      OldSymEdgeIt sym;
    3335    public:
    3436      EdgeIt() { }
    3537      //EdgeIt(const EdgeIt& e) : resG(e.resG), sym(e.sym) { }
    36       T free() const {
     38      Number free() const {
    3739        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
    3840          return (resG->capacity.get(sym)-resG->flow.get(sym));
    … …  
    4244      }
    4345      bool valid() const { return sym.valid(); }
    44       void augment(T a) const {
     46      void augment(Number a) const {
    4547        if (resG->G.aNode(sym)==resG->G.tail(sym)) {
    4648          resG->flow.set(sym, resG->flow.get(sym)+a);
     49          //resG->flow[sym]+=a;
    4750        } else {
    4851          resG->flow.set(sym, resG->flow.get(sym)-a);
     52          //resG->flow[sym]-=a;
    4953        }
    5054      }
    … …  
    5256
    5357    class OutEdgeIt : public EdgeIt {
    54       friend class ResGraph<Graph, T, FlowMap, CapacityMap>;
     58      friend class ResGraph<Graph, Number, FlowMap, CapacityMap>;
    5559    public:
    5660      OutEdgeIt() { }
    5761      //OutEdgeIt(const OutEdgeIt& e) { resG=e.resG; sym=e.sym; }
    5862    private:
    59       OutEdgeIt(const ResGraph<Graph, T, FlowMap, CapacityMap>& _resG, NodeIt v) {
     63      OutEdgeIt(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
    6064        resG=&_resG;
    6165        sym=resG->G.template first<OldSymEdgeIt>(v);
    … …  
    6670        ++sym;
    6771        while( sym.valid() && !(free()>0) ) { ++sym; }
     72        return *this;
     73      }
     74    };
     75
     76    void getFirst(OutEdgeIt& e, NodeIt v) const {
     77      e=OutEdgeIt(*this, v);
     78    }
     79    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
     80   
     81    template< typename It >
     82    It first() const {
     83      It e;     
     84      getFirst(e);
     85      return e;
     86    }
     87
     88    template< typename It >
     89    It first(NodeIt v) const {
     90      It e;
     91      getFirst(e, v);
     92      return e;
     93    }
     94
     95    NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
     96    NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
     97
     98    NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
     99    NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
     100
     101    int id(NodeIt v) const { return G.id(v); }
     102
     103    template <typename S>
     104    class NodeMap {
     105      typename Graph::NodeMap<S> node_map;
     106    public:
     107      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
     108      NodeMap(const ResGraph<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
     109      void set(NodeIt nit, S a) { node_map.set(nit, a); }
     110      S get(NodeIt nit) const { return node_map.get(nit); }
     111      S& operator[](NodeIt nit) { return node_map[nit]; }
     112      const S& operator[](NodeIt nit) const { return node_map[nit]; }
     113    };
     114
     115  };
     116
     117
     118  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     119  class ResGraph2 {
     120    typedef typename Graph::NodeIt NodeIt;
     121    typedef typename Graph::EachNodeIt EachNodeIt;
     122    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
     123    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
     124    typedef typename Graph::InEdgeIt OldInEdgeIt;
     125   
     126    const Graph& G;
     127    FlowMap& flow;
     128    const CapacityMap& capacity;
     129  public:
     130    ResGraph2(const Graph& _G, FlowMap& _flow,
     131             const CapacityMap& _capacity) :
     132      G(_G), flow(_flow), capacity(_capacity) { }
     133
     134    class EdgeIt;
     135    class OutEdgeIt;
     136    friend class EdgeIt;
     137    friend class OutEdgeIt;
     138
     139    class EdgeIt {
     140      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
     141    protected:
     142      const ResGraph2<Graph, Number, FlowMap, CapacityMap>* resG;
     143      //OldSymEdgeIt sym;
     144      OldOutEdgeIt out;
     145      OldInEdgeIt in;
     146      bool out_or_in; //1, iff out
     147    public:
     148      EdgeIt() : out_or_in(1) { }
     149      Number free() const {
     150        if (out_or_in) {
     151          return (resG->capacity.get(out)-resG->flow.get(out));
     152        } else {
     153          return (resG->flow.get(in));
     154        }
     155      }
     156      bool valid() const {
     157        return out_or_in && out.valid() || in.valid(); }
     158      void augment(Number a) const {
     159        if (out_or_in) {
     160          resG->flow.set(out, resG->flow.get(out)+a);
     161        } else {
     162          resG->flow.set(in, resG->flow.get(in)-a);
     163        }
     164      }
     165    };
     166
     167    class OutEdgeIt : public EdgeIt {
     168      friend class ResGraph2<Graph, Number, FlowMap, CapacityMap>;
     169    public:
     170      OutEdgeIt() { }
     171    private:
     172      OutEdgeIt(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _resG, NodeIt v) {
     173        resG=&_resG;
     174        out=resG->G.template first<OldOutEdgeIt>(v);
     175        while( out.valid() && !(free()>0) ) { ++out; }
     176        if (!out.valid()) {
     177          out_or_in=0;
     178          in=resG->G.template first<OldInEdgeIt>(v);
     179          while( in.valid() && !(free()>0) ) { ++in; }
     180        }
     181      }
     182    public:
     183      OutEdgeIt& operator++() {
     184        if (out_or_in) {
     185          NodeIt v=resG->G.aNode(out);
     186          ++out;
     187          while( out.valid() && !(free()>0) ) { ++out; }
     188          if (!out.valid()) {
     189            out_or_in=0;
     190            in=resG->G.template first<OldInEdgeIt>(v);
     191            while( in.valid() && !(free()>0) ) { ++in; }
     192          }
     193        } else {
     194          ++in;
     195          while( in.valid() && !(free()>0) ) { ++in; }
     196        }
    68197        return *this;
    69198      }
    … …  
    89218    }
    90219
    91     NodeIt tail(EdgeIt e) const { return G.aNode(e.sym); }
    92     NodeIt head(EdgeIt e) const { return G.bNode(e.sym); }
    93 
    94     NodeIt aNode(OutEdgeIt e) const { return G.aNode(e.sym); }
    95     NodeIt bNode(OutEdgeIt e) const { return G.bNode(e.sym); }
     220    NodeIt tail(EdgeIt e) const {
     221      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
     222    NodeIt head(EdgeIt e) const {
     223      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
     224
     225    NodeIt aNode(OutEdgeIt e) const {
     226      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
     227    NodeIt bNode(OutEdgeIt e) const {
     228      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
    96229
    97230    int id(NodeIt v) const { return G.id(v); }
    … …  
    101234      typename Graph::NodeMap<S> node_map;
    102235    public:
    103       NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
    104       NodeMap(const ResGraph<Graph, T, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
     236      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
     237      NodeMap(const ResGraph2<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
    105238      void set(NodeIt nit, S a) { node_map.set(nit, a); }
    106239      S get(NodeIt nit) const { return node_map.get(nit); }
    107240    };
    108 
    109241  };
    110242
    111   template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
     243  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     244  class ResGraph3 {
     245    typedef typename Graph::NodeIt NodeIt;
     246    typedef typename Graph::EachNodeIt EachNodeIt;
     247    //typedef typename Graph::SymEdgeIt OldSymEdgeIt;
     248    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
     249    typedef typename Graph::InEdgeIt OldInEdgeIt;
     250   
     251    const Graph& G;
     252    FlowMap& flow;
     253    const CapacityMap& capacity;
     254  public:
     255    ResGraph3(const Graph& _G, FlowMap& _flow,
     256             const CapacityMap& _capacity) :
     257      G(_G), flow(_flow), capacity(_capacity) { }
     258
     259    class EdgeIt;
     260    class OutEdgeIt;
     261    friend class EdgeIt;
     262    friend class OutEdgeIt;
     263
     264    class EdgeIt {
     265      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
     266    protected:
     267      //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
     268      const Graph* G;
     269      FlowMap* flow;
     270      const CapacityMap* capacity;
     271      //OldSymEdgeIt sym;
     272      OldOutEdgeIt out;
     273      OldInEdgeIt in;
     274      bool out_or_in; //1, iff out
     275    public:
     276      EdgeIt() : out_or_in(1) { }
     277      Number free() const {
     278        if (out_or_in) {
     279          return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
     280        } else {
     281          return (/*resG->*/flow->get(in));
     282        }
     283      }
     284      bool valid() const {
     285        return out_or_in && out.valid() || in.valid(); }
     286      void augment(Number a) const {
     287        if (out_or_in) {
     288          /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
     289        } else {
     290          /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
     291        }
     292      }
     293    };
     294
     295    class OutEdgeIt : public EdgeIt {
     296      friend class ResGraph3<Graph, Number, FlowMap, CapacityMap>;
     297    public:
     298      OutEdgeIt() { }
     299    private:
     300      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) {
     301        G=&_G;
     302        flow=&_flow;
     303        capacity=&_capacity;
     304        out=/*resG->*/G->template first<OldOutEdgeIt>(v);
     305        while( out.valid() && !(free()>0) ) { ++out; }
     306        if (!out.valid()) {
     307          out_or_in=0;
     308          in=/*resG->*/G->template first<OldInEdgeIt>(v);
     309          while( in.valid() && !(free()>0) ) { ++in; }
     310        }
     311      }
     312    public:
     313      OutEdgeIt& operator++() {
     314        if (out_or_in) {
     315          NodeIt v=/*resG->*/G->aNode(out);
     316          ++out;
     317          while( out.valid() && !(free()>0) ) { ++out; }
     318          if (!out.valid()) {
     319            out_or_in=0;
     320            in=/*resG->*/G->template first<OldInEdgeIt>(v);
     321            while( in.valid() && !(free()>0) ) { ++in; }
     322          }
     323        } else {
     324          ++in;
     325          while( in.valid() && !(free()>0) ) { ++in; }
     326        }
     327        return *this;
     328      }
     329    };
     330
     331    void getFirst(OutEdgeIt& e, NodeIt v) const {
     332      e=OutEdgeIt(G, v, flow, capacity);
     333    }
     334    void getFirst(EachNodeIt& v) const { G.getFirst(v); }
     335   
     336    template< typename It >
     337    It first() const {
     338      It e;
     339      getFirst(e);
     340      return e;
     341    }
     342
     343    template< typename It >
     344    It first(NodeIt v) const {
     345      It e;
     346      getFirst(e, v);
     347      return e;
     348    }
     349
     350    NodeIt tail(EdgeIt e) const {
     351      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
     352    NodeIt head(EdgeIt e) const {
     353      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
     354
     355    NodeIt aNode(OutEdgeIt e) const {
     356      return ((e.out_or_in) ? G.aNode(e.out) : G.aNode(e.in)); }
     357    NodeIt bNode(OutEdgeIt e) const {
     358      return ((e.out_or_in) ? G.bNode(e.out) : G.bNode(e.in)); }
     359
     360    int id(NodeIt v) const { return G.id(v); }
     361
     362    template <typename S>
     363    class NodeMap {
     364      typename Graph::NodeMap<S> node_map;
     365    public:
     366      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(_G.G) { }
     367      NodeMap(const ResGraph3<Graph, Number, FlowMap, CapacityMap>& _G, S a) : node_map(_G.G, a) { }
     368      void set(NodeIt nit, S a) { node_map.set(nit, a); }
     369      S get(NodeIt nit) const { return node_map.get(nit); }
     370    };
     371
     372  };
     373
     374
     375  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    112376  class MaxFlow {
    113377    typedef typename Graph::NodeIt NodeIt;
    … …  
    121385    FlowMap& flow;
    122386    const CapacityMap& capacity;
    123     typedef ResGraph<Graph, T, FlowMap, CapacityMap > AugGraph;
     387    typedef ResGraph3<Graph, Number, FlowMap, CapacityMap > AugGraph;
    124388    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    125389    typedef typename AugGraph::EdgeIt AugEdgeIt;
     390
     391    //AugGraph res_graph;   
     392    //typedef typename AugGraph::NodeMap<bool> ReachedMap;
     393    //typename AugGraph::NodeMap<AugEdgeIt> pred;
     394    //typename AugGraph::NodeMap<int> free;
    126395  public:
    127     MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) { }
     396    MaxFlow(const Graph& _G, NodeIt _s, NodeIt _t, FlowMap& _flow, const CapacityMap& _capacity) :
     397      G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) //, 
     398      //res_graph(G, flow, capacity), pred(res_graph), free(res_graph)
     399      { }
    128400    bool augment() {
    129401      AugGraph res_graph(G, flow, capacity);
    … …  
    131403     
    132404      typedef typename AugGraph::NodeMap<bool> ReachedMap;
    133       BfsIterator2< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
     405      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
    134406      res_bfs.pushAndSetReached(s);
    135407       
    136408      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
    137       //filled with invalid iterators
     409      //filled up with invalid iterators
     410      //pred.set(s, AugEdgeIt());
    138411     
    139412      typename AugGraph::NodeMap<int> free(res_graph);
    … …  
    159432      if (_augment) {
    160433        NodeIt n=t;
    161         T augment_value=free.get(t);
     434        Number augment_value=free.get(t);
    162435        while (pred.get(n).valid()) {
    163436          AugEdgeIt e=pred.get(n);
    … …  
    172445      while (augment()) { }
    173446    }
    174     T flowValue() {
    175       T a=0;
     447    Number flowValue() {
     448      Number a=0;
    176449      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) {
    177450        a+=flow.get(i);
    … …  
    181454  };
    182455
     456
     457/*
     458  template <typename Graph>
     459  class IteratorBoolNodeMap {
     460    typedef typename Graph::NodeIt NodeIt;
     461    typedef typename Graph::EachNodeIt EachNodeIt;
     462    class BoolItem {
     463    public:
     464      bool value;
     465      NodeIt prev;
     466      NodeIt next;
     467      BoolItem() : value(false), prev(), next() {}
     468    };
     469    NodeIt first_true;
     470    //NodeIt last_true;
     471    NodeIt first_false;
     472    //NodeIt last_false;
     473    const Graph& G;
     474    typename Graph::NodeMap<BoolItem> container;
     475  public:
     476    typedef bool ValueType;
     477    typedef NodeIt KeyType;
     478    IteratorBoolNodeMap(const Graph& _G) : G(_G), container(G), first_true(NodeIt()) {
     479      //for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
     480      //BoolItem b=container.get(e);
     481      //b.me=e;
     482      //container.set(b);
     483      //}
     484      G.getFirst(first_false);
     485      NodeIt e_prev;
     486      for (EachNodeIt e=G.template first<EacNodeIt>(); e.valid(); ++e) {
     487        container[e].prev=e_prev;
     488        if (e_prev.valid()) container[e_prev].next=e;
     489        e_prev=e;
     490      }
     491    }
     492    //NodeMap(const Graph& _G, T a) :
     493    //  G(_G), container(G.node_id, a) { }
     494    //FIXME
     495    void set(NodeIt nit, T a) { container[G.id(nit)]=a; }
     496    T get(NodeIt nit) const { return container[G.id(nit)]; }
     497    //void resize() { container.resize(G.node_id); }
     498    //void resize(T a) { container.resize(G.node_id, a); }
     499  };
     500*/
     501
     502 
     503  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     504  class MaxFlow2 {
     505    typedef typename Graph::NodeIt NodeIt;
     506    typedef typename Graph::EdgeIt EdgeIt;
     507    typedef typename Graph::EachEdgeIt EachEdgeIt;
     508    typedef typename Graph::OutEdgeIt OutEdgeIt;
     509    typedef typename Graph::InEdgeIt InEdgeIt;
     510    const Graph& G;
     511    std::list<NodeIt>& S;
     512    std::list<NodeIt>& T;
     513    FlowMap& flow;
     514    const CapacityMap& capacity;
     515    typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;
     516    typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
     517    typedef typename AugGraph::EdgeIt AugEdgeIt;
     518    typename Graph::NodeMap<bool> SMap;
     519    typename Graph::NodeMap<bool> TMap;
     520  public:
     521    MaxFlow2(const Graph& _G, std::list<NodeIt>& _S, std::list<NodeIt>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
     522      for(typename std::list<NodeIt>::const_iterator i=S.begin();
     523          i!=S.end(); ++i) {
     524        SMap.set(*i, true);
     525      }
     526      for (typename std::list<NodeIt>::const_iterator i=T.begin();
     527           i!=T.end(); ++i) {
     528        TMap.set(*i, true);
     529      }
     530    }
     531    bool augment() {
     532      AugGraph res_graph(G, flow, capacity);
     533      bool _augment=false;
     534      NodeIt reached_t_node;
     535     
     536      typedef typename AugGraph::NodeMap<bool> ReachedMap;
     537      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
     538      for(typename std::list<NodeIt>::const_iterator i=S.begin();
     539          i!=S.end(); ++i) {
     540        res_bfs.pushAndSetReached(*i);
     541      }
     542      //res_bfs.pushAndSetReached(s);
     543       
     544      typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
     545      //filled up with invalid iterators
     546     
     547      typename AugGraph::NodeMap<int> free(res_graph);
     548       
     549      //searching for augmenting path
     550      while ( !res_bfs.finished() ) {
     551        AugOutEdgeIt e=AugOutEdgeIt(res_bfs);
     552        if (e.valid() && res_bfs.isBNodeNewlyReached()) {
     553          NodeIt v=res_graph.tail(e);
     554          NodeIt w=res_graph.head(e);
     555          pred.set(w, e);
     556          if (pred.get(v).valid()) {
     557            free.set(w, std::min(free.get(v), e.free()));
     558          } else {
     559            free.set(w, e.free());
     560          }
     561          if (TMap.get(res_graph.head(e))) {
     562            _augment=true;
     563            reached_t_node=res_graph.head(e);
     564            break;
     565          }
     566        }
     567       
     568        ++res_bfs;
     569      } //end of searching augmenting path
     570
     571      if (_augment) {
     572        NodeIt n=reached_t_node;
     573        Number augment_value=free.get(reached_t_node);
     574        while (pred.get(n).valid()) {
     575          AugEdgeIt e=pred.get(n);
     576          e.augment(augment_value);
     577          n=res_graph.tail(e);
     578        }
     579      }
     580
     581      return _augment;
     582    }
     583    void run() {
     584      while (augment()) { }
     585    }
     586    Number flowValue() {
     587      Number a=0;
     588      for(typename std::list<NodeIt>::const_iterator i=S.begin();
     589          i!=S.end(); ++i) {
     590        for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
     591          a+=flow.get(e);
     592        }
     593        for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
     594          a-=flow.get(e);
     595        }
     596      }
     597      return a;
     598    }
     599  };
     600
     601
     602
    183603} // namespace marci
    184604
Note: See TracChangeset for help on using the changeset viewer.