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


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

graph wrappers

Location:
src/work
Files:
5 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

  • src/work/makefile

    r149 r155  
    22CXXFLAGS = -g -O -Wall $(INCLUDEDIRS) -ansi -pedantic
    33
    4 BINARIES ?= bin_heap_demo marci_graph_demo iterator_bfs_dfs_demo graphdemo bfsdemo bfsdemo2
     4BINARIES ?= bin_heap_demo marci_graph_demo iterator_bfs_dfs_demo
    55
    66# Hat, ez elismerem, hogy nagyon ronda, de mukodik minden altalam

  • src/work/marci/edmonds_karp_demo.cc

    r146 r155  
    66#include <edmonds_karp.hh>
    77#include <time_measure.h>
     8#include <graph_wrapper.h>
    89
    910using namespace hugo;
    … …  
    5859  ListGraph::EdgeMap<int> cap(G);
    5960  readDimacsMaxFlow(std::cin, G, s, t, cap);
     61/*
     62  typedef TrivGraphWrapper<ListGraph> TGW;
     63  TGW gw(G);
     64  TGW::EachNodeIt sw;
     65  gw.getFirst(sw);
     66  std::cout << "p1:" << gw.nodeNum() << std::endl;
     67  gw.erase(sw);
     68  std::cout << "p2:" << gw.nodeNum() << std::endl;
     69
     70  typedef const ListGraph cLG;
     71  typedef TrivGraphWrapper<const cLG> CTGW;
     72  CTGW cgw(G);
     73  CTGW::EachNodeIt csw;
     74  cgw.getFirst(csw);
     75  std::cout << "p1:" << cgw.nodeNum() << std::endl;
     76  //cgw.erase(csw);
     77  std::cout << "p2:" << cgw.nodeNum() << std::endl;
     78*/
    6079
    6180  {

  • src/work/marci/graph_wrapper.h

    r148 r155  
    1313
    1414    typedef typename Graph::NodeIt NodeIt;
     15    typedef typename Graph::EachNodeIt EachNodeIt;
     16
    1517    typedef typename Graph::EdgeIt EdgeIt;
    16  
    17     typedef typename Graph::EachNodeIt EachNodeIt;
    18 
    1918    typedef typename Graph::OutEdgeIt OutEdgeIt;
    2019    typedef typename Graph::InEdgeIt InEdgeIt;
    21     typedef typename Graph::SymEdgeIt SymEdgeIt;
     20    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    2221    typedef typename Graph::EachEdgeIt EachEdgeIt;
    23 
    24     int nodeNum() const { return graph->nodeNum(); }
    25     int edgeNum() const { return graph->edgeNum(); }
    2622   
    2723    template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
    2824    template<typename I, typename P> I& getFirst(I& i, const P& p) const {
    2925      return graph->getFirst(i, p); }
    30     //template<typename I> I next(const I i); { return graph->goNext(i); }
    31     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
     26   
     27    template<typename I> I getNext(const I& i) const {
     28      return graph->getNext(i); }
     29    template<typename I> I& next(I &i) const { return graph->next(i); }   
    3230
    3331    template< typename It > It first() const {
    3432      It e; getFirst(e); return e; }
    3533
    36     template< typename It > It first(NodeIt v) const {
     34    template< typename It > It first(const NodeIt& v) const {
    3735      It e; getFirst(e, v); return e; }
    3836
    3937    NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    4038    NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
     39
     40    template<typename I> bool valid(const I& i) const
     41      { return graph->valid(i); }
     42 
     43    //template<typename I> void setInvalid(const I &i);
     44    //{ return graph->setInvalid(i); }
     45
     46    int nodeNum() const { return graph->nodeNum(); }
     47    int edgeNum() const { return graph->edgeNum(); }
    4148 
    4249    template<typename I> NodeIt aNode(const I& e) const {
    … …  
    4552      return graph->bNode(e); }
    4653 
    47     //template<typename I> bool valid(const I& i)
    48     //{ return graph->valid(i); }
    49  
    50     //template<typename I> void setInvalid(const I &i);
    51     //{ return graph->setInvalid(i); }
    52  
    5354    NodeIt addNode() const { return graph->addNode(); }
    5455    EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
    … …  
    5859 
    5960    void clear() const { graph->clear(); }
    60  
     61   
    6162    template<typename T> class NodeMap : public Graph::NodeMap<T> {
    6263    public:
    63       NodeMap(const Graph& _G) : Graph::NodeMap<T>(_G) { }
    64       NodeMap(const Graph& _G, T a) : Graph::NodeMap<T>(_G, a) { }
    65     };
    66     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
    67  
     64      NodeMap(const TrivGraphWrapper<Graph>& _G) :
     65        Graph::NodeMap<T>(*(_G.G)) { }
     66      NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
     67        Graph::NodeMap<T>(*(_G.G), a) { }
     68    };
     69    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
     70    public:
     71      EdgeMap(const TrivGraphWrapper<Graph>& _G) :
     72        Graph::EdgeMap<T>(*(_G.G)) { }
     73      EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
     74        Graph::EdgeMap<T>(*(_G.G), a) { }
     75    };
     76   
    6877    void setGraph(Graph& _graph) { graph = &_graph; }
    69     Graph& getGraph() { return (*graph); }
     78    Graph& getGraph() const { return (*graph); }
    7079 
    7180    //TrivGraphWrapper() : graph(0) { }
    … …  
    7483
    7584  template<typename Graph>
    76   class ConstTrivGraphWrapper {
    77     const Graph* graph;
     85  class RevGraphWrapper
     86  {
     87    Graph* graph;
    7888 
    7989  public:
    8090    typedef Graph BaseGraph;
    8191
    82     typedef typename Graph::NodeIt NodeIt;
     92    typedef typename Graph::NodeIt NodeIt;   
     93    typedef typename Graph::EachNodeIt EachNodeIt;
     94 
    8395    typedef typename Graph::EdgeIt EdgeIt;
    84  
    85     typedef typename Graph::EachNodeIt EachNodeIt;
    86 
    87     typedef typename Graph::OutEdgeIt OutEdgeIt;
    88     typedef typename Graph::InEdgeIt InEdgeIt;
    89     typedef typename Graph::SymEdgeIt SymEdgeIt;
     96    typedef typename Graph::OutEdgeIt InEdgeIt;
     97    typedef typename Graph::InEdgeIt OutEdgeIt;
     98    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    9099    typedef typename Graph::EachEdgeIt EachEdgeIt;
    91 
    92     int nodeNum() const { return graph->nodeNum(); }
    93     int edgeNum() const { return graph->edgeNum(); }
    94100   
    95101    template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
    96102    template<typename I, typename P> I& getFirst(I& i, const P& p) const {
    97103      return graph->getFirst(i, p); }
    98     //template<typename I> I next(const I i); { return graph->goNext(i); }
    99     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
     104
     105    template<typename I> I getNext(const I& i) const {
     106      return graph->getNext(i); }
     107    template<typename I> I& next(I &i) const { return graph->next(i); }   
    100108
    101109    template< typename It > It first() const {
    102110      It e; getFirst(e); return e; }
    103111
    104     template< typename It > It first(NodeIt v) const {
     112    template< typename It > It first(const NodeIt& v) const {
    105113      It e; getFirst(e, v); return e; }
    106114
    107     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    108     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
     115    NodeIt head(const EdgeIt& e) const { return graph->tail(e); }
     116    NodeIt tail(const EdgeIt& e) const { return graph->head(e); }
     117 
     118    template<typename I> bool valid(const I& i) const
     119      { return graph->valid(i); }
     120 
     121    //template<typename I> void setInvalid(const I &i);
     122    //{ return graph->setInvalid(i); }
    109123 
    110124    template<typename I> NodeIt aNode(const I& e) const {
    … …  
    112126    template<typename I> NodeIt bNode(const I& e) const {
    113127      return graph->bNode(e); }
    114  
    115     //template<typename I> bool valid(const I& i)
    116     //{ return graph->valid(i); }
    117  
    118     //template<typename I> void setInvalid(const I &i);
    119     //{ return graph->setInvalid(i); }
    120  
     128
    121129    NodeIt addNode() const { return graph->addNode(); }
    122130    EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
    123131      return graph->addEdge(tail, head); }
    124132 
    125     template<typename I> void erase(const I& i) const { graph->erase(i); }
    126  
    127     void clear() const { graph->clear(); }
    128  
    129     template<typename T> class NodeMap : public Graph::NodeMap<T> {
    130     public:
    131       NodeMap(const Graph& _G) : Graph::NodeMap<T>(_G) { }
    132       NodeMap(const Graph& _G, T a) : Graph::NodeMap<T>(_G, a) { }
    133     };
    134     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
    135  
    136     void setGraph(const Graph& _graph) { graph = &_graph; }
    137     const Graph& getGraph() { return (*graph); }
    138  
    139     //ConstTrivGraphWrapper() : graph(0) { }
    140     ConstTrivGraphWrapper(const Graph& _graph) : graph(&_graph) { }
    141   };
    142 
    143 
    144   template<typename Graph>
    145   class RevGraphWrapper
    146   {
    147     Graph* graph;
    148  
    149   public:
    150     typedef Graph BaseGraph;
    151 
    152     typedef typename Graph::NodeIt NodeIt;
    153     typedef typename Graph::EdgeIt EdgeIt;
    154  
    155     typedef typename Graph::EachNodeIt EachNodeIt;
    156  
    157     typedef typename Graph::OutEdgeIt InEdgeIt;
    158     typedef typename Graph::InEdgeIt OutEdgeIt;
    159     typedef typename Graph::SymEdgeIt SymEdgeIt;
    160     typedef typename Graph::EachEdgeIt EachEdgeIt;
    161 
    162133    int nodeNum() const { return graph->nodeNum(); }
    163134    int edgeNum() const { return graph->edgeNum(); }
    164    
    165     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
    166     template<typename I, typename P> I& getFirst(I& i, const P& p) const {
    167       return graph->getFirst(i, p); }
    168     //template<typename I> I next(const I i); { return graph->goNext(i); }
    169     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
    170 
    171     template< typename It > It first() const {
    172       It e; getFirst(e); return e; }
    173 
    174     template< typename It > It first(NodeIt v) const {
    175       It e; getFirst(e, v); return e; }
    176 
    177     NodeIt head(const EdgeIt& e) const { return graph->tail(e); }
    178     NodeIt tail(const EdgeIt& e) const { return graph->head(e); }
    179  
    180     template<typename I> NodeIt aNode(const I& e) const {
    181       return graph->aNode(e); }
    182     template<typename I> NodeIt bNode(const I& e) const {
    183       return graph->bNode(e); }
    184  
    185     //template<typename I> bool valid(const I i);
    186     //{ return graph->valid(i); }
    187  
    188     //template<typename I> void setInvalid(const I &i);
    189     //{ return graph->setInvalid(i); }
    190  
    191     NodeIt addNode() { return graph->addNode(); }
    192     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
    193       return graph->addEdge(tail, head); }
    194  
    195     template<typename I> void erase(const I& i) { graph->erase(i); }
    196  
    197     void clear() { graph->clear(); }
    198  
    199     template<typename T> class NodeMap : public Graph::NodeMap<T> { };
    200     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
    201  
     135 
     136    template<typename I> void erase(const I& i) const { graph->erase(i); }
     137 
     138    void clear() const { graph->clear(); }
     139
     140    template<typename T> class NodeMap : public Graph::NodeMap<T> {
     141    public:
     142      NodeMap(const RevGraphWrapper<Graph>& _G) :
     143        Graph::NodeMap<T>(*(_G.G)) { }
     144      NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
     145        Graph::NodeMap<T>(*(_G.G), a) { }
     146    };
     147    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
     148    public:
     149      EdgeMap(const RevGraphWrapper<Graph>& _G) :
     150        Graph::EdgeMap<T>(*(_G.G)) { }
     151      EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
     152        Graph::EdgeMap<T>(*(_G.G), a) { }
     153    };
     154
    202155    void setGraph(Graph& _graph) { graph = &_graph; }
    203     Graph& getGraph() { return (*graph); }
     156    Graph& getGraph() const { return (*graph); }
    204157
    205158    //RevGraphWrapper() : graph(0) { }
    … …  
    207160  };
    208161
    209   template<typename Graph>
    210   class SymGraphWrapper
    211   {
    212     Graph* graph;
    213  
     162
     163//   template<typename Graph>
     164//   class SymGraphWrapper
     165//   {
     166//     Graph* graph;
     167 
     168//   public:
     169//     typedef Graph BaseGraph;
     170
     171//     typedef typename Graph::NodeIt NodeIt;
     172//     typedef typename Graph::EdgeIt EdgeIt;
     173 
     174//     typedef typename Graph::EachNodeIt EachNodeIt;
     175   
     176//     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
     177//     //iranyitatlant, ami van
     178//     //mert csak 1 dolgot lehet be typedef-elni
     179//     typedef typename Graph::OutEdgeIt SymEdgeIt;
     180//     //typedef typename Graph::InEdgeIt SymEdgeIt;
     181//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
     182//     typedef typename Graph::EachEdgeIt EachEdgeIt;
     183
     184//     int nodeNum() const { return graph->nodeNum(); }
     185//     int edgeNum() const { return graph->edgeNum(); }
     186   
     187//     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
     188//     template<typename I, typename P> I& getFirst(I& i, const P& p) const {
     189//       return graph->getFirst(i, p); }
     190//     //template<typename I> I next(const I i); { return graph->goNext(i); }
     191//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
     192
     193//     template< typename It > It first() const {
     194//       It e; getFirst(e); return e; }
     195
     196//     template< typename It > It first(NodeIt v) const {
     197//       It e; getFirst(e, v); return e; }
     198
     199//     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
     200//     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
     201 
     202//     template<typename I> NodeIt aNode(const I& e) const {
     203//       return graph->aNode(e); }
     204//     template<typename I> NodeIt bNode(const I& e) const {
     205//       return graph->bNode(e); }
     206 
     207//     //template<typename I> bool valid(const I i);
     208//     //{ return graph->valid(i); }
     209 
     210//     //template<typename I> void setInvalid(const I &i);
     211//     //{ return graph->setInvalid(i); }
     212 
     213//     NodeIt addNode() { return graph->addNode(); }
     214//     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
     215//       return graph->addEdge(tail, head); }
     216 
     217//     template<typename I> void erase(const I& i) { graph->erase(i); }
     218 
     219//     void clear() { graph->clear(); }
     220 
     221//     template<typename T> class NodeMap : public Graph::NodeMap<T> { };
     222//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
     223 
     224//     void setGraph(Graph& _graph) { graph = &_graph; }
     225//     Graph& getGraph() { return (*graph); }
     226
     227//     //SymGraphWrapper() : graph(0) { }
     228//     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
     229//   };
     230
     231
     232  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     233  class ResGraphWrapper {
    214234  public:
    215235    typedef Graph BaseGraph;
    216 
    217236    typedef typename Graph::NodeIt NodeIt;
    218     typedef typename Graph::EdgeIt EdgeIt;
    219  
    220237    typedef typename Graph::EachNodeIt EachNodeIt;
     238  private:
     239    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
     240    typedef typename Graph::InEdgeIt OldInEdgeIt;
     241    const Graph* G;
     242    FlowMap* flow;
     243    const CapacityMap* capacity;
     244  public:
     245    ResGraphWrapper(const Graph& _G, FlowMap& _flow,
     246             const CapacityMap& _capacity) :
     247      G(&_G), flow(&_flow), capacity(&_capacity) { }
     248//     ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
     249//       G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
     250    class EdgeIt;
     251    class OutEdgeIt;
     252    friend class EdgeIt;
     253    friend class OutEdgeIt;
     254
     255    class EdgeIt {
     256      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     257    protected:
     258      //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
     259      const Graph* G;
     260      FlowMap* flow;
     261      const CapacityMap* capacity;
     262      //OldSymEdgeIt sym;
     263      OldOutEdgeIt out;
     264      OldInEdgeIt in;
     265      bool out_or_in; //true, iff out
     266    public:
     267      EdgeIt() : out_or_in(true) { }
     268      EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :
     269        G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
     270      //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) { }
     271      Number free() const {
     272        if (out_or_in) {
     273          return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
     274        } else {
     275          return (/*resG->*/flow->get(in));
     276        }
     277      }
     278      bool valid() const {
     279        return out_or_in && out.valid() || in.valid(); }
     280      void augment(Number a) const {
     281        if (out_or_in) {
     282          /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
     283        } else {
     284          /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
     285        }
     286      }
     287      void print() {
     288        if (out_or_in) {
     289          std::cout << "out ";
     290          if (out.valid())
     291            std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
     292          else
     293            std::cout << "invalid";
     294        }
     295        else {
     296          std::cout << "in ";
     297          if (in.valid())
     298            std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
     299          else
     300            std::cout << "invalid";
     301        }
     302        std::cout << std::endl;
     303      }
     304    };
     305
     306    Number free(OldOutEdgeIt out) const {
     307      return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
     308    }
     309    Number free(OldInEdgeIt in) const {
     310      return (/*resG->*/flow->get(in));
     311    }
     312
     313    class OutEdgeIt : public EdgeIt {
     314      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     315    public:
     316      OutEdgeIt() { }
     317    private:
     318      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
     319        //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
     320        G->getFirst(out, v);
     321        while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     322        if (!out.valid()) {
     323          out_or_in=0;
     324          //in=/*resG->*/G->template first<OldInEdgeIt>(v);
     325          G->getFirst(in, v);
     326          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     327        }
     328      }
     329    public:
     330      OutEdgeIt& operator++() {
     331        if (out_or_in) {
     332          NodeIt v=/*resG->*/G->aNode(out);
     333          ++out;
     334          while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     335          if (!out.valid()) {
     336            out_or_in=0;
     337            G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
     338            while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     339          }
     340        } else {
     341          ++in;
     342          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     343        }
     344        return *this;
     345      }
     346    };
     347
     348    class EachEdgeIt : public EdgeIt {
     349      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     350      typename Graph::EachNodeIt v;
     351    public:
     352      EachEdgeIt() { }
     353      //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
     354      EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
     355        out_or_in=true;
     356        G->getFirst(v);
     357        if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
     358        while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     359        while (v.valid() && !out.valid()) {
     360          ++v;
     361          if (v.valid()) G->getFirst(out, v);
     362          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     363        }
     364        if (!out.valid()) {
     365          out_or_in=0;
     366          G->getFirst(v);
     367          if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
     368          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     369          while (v.valid() && !in.valid()) {
     370            ++v;
     371            if (v.valid()) G->getFirst(in, v);
     372            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     373          }
     374        }
     375      }
     376      EachEdgeIt& operator++() {
     377        if (out_or_in) {
     378          ++out;
     379          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     380          while (v.valid() && !out.valid()) {
     381            ++v;
     382            if (v.valid()) G->getFirst(out, v);
     383            while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     384          }
     385          if (!out.valid()) {
     386            out_or_in=0;
     387            G->getFirst(v);
     388            if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
     389            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     390            while (v.valid() && !in.valid()) {
     391              ++v;
     392              if (v.valid()) G->getFirst(in, v);
     393              while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     394            } 
     395          }
     396        } else {
     397          ++in;
     398          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     399          while (v.valid() && !in.valid()) {
     400            ++v;
     401            if (v.valid()) G->getFirst(in, v);
     402            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     403          }
     404        }
     405        return *this;
     406      }
     407    };
     408
     409    void getFirst(EachNodeIt& v) const { G->getFirst(v); }
     410    void getFirst(OutEdgeIt& e, NodeIt v) const {
     411      e=OutEdgeIt(*G, v, *flow, *capacity);
     412    }
     413    void getFirst(EachEdgeIt& e) const {
     414      e=EachEdgeIt(*G, *flow, *capacity);
     415    }
     416   
     417    EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
     418
     419    OutEdgeIt& next(OutEdgeIt& e) const {
     420      if (e.out_or_in) {
     421        NodeIt v=G->aNode(e.out);
     422        ++(e.out);
     423        while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
     424        if (!G->valid(e.out)) {
     425          e.out_or_in=0;
     426          G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
     427          while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     428        }
     429      } else {
     430        ++(e.in);
     431        while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     432      }
     433      return e;
     434    }
     435
     436    EachEdgeIt& next(EachEdgeIt& e) const {
     437      if (e.out_or_in) {
     438        ++(e.out);
     439        while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
     440          while (G->valid(e.v) && !G->valid(e.out)) {
     441            ++(e.v);
     442            if (G->valid(e.v)) G->getFirst(e.out, e.v);
     443            while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
     444          }
     445          if (!G->valid(e.out)) {
     446            e.out_or_in=0;
     447            G->getFirst(e.v);
     448            if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
     449            while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     450            while (G->valid(e.v) && !G->valid(e.in)) {
     451              ++(e.v);
     452              if (G->valid(e.v)) G->getFirst(e.in, e.v);
     453              while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     454            } 
     455          }
     456        } else {
     457          ++(e.in);
     458          while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     459          while (G->valid(e.v) && !G->valid(e.in)) {
     460            ++(e.v);
     461            if (G->valid(e.v)) G->getFirst(e.in, e.v);
     462            while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     463          }
     464        }
     465        return e;
     466      }
    221467   
    222     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
    223     //iranyitatlant, ami van
    224     //mert csak 1 dolgot lehet be typedef-elni
    225     typedef typename Graph::OutEdgeIt SymEdgeIt;
    226     //typedef typename Graph::InEdgeIt SymEdgeIt;
    227     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    228     typedef typename Graph::EachEdgeIt EachEdgeIt;
    229 
    230     int nodeNum() const { return graph->nodeNum(); }
    231     int edgeNum() const { return graph->edgeNum(); }
    232    
    233     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
    234     template<typename I, typename P> I& getFirst(I& i, const P& p) const {
    235       return graph->getFirst(i, p); }
    236     //template<typename I> I next(const I i); { return graph->goNext(i); }
    237     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
    238 
    239     template< typename It > It first() const {
    240       It e; getFirst(e); return e; }
    241 
    242     template< typename It > It first(NodeIt v) const {
    243       It e; getFirst(e, v); return e; }
    244 
    245     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    246     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
    247  
    248     template<typename I> NodeIt aNode(const I& e) const {
    249       return graph->aNode(e); }
    250     template<typename I> NodeIt bNode(const I& e) const {
    251       return graph->bNode(e); }
    252  
    253     //template<typename I> bool valid(const I i);
    254     //{ return graph->valid(i); }
    255  
    256     //template<typename I> void setInvalid(const I &i);
    257     //{ return graph->setInvalid(i); }
    258  
    259     NodeIt addNode() { return graph->addNode(); }
    260     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
    261       return graph->addEdge(tail, head); }
    262  
    263     template<typename I> void erase(const I& i) { graph->erase(i); }
    264  
    265     void clear() { graph->clear(); }
    266  
    267     template<typename T> class NodeMap : public Graph::NodeMap<T> { };
    268     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
    269  
    270     void setGraph(Graph& _graph) { graph = &_graph; }
    271     Graph& getGraph() { return (*graph); }
    272 
    273     //SymGraphWrapper() : graph(0) { }
    274     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
     468
     469    template< typename It >
     470    It first() const {
     471      It e;
     472      getFirst(e);
     473      return e;
     474    }
     475
     476    template< typename It >
     477    It first(NodeIt v) const {
     478      It e;
     479      getFirst(e, v);
     480      return e;
     481    }
     482
     483    NodeIt tail(EdgeIt e) const {
     484      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
     485    NodeIt head(EdgeIt e) const {
     486      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
     487
     488    NodeIt aNode(OutEdgeIt e) const {
     489      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
     490    NodeIt bNode(OutEdgeIt e) const {
     491      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
     492
     493    int id(NodeIt v) const { return G->id(v); }
     494
     495    bool valid(NodeIt n) const { return G->valid(n); }
     496    bool valid(EdgeIt e) const {
     497      return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
     498
     499    template<typename T> class NodeMap : public Graph::NodeMap<T> {
     500    public:
     501      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
     502        : Graph::NodeMap<T>(*(_G.G)) { }
     503      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
     504              T a) : Graph::NodeMap<T>(*(_G.G), a) { }
     505    };
     506
     507//     template <typename T>
     508//     class NodeMap {
     509//       typename Graph::NodeMap<T> node_map;
     510//     public:
     511//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }
     512//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }
     513//       void set(NodeIt nit, T a) { node_map.set(nit, a); }
     514//       T get(NodeIt nit) const { return node_map.get(nit); }
     515//     };
     516
     517    template <typename T>
     518    class EdgeMap {
     519      typename Graph::EdgeMap<T> forward_map, backward_map;
     520    public:
     521      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { }
     522      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { }
     523      void set(EdgeIt e, T a) {
     524        if (e.out_or_in)
     525          forward_map.set(e.out, a);
     526        else
     527          backward_map.set(e.in, a);
     528      }
     529      T get(EdgeIt e) {
     530        if (e.out_or_in)
     531          return forward_map.get(e.out);
     532        else
     533          return backward_map.get(e.in);
     534      }
     535    };
     536
    275537  };
    276538
    … …  
    423685//   };
    424686
    425 
    426 // // FIXME: comparison should be made better!!!
    427 //   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
    428 //   class ConstResGraphWrapper
    429 //   {
    430 //     const Graph* graph;
    431 //     const LowerMap* low;
    432 //     FlowMap* flow;
    433 //     const UpperMap* up;
    434 //   public:
    435 //     typedef Graph BaseGraph;
    436 
    437 //     typedef typename Graph::NodeIt NodeIt;
    438 //     typedef typename Graph::EdgeIt EdgeIt;
    439  
    440 //     typedef typename Graph::EachNodeIt EachNodeIt;
    441    
    442 //     class OutEdgeIt {
    443 //     public:
    444 //       //Graph::NodeIt n;
    445 //       bool out_or_in;
    446 //       typename Graph::SymEdgeIt sym;
    447 //     };
    448 //     class InEdgeIt {
    449 //     public:
    450 //       //Graph::NodeIt n;
    451 //       bool out_or_in;
    452 //       typename Graph::OutEdgeIt sym;
    453 //     };
    454 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    455 //     //typedef typename Graph::EachEdgeIt EachEdgeIt;
    456 
    457 //     int nodeNum() const { return graph->nodeNum(); }
    458 //     //int edgeNum() const { return graph->edgeNum(); }
    459 
    460 //     NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
    461 
    462 //     // EachEdge and SymEdge  is missing!!!!
    463 //     // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
    464 
    465    
    466 //     //FIXME
    467 //     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const
    468 //       {
    469 //      e.n=n;
    470 //      graph->getFirst(e.o,n);
    471 //      while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
    472 //        graph->goNext(e.o);
    473 //      if(!graph->valid(e.o)) {
    474 //        graph->getFirst(e.i,n);
    475 //        while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
    476 //          graph->goNext(e.i);
    477 //      }
    478 //      return e;
    479 //       }
    480 // /*
    481 //   OutEdgeIt &goNext(OutEdgeIt &e)
    482 //   {
    483 //   if(graph->valid(e.o)) {
    484 //   while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
    485 //   graph->goNext(e.o);
    486 //   if(graph->valid(e.o)) return e;
    487 //   else graph->getFirst(e.i,e.n);
    488 //   }
    489 //   else {
    490 //   while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
    491 //   graph->goNext(e.i);
    492 //   return e;
    493 //   }
    494 //   }
    495 //   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
    496 // */
    497 //     //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
    498 
    499 //     //FIXME
    500 //     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const
    501 //       {
    502 //      e.n=n;
    503 //      graph->getFirst(e.i,n);
    504 //      while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
    505 //        graph->goNext(e.i);
    506 //      if(!graph->valid(e.i)) {
    507 //        graph->getFirst(e.o,n);
    508 //        while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
    509 //          graph->goNext(e.o);
    510 //      }
    511 //      return e;
    512 //       }
    513 // /*
    514 //   InEdgeIt &goNext(InEdgeIt &e)
    515 //   {
    516 //   if(graph->valid(e.i)) {
    517 //   while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
    518 //   graph->goNext(e.i);
    519 //   if(graph->valid(e.i)) return e;
    520 //   else graph->getFirst(e.o,e.n);
    521 //   }
    522 //   else {
    523 //   while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
    524 //   graph->goNext(e.o);
    525 //   return e;
    526 //   }
    527 //   }
    528 //   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
    529 // */
    530 //     //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
    531 
    532 //     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
    533 //     //template<typename I> I next(const I i); { return graph->goNext(i); }
    534 
    535 //     template< typename It > It first() const {
    536 //       It e; getFirst(e); return e; }
    537 
    538 //     template< typename It > It first(NodeIt v) const {
    539 //       It e; getFirst(e, v); return e; }
    540 
    541 //     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    542 //     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
    543  
    544 //     template<typename I> NodeIt aNode(const I& e) const {
    545 //       return graph->aNode(e); }
    546 //     template<typename I> NodeIt bNode(const I& e) const {
    547 //       return graph->bNode(e); }
    548  
    549 //     //template<typename I> bool valid(const I i);
    550 //     //{ return graph->valid(i); }
    551  
    552 //     //template<typename I> void setInvalid(const I &i);
    553 //     //{ return graph->setInvalid(i); }
    554  
    555 //     NodeIt addNode() { return graph->addNode(); }
    556 //     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
    557 //       return graph->addEdge(tail, head); }
    558  
    559 //     template<typename I> void erase(const I& i) { graph->erase(i); }
    560  
    561 //     void clear() { graph->clear(); }
    562  
    563 //     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
    564 //     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
    565  
    566 //     void setGraph(const Graph& _graph) { graph = &_graph; }
    567 //     const Graph& getGraph() { return (*graph); }
    568 
    569 //     //ConstResGraphWrapper() : graph(0) { }
    570 //     ConstResGraphWrapper(const Graph& _graph) : graph(&_graph) { }
    571 //   };
    572 
    573 
    574 
    575 
    576 
    577687} //namespace hugo
    578688

  • src/work/marci_graph_demo.cc

    r133 r155  
    246246    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    247247  }
    248 
     248/*
    249249  {
    250250    std::list<NodeIt> S;
    … …  
    264264    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    265265  }
    266 
     266*/
    267267  return 0;
    268268}
Note: See TracChangeset for help on using the changeset viewer.