COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 155:8c6292ec54c6 in lemon-0.x for src/work/edmonds_karp.hh


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

graph wrappers

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/work/edmonds_karp.hh

    r148 r155  
    246246  };
    247247
    248   template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    249   class ResGraphWrapper {
    250   public:
    251     typedef typename Graph::NodeIt NodeIt;
    252     typedef typename Graph::EachNodeIt EachNodeIt;
    253   private:
    254     typedef typename Graph::OutEdgeIt OldOutEdgeIt;
    255     typedef typename Graph::InEdgeIt OldInEdgeIt;
    256     const Graph* G;
    257     FlowMap* flow;
    258     const CapacityMap* capacity;
    259   public:
    260     ResGraphWrapper(const Graph& _G, FlowMap& _flow,
    261              const CapacityMap& _capacity) :
    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) { }
    265     class EdgeIt;
    266     class OutEdgeIt;
    267     friend class EdgeIt;
    268     friend class OutEdgeIt;
    269 
    270     class EdgeIt {
    271       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    272     protected:
    273       //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
    274       const Graph* G;
    275       FlowMap* flow;
    276       const CapacityMap* capacity;
    277       //OldSymEdgeIt sym;
    278       OldOutEdgeIt out;
    279       OldInEdgeIt in;
    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) { }
    285       //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) { }
    286       Number free() const {
    287         if (out_or_in) {
    288           return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
    289         } else {
    290           return (/*resG->*/flow->get(in));
    291         }
    292       }
    293       bool valid() const {
    294         return out_or_in && out.valid() || in.valid(); }
    295       void augment(Number a) const {
    296         if (out_or_in) {
    297           /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
    298         } else {
    299           /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
    300         }
    301       }
    302       void print() {
    303         if (out_or_in) {
    304           std::cout << "out ";
    305           if (out.valid())
    306             std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
    307           else
    308             std::cout << "invalid";
    309         }
    310         else {
    311           std::cout << "in ";
    312           if (in.valid())
    313             std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
    314           else
    315             std::cout << "invalid";
    316         }
    317         std::cout << std::endl;
    318       }
    319     };
    320 
    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 
    328     class OutEdgeIt : public EdgeIt {
    329       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    330     public:
    331       OutEdgeIt() { }
    332     private:
    333       OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
    334         //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
    335         G->getFirst(out, v);
    336         while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    337         if (!out.valid()) {
    338           out_or_in=0;
    339           //in=/*resG->*/G->template first<OldInEdgeIt>(v);
    340           G->getFirst(in, v);
    341           while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    342         }
    343       }
    344     public:
    345       OutEdgeIt& operator++() {
    346         if (out_or_in) {
    347           NodeIt v=/*resG->*/G->aNode(out);
    348           ++out;
    349           while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    350           if (!out.valid()) {
    351             out_or_in=0;
    352             G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
    353             while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    354           }
    355         } else {
    356           ++in;
    357           while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    358         }
    359         return *this;
    360       }
    361     };
    362 
    363     class EachEdgeIt : public EdgeIt {
    364       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    365       typename Graph::EachNodeIt v;
    366     public:
    367       EachEdgeIt() { }
    368       //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
    369       EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
    370         out_or_in=true;
    371         G->getFirst(v);
    372         if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
    373         while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    374         while (v.valid() && !out.valid()) {
    375           ++v;
    376           if (v.valid()) G->getFirst(out, v);
    377           while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    378         }
    379         if (!out.valid()) {
    380           out_or_in=0;
    381           G->getFirst(v);
    382           if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
    383           while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    384           while (v.valid() && !in.valid()) {
    385             ++v;
    386             if (v.valid()) G->getFirst(in, v);
    387             while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    388           }
    389         }
    390       }
    391       EachEdgeIt& operator++() {
    392         if (out_or_in) {
    393           ++out;
    394           while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    395           while (v.valid() && !out.valid()) {
    396             ++v;
    397             if (v.valid()) G->getFirst(out, v);
    398             while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    399           }
    400           if (!out.valid()) {
    401             out_or_in=0;
    402             G->getFirst(v);
    403             if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
    404             while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    405             while (v.valid() && !in.valid()) {
    406               ++v;
    407               if (v.valid()) G->getFirst(in, v);
    408               while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    409             } 
    410           }
    411         } else {
    412           ++in;
    413           while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    414           while (v.valid() && !in.valid()) {
    415             ++v;
    416             if (v.valid()) G->getFirst(in, v);
    417             while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    418           }
    419         }
    420         return *this;
    421       }
    422     };
    423 
    424     void getFirst(EachNodeIt& v) const { G->getFirst(v); }
    425     void getFirst(OutEdgeIt& e, NodeIt v) const {
    426       e=OutEdgeIt(*G, v, *flow, *capacity);
    427     }
    428     void getFirst(EachEdgeIt& e) const {
    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       }
    482    
    483 
    484     template< typename It >
    485     It first() const {
    486       It e;
    487       getFirst(e);
    488       return e;
    489     }
    490 
    491     template< typename It >
    492     It first(NodeIt v) const {
    493       It e;
    494       getFirst(e, v);
    495       return e;
    496     }
    497 
    498     NodeIt tail(EdgeIt e) const {
    499       return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
    500     NodeIt head(EdgeIt e) const {
    501       return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
    502 
    503     NodeIt aNode(OutEdgeIt e) const {
    504       return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
    505     NodeIt bNode(OutEdgeIt e) const {
    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); }
    513 
    514     template <typename T>
    515     class NodeMap {
    516       typename Graph::NodeMap<T> node_map;
    517     public:
    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) { }
    520       void set(NodeIt nit, T a) { node_map.set(nit, a); }
    521       T get(NodeIt nit) const { return node_map.get(nit); }
    522     };
    523 
    524     template <typename T>
    525     class EdgeMap {
    526       typename Graph::EdgeMap<T> forward_map, backward_map;
    527     public:
    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) { }
    530       void set(EdgeIt e, T a) {
    531         if (e.out_or_in)
    532           forward_map.set(e.out, a);
    533         else
    534           backward_map.set(e.in, a);
    535       }
    536       T get(EdgeIt e) {
    537         if (e.out_or_in)
    538           return forward_map.get(e.out);
    539         else
    540           return backward_map.get(e.in);
    541       }
    542     };
    543 
    544   };
    545248
    546249  template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    … …  
    759462
    760463 
    761   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
    762   class MaxFlow2 {
    763   public:
    764     typedef typename Graph::NodeIt NodeIt;
    765     typedef typename Graph::EdgeIt EdgeIt;
    766     typedef typename Graph::EachEdgeIt EachEdgeIt;
    767     typedef typename Graph::OutEdgeIt OutEdgeIt;
    768     typedef typename Graph::InEdgeIt InEdgeIt;
    769   private:
    770     const Graph& G;
    771     std::list<NodeIt>& S;
    772     std::list<NodeIt>& T;
    773     FlowMap& flow;
    774     const CapacityMap& capacity;
    775     typedef ResGraph<Graph, Number, FlowMap, CapacityMap > AugGraph;
    776     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    777     typedef typename AugGraph::EdgeIt AugEdgeIt;
    778     typename Graph::NodeMap<bool> SMap;
    779     typename Graph::NodeMap<bool> TMap;
    780   public:
    781     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) {
    782       for(typename std::list<NodeIt>::const_iterator i=S.begin();
    783           i!=S.end(); ++i) {
    784         SMap.set(*i, true);
    785       }
    786       for (typename std::list<NodeIt>::const_iterator i=T.begin();
    787            i!=T.end(); ++i) {
    788         TMap.set(*i, true);
    789       }
    790     }
    791     bool augment() {
    792       AugGraph res_graph(G, flow, capacity);
    793       bool _augment=false;
    794       NodeIt reached_t_node;
     464//   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     465//   class MaxFlow2 {
     466//   public:
     467//     typedef typename Graph::NodeIt NodeIt;
     468//     typedef typename Graph::EdgeIt EdgeIt;
     469//     typedef typename Graph::EachEdgeIt EachEdgeIt;
     470//     typedef typename Graph::OutEdgeIt OutEdgeIt;
     471//     typedef typename Graph::InEdgeIt InEdgeIt;
     472//   private:
     473//     const Graph& G;
     474//     std::list<NodeIt>& S;
     475//     std::list<NodeIt>& T;
     476//     FlowMap& flow;
     477//     const CapacityMap& capacity;
     478//     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
     479//     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
     480//     typedef typename AugGraph::EdgeIt AugEdgeIt;
     481//     typename Graph::NodeMap<bool> SMap;
     482//     typename Graph::NodeMap<bool> TMap;
     483//   public:
     484//     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) {
     485//       for(typename std::list<NodeIt>::const_iterator i=S.begin();
     486//        i!=S.end(); ++i) {
     487//      SMap.set(*i, true);
     488//       }
     489//       for (typename std::list<NodeIt>::const_iterator i=T.begin();
     490//         i!=T.end(); ++i) {
     491//      TMap.set(*i, true);
     492//       }
     493//     }
     494//     bool augment() {
     495//       AugGraph res_graph(G, flow, capacity);
     496//       bool _augment=false;
     497//       NodeIt reached_t_node;
    795498     
    796       typedef typename AugGraph::NodeMap<bool> ReachedMap;
    797       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
    798       for(typename std::list<NodeIt>::const_iterator i=S.begin();
    799           i!=S.end(); ++i) {
    800         res_bfs.pushAndSetReached(*i);
    801       }
    802       //res_bfs.pushAndSetReached(s);
    803        
    804       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
    805       //filled up with invalid iterators
     499//       typedef typename AugGraph::NodeMap<bool> ReachedMap;
     500//       BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
     501//       for(typename std::list<NodeIt>::const_iterator i=S.begin();
     502//        i!=S.end(); ++i) {
     503//      res_bfs.pushAndSetReached(*i);
     504//       }
     505//       //res_bfs.pushAndSetReached(s);
     506       
     507//       typename AugGraph::NodeMap<AugEdgeIt> pred(res_graph);
     508//       //filled up with invalid iterators
    806509     
    807       typename AugGraph::NodeMap<Number> free(res_graph);
    808        
    809       //searching for augmenting path
    810       while ( !res_bfs.finished() ) {
    811         AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
    812         if (e.valid() && res_bfs.isBNodeNewlyReached()) {
    813           NodeIt v=res_graph.tail(e);
    814           NodeIt w=res_graph.head(e);
    815           pred.set(w, e);
    816           if (pred.get(v).valid()) {
    817             free.set(w, std::min(free.get(v), e.free()));
    818           } else {
    819             free.set(w, e.free());
    820           }
    821           if (TMap.get(res_graph.head(e))) {
    822             _augment=true;
    823             reached_t_node=res_graph.head(e);
    824             break;
    825           }
    826         }
    827        
    828         ++res_bfs;
    829       } //end of searching augmenting path
    830 
    831       if (_augment) {
    832         NodeIt n=reached_t_node;
    833         Number augment_value=free.get(reached_t_node);
    834         while (pred.get(n).valid()) {
    835           AugEdgeIt e=pred.get(n);
    836           e.augment(augment_value);
    837           n=res_graph.tail(e);
    838         }
    839       }
    840 
    841       return _augment;
    842     }
    843     void run() {
    844       while (augment()) { }
    845     }
    846     Number flowValue() {
    847       Number a=0;
    848       for(typename std::list<NodeIt>::const_iterator i=S.begin();
    849           i!=S.end(); ++i) {
    850         for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
    851           a+=flow.get(e);
    852         }
    853         for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
    854           a-=flow.get(e);
    855         }
    856       }
    857       return a;
    858     }
    859   };
     510//       typename AugGraph::NodeMap<Number> free(res_graph);
     511       
     512//       //searching for augmenting path
     513//       while ( !res_bfs.finished() ) {
     514//      AugOutEdgeIt e=/*AugOutEdgeIt*/(res_bfs);
     515//      if (e.valid() && res_bfs.isBNodeNewlyReached()) {
     516//        NodeIt v=res_graph.tail(e);
     517//        NodeIt w=res_graph.head(e);
     518//        pred.set(w, e);
     519//        if (pred.get(v).valid()) {
     520//          free.set(w, std::min(free.get(v), e.free()));
     521//        } else {
     522//          free.set(w, e.free());
     523//        }
     524//        if (TMap.get(res_graph.head(e))) {
     525//          _augment=true;
     526//          reached_t_node=res_graph.head(e);
     527//          break;
     528//        }
     529//      }
     530       
     531//      ++res_bfs;
     532//       } //end of searching augmenting path
     533
     534//       if (_augment) {
     535//      NodeIt n=reached_t_node;
     536//      Number augment_value=free.get(reached_t_node);
     537//      while (pred.get(n).valid()) {
     538//        AugEdgeIt e=pred.get(n);
     539//        e.augment(augment_value);
     540//        n=res_graph.tail(e);
     541//      }
     542//       }
     543
     544//       return _augment;
     545//     }
     546//     void run() {
     547//       while (augment()) { }
     548//     }
     549//     Number flowValue() {
     550//       Number a=0;
     551//       for(typename std::list<NodeIt>::const_iterator i=S.begin();
     552//        i!=S.end(); ++i) {
     553//      for(OutEdgeIt e=G.template first<OutEdgeIt>(*i); e.valid(); ++e) {
     554//        a+=flow.get(e);
     555//      }
     556//      for(InEdgeIt e=G.template first<InEdgeIt>(*i); e.valid(); ++e) {
     557//        a-=flow.get(e);
     558//      }
     559//       }
     560//       return a;
     561//     }
     562//   };
    860563
    861564
Note: See TracChangeset for help on using the changeset viewer.