COIN-OR::LEMON - Graph Library

Changeset 168:27fbd1559fb7 in lemon-0.x


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

graph wrapper improvements, blocking flow on fly

Location:
src/work
Files:
6 edited

Legend:

Unmodified
Added
Removed
  • src/work/bfs_iterator.hh

    r158 r168  
    563563    ~BfsIterator4() { if (own_reached_map) delete &reached; }
    564564    void pushAndSetReached(NodeIt s) {
     565      //std::cout << "mimi" << &reached << std::endl;
    565566      reached.set(s, true);
     567      //std::cout << "mumus" << std::endl;
    566568      if (bfs_queue.empty()) {
     569        //std::cout << "bibi1" << std::endl;
    567570        bfs_queue.push(s);
     571        //std::cout << "zizi" << std::endl;
    568572        G.getFirst(actual_edge, s);
     573        //std::cout << "kiki" << std::endl;
    569574        if (G.valid(actual_edge)/*.valid()*/) {
    570575          NodeIt w=G.bNode(actual_edge);
     
    578583        }
    579584      } else {
     585        //std::cout << "bibi2" << std::endl;
    580586        bfs_queue.push(s);
    581587      }
  • src/work/edmonds_karp.hh

    r155 r168  
    280280     
    281281      typedef typename AugGraph::NodeMap<bool> ReachedMap;
    282       BfsIterator5< AugGraph, AugOutEdgeIt, ReachedMap > res_bfs(res_graph);
     282      BfsIterator5< AugGraph, /*AugOutEdgeIt,*/ ReachedMap > res_bfs(res_graph);
    283283      res_bfs.pushAndSetReached(s);
    284284       
     
    297297          pred.set(w, e);
    298298          if (res_graph.valid(pred.get(v))) {
    299             free.set(w, std::min(free.get(v), e.free()));
     299            free.set(w, std::min(free.get(v), res_graph.free(e)));
    300300          } else {
    301             free.set(w, e.free());
     301            free.set(w, res_graph.free(e));
    302302          }
    303303          if (res_graph.head(e)==t) { _augment=true; break; }
     
    312312        while (res_graph.valid(pred.get(n))) {
    313313          AugEdgeIt e=pred.get(n);
    314           e.augment(augment_value);
     314          res_graph.augment(e, augment_value);
     315          //e.augment(augment_value);
    315316          n=res_graph.tail(e);
    316317        }
     
    359360          original_edge.set(f, e);
    360361          residual_capacity.update();
    361           residual_capacity.set(f, e.free());
     362          residual_capacity.set(f, res_graph.free(e));
    362363        }
    363364      }
     
    377378          ++dfs;
    378379          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
    379             //std::cout << "OutEdgeIt: " << dfs;
    380             //std::cout << " aNode: " << F.aNode(dfs);
    381             //std::cout << " bNode: " << F.bNode(dfs) << " ";
     380            if (dfs.isBNodeNewlyReached()) {
     381//            std::cout << "OutEdgeIt: " << dfs;
     382//            std::cout << " aNode: " << F.aNode(dfs);
     383//            std::cout << " bNode: " << F.bNode(dfs) << " ";
    382384         
    383             typename MutableGraph::NodeIt v=F.aNode(dfs);
    384             typename MutableGraph::NodeIt w=F.bNode(dfs);
    385             pred.set(w, dfs);
    386             if (F.valid(pred.get(v))) {
    387               free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
     385              typename MutableGraph::NodeIt v=F.aNode(dfs);
     386              typename MutableGraph::NodeIt w=F.bNode(dfs);
     387              pred.set(w, dfs);
     388              if (F.valid(pred.get(v))) {
     389                free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
     390              } else {
     391                free.set(w, residual_capacity.get(dfs));
     392              }
     393              if (w==tF) {
     394                //std::cout << "AUGMENTATION"<<std::endl;
     395                __augment=true;
     396                _augment=true;
     397                break;
     398              }
     399             
    388400            } else {
    389               free.set(w, residual_capacity.get(dfs)/*original_edge.get(dfs).free()*/);
    390             }
    391             if (w==tF) {
    392               //std::cout << "AUGMENTATION"<<std::endl;
    393               __augment=true;
    394               _augment=true;
    395               break;
    396             }
    397           } else {
    398             //std::cout << "OutEdgeIt: " << "invalid";
    399             //std::cout << " aNode: " << dfs.aNode();
    400             //std::cout << " bNode: " << "invalid" << " ";
    401           }
    402           if (dfs.isBNodeNewlyReached()) {
    403             //std::cout << "bNodeIsNewlyReached ";
    404           } else {
    405             //std::cout << "bNodeIsNotNewlyReached ";
    406             if (typename MutableGraph::OutEdgeIt(dfs).valid()) {
    407               //std::cout << "DELETE ";
    408401              F.erase(typename MutableGraph::OutEdgeIt(dfs));
    409402            }
    410403          }
    411           //if (dfs.isANodeExamined()) {
    412             //std::cout << "aNodeIsExamined ";
    413             //} else {
    414             //std::cout << "aNodeIsNotExamined ";
    415             //}
    416           //std::cout<<std::endl;
    417404        }
    418405
     
    422409          while (F.valid(pred.get(n))) {
    423410            typename MutableGraph::EdgeIt e=pred.get(n);
    424             original_edge.get(e).augment(augment_value);
     411            res_graph.augment(original_edge.get(e), augment_value);
     412            //original_edge.get(e).augment(augment_value);
    425413            n=F.tail(e);
    426414            if (residual_capacity.get(e)==augment_value)
     
    428416            else
    429417              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
     418          }
     419        }
     420       
     421      }
     422           
     423      return _augment;
     424    }
     425    bool augmentOnBlockingFlow2() {
     426      bool _augment=false;
     427
     428      //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
     429      typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
     430      typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
     431      typedef typename EAugGraph::EdgeIt EAugEdgeIt;
     432
     433      EAugGraph res_graph(*G, *flow, *capacity);
     434
     435      //std::cout << "meg jo1" << std::endl;
     436
     437      //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
     438      BfsIterator4<
     439        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
     440        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,
     441        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
     442     
     443      //std::cout << "meg jo2" << std::endl;
     444
     445      bfs.pushAndSetReached(s);
     446      //std::cout << "meg jo2.5" << std::endl;
     447
     448      //typename EAugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
     449      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
     450        NodeMap<int>& dist=res_graph.dist;
     451      //std::cout << "meg jo2.6" << std::endl;
     452
     453      while ( !bfs.finished() ) {
     454        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
     455//      EAugOutEdgeIt e=/*AugOutEdgeIt*/(bfs);
     456        //if (res_graph.valid(e)) {
     457        //    std::cout<<"a:"<<res_graph.tail(e)<<"b:"<<res_graph.head(e)<<std::endl;
     458        //}
     459        if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
     460          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     461        }
     462       
     463        ++bfs; 
     464      } //computing distances from s in the residual graph
     465
     466
     467      //std::cout << "meg jo3" << std::endl;
     468
     469//       typedef typename EAugGraph::EachNodeIt EAugEachNodeIt;
     470//       for(EAugEachNodeIt n=res_graph.template first<EAugEachNodeIt>(); res_graph.valid(n); res_graph.next(n)) {
     471//      std::cout << "dist: " << dist.get(n) << std::endl;
     472//       }
     473
     474      bool __augment=true;
     475
     476      while (__augment) {
     477//      std::cout << "new iteration"<< std::endl;
     478
     479        __augment=false;
     480        //computing blocking flow with dfs
     481        typedef typename EAugGraph::NodeMap<bool> BlockingReachedMap;
     482        DfsIterator4< EAugGraph, EAugOutEdgeIt, BlockingReachedMap >
     483          dfs(res_graph);
     484        typename EAugGraph::NodeMap<EAugEdgeIt> pred(res_graph); //invalid iterators
     485        typename EAugGraph::NodeMap<Number> free(res_graph);
     486
     487        dfs.pushAndSetReached(s);
     488        while (!dfs.finished()) {
     489          ++dfs;
     490          if (res_graph.valid(EAugOutEdgeIt(dfs))) {
     491            if (dfs.isBNodeNewlyReached()) {
     492//            std::cout << "OutEdgeIt: " << dfs;
     493//            std::cout << " aNode: " << res_graph.aNode(dfs);
     494//            std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
     495//            std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
     496         
     497              typename EAugGraph::NodeIt v=res_graph.aNode(dfs);
     498              typename EAugGraph::NodeIt w=res_graph.bNode(dfs);
     499
     500              pred.set(w, EAugOutEdgeIt(dfs));
     501
     502              //std::cout << EAugOutEdgeIt(dfs).free() << std::endl;
     503              if (res_graph.valid(pred.get(v))) {
     504                free.set(w, std::min(free.get(v), res_graph.free(/*EAugOutEdgeIt*/(dfs))));
     505              } else {
     506                free.set(w, res_graph.free(/*EAugOutEdgeIt*/(dfs)));
     507              }
     508             
     509              if (w==t) {
     510//              std::cout << "t is reached, AUGMENTATION"<<std::endl;
     511                __augment=true;
     512                _augment=true;
     513                break;
     514              }
     515            } else {
     516//            std::cout << "<<DELETE ";
     517//            std::cout << " aNode: " << res_graph.aNode(dfs);
     518//            std::cout << " res cap: " << EAugOutEdgeIt(dfs).free();
     519//            std::cout << " bNode: " << res_graph.bNode(dfs) << " ";
     520//            std::cout << "DELETE>> ";
     521
     522              res_graph.erase(dfs);
     523            }
     524          }
     525
     526        }
     527
     528        if (__augment) {
     529          typename EAugGraph::NodeIt n=t;
     530          Number augment_value=free.get(t);
     531//        std::cout << "av:" << augment_value << std::endl;
     532          while (res_graph.valid(pred.get(n))) {
     533            EAugEdgeIt e=pred.get(n);
     534            res_graph.augment(e, augment_value);
     535            //e.augment(augment_value);
     536            n=res_graph.tail(e);
     537            if (res_graph.free(e)==0)
     538              res_graph.erase(e);
    430539          }
    431540        }
  • src/work/marci/edmonds_karp_demo.cc

    r155 r168  
    8888  //max_flow_test.augmentWithBlockingFlow<ListGraph>();
    8989  int i=0;
    90   while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { ++i; }
     90  while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) {
     91//     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
     92//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     93//     }
     94//     std::cout<<std::endl;
     95    ++i;
     96  }
     97  //double post_time=currTime();
     98
     99  //std::cout << "maximum flow: "<< std::endl;
     100  //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
     101  //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     102  //}
     103  //std::cout<<std::endl;
     104  std::cout << "elapsed time: " << ts << std::endl;
     105  std::cout << "number of augmentation phases: " << i << std::endl;
     106  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     107  }
     108
     109  {
     110  std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
     111  ListGraph::EdgeMap<int> flow(G); //0 flow
     112
     113  Timer ts;
     114  ts.reset();
     115  //double pre_time=currTime();
     116  MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
     117  //max_flow_test.augmentWithBlockingFlow<ListGraph>();
     118  int i=0;
     119  while (max_flow_test.augmentOnBlockingFlow2()) {
     120//     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
     121//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     122//     }
     123//     std::cout<<std::endl;
     124    ++i;
     125  }
    91126  //double post_time=currTime();
    92127
     
    111146  //max_flow_test.augmentWithBlockingFlow<ListGraph>();
    112147  int i=0;
    113   while (max_flow_test.augmentOnShortestPath()) { ++i; }
     148  while (max_flow_test.augmentOnShortestPath()) {
     149//     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) {
     150//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     151//     }
     152//     std::cout<<std::endl;
     153    ++i;
     154  }
    114155  //double post_time=currTime();
    115156
  • src/work/marci/graph_wrapper.h

    r158 r168  
    2020    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    2121    typedef typename Graph::EachEdgeIt EachEdgeIt;
     22
     23    //TrivGraphWrapper() : graph(0) { }
     24    TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
     25
     26    void setGraph(Graph& _graph) { graph = &_graph; }
     27    Graph& getGraph() const { return (*graph); }
    2228   
    2329    template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
     
    6773        Graph::NodeMap<T>(_G.getGraph(), a) { }
    6874    };
     75
    6976    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
    7077    public:
     
    7481        Graph::EdgeMap<T>(_G.getGraph(), a) { }
    7582    };
    76    
    77     void setGraph(Graph& _graph) { graph = &_graph; }
    78     Graph& getGraph() const { return (*graph); }
    79  
    80     //TrivGraphWrapper() : graph(0) { }
    81     TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
    8283  };
    8384
     
    9899    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    99100    typedef typename Graph::EachEdgeIt EachEdgeIt;
     101
     102    //RevGraphWrapper() : graph(0) { }
     103    RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
     104
     105    void setGraph(Graph& _graph) { graph = &_graph; }
     106    Graph& getGraph() const { return (*graph); }
    100107   
    101108    template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
     
    145152        Graph::NodeMap<T>(_G.getGraph(), a) { }
    146153    };
     154
    147155    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
    148156    public:
     
    152160        Graph::EdgeMap<T>(_G.getGraph(), a) { }
    153161    };
    154 
    155     void setGraph(Graph& _graph) { graph = &_graph; }
    156     Graph& getGraph() const { return (*graph); }
    157 
    158     //RevGraphWrapper() : graph(0) { }
    159     RevGraphWrapper(Graph& _graph) : graph(&_graph) { }
    160162  };
    161163
     
    183185    //public:
    184186
     187    //UndirGraphWrapper() : graph(0) { }
     188    UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
     189
     190    void setGraph(Graph& _graph) { graph = &_graph; }
     191    Graph& getGraph() const { return (*graph); }
     192 
    185193    class EdgeIt {
    186194      friend class UndirGraphWrapper<Graph>;
     
    197205    class OutEdgeIt : public EdgeIt {
    198206      friend class UndirGraphWrapper<Graph>;
    199       //bool out_or_in; //true iff out
    200       //GraphOutEdgeIt out;
    201       //GraphInEdgeIt in;
    202207    public:
    203208      OutEdgeIt() : EdgeIt() { }
     
    288293        Graph::NodeMap<T>(_G.getGraph(), a) { }
    289294    };
     295
    290296    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
    291297    public:
     
    295301        Graph::EdgeMap<T>(_G.getGraph(), a) { }
    296302    };
    297    
    298     void setGraph(Graph& _graph) { graph = &_graph; }
    299     Graph& getGraph() const { return (*graph); }
    300  
    301     //TrivGraphWrapper() : graph(0) { }
    302     UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
    303303  };
    304304
     
    387387    const CapacityMap* capacity;
    388388  public:
     389
    389390    ResGraphWrapper(const Graph& _G, FlowMap& _flow,
    390391             const CapacityMap& _capacity) :
     
    392393//     ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
    393394//       G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
    394     void setGraph(Graph& _graph) { graph = &_graph; }
    395     Graph& getGraph() const { return (*graph); }
     395
     396    void setGraph(const Graph& _graph) { graph = &_graph; }
     397    const Graph& getGraph() const { return (*G); }
     398
    396399    class EdgeIt;
    397400    class OutEdgeIt;
     
    402405      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    403406    protected:
    404       //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
    405       const Graph* G;
    406       FlowMap* flow;
    407       const CapacityMap* capacity;
    408       //OldSymEdgeIt sym;
     407      bool out_or_in; //true, iff out
    409408      OldOutEdgeIt out;
    410409      OldInEdgeIt in;
    411       bool out_or_in; //true, iff out
    412410    public:
    413411      EdgeIt() : out_or_in(true) { }
    414       EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :
    415         G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
    416       //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) { }
    417       Number free() const {
    418         if (out_or_in) {
    419           return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
    420         } else {
    421           return (/*resG->*/flow->get(in));
     412//       bool valid() const {
     413//      return out_or_in && out.valid() || in.valid(); }
     414    };
     415
     416
     417    class OutEdgeIt : public EdgeIt {
     418      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     419    public:
     420      OutEdgeIt() { }
     421      //FIXME
     422      OutEdgeIt(const EdgeIt& e) : EdgeIt(e) { }
     423    private:
     424      OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, NodeIt v) : EdgeIt() {
     425        resG.G->getFirst(out, v);
     426        while( out.valid() && !(resG.free(out)>0) ) { ++out; }
     427        if (!out.valid()) {
     428          out_or_in=0;
     429          resG.G->getFirst(in, v);
     430          while( in.valid() && !(resG.free(in)>0) ) { ++in; }
    422431        }
    423432      }
    424       bool valid() const {
    425         return out_or_in && out.valid() || in.valid(); }
    426       void augment(Number a) const {
    427         if (out_or_in) {
    428           /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
    429         } else {
    430           /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
    431         }
    432       }
    433       void print() {
    434         if (out_or_in) {
    435           std::cout << "out ";
    436           if (out.valid())
    437             std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
    438           else
    439             std::cout << "invalid";
    440         }
    441         else {
    442           std::cout << "in ";
    443           if (in.valid())
    444             std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
    445           else
    446             std::cout << "invalid";
    447         }
    448         std::cout << std::endl;
    449       }
    450     };
    451 
    452     Number free(OldOutEdgeIt out) const {
    453       return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
    454     }
    455     Number free(OldInEdgeIt in) const {
    456       return (/*resG->*/flow->get(in));
    457     }
    458 
    459     class OutEdgeIt : public EdgeIt {
    460       friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
    461     public:
    462       OutEdgeIt() { }
    463     private:
    464       OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
    465         //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
    466         G->getFirst(out, v);
    467         while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    468         if (!out.valid()) {
    469           out_or_in=0;
    470           //in=/*resG->*/G->template first<OldInEdgeIt>(v);
    471           G->getFirst(in, v);
    472           while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    473         }
    474       }
    475     public:
    476       OutEdgeIt& operator++() {
    477         if (out_or_in) {
    478           NodeIt v=/*resG->*/G->aNode(out);
    479           ++out;
    480           while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    481           if (!out.valid()) {
    482             out_or_in=0;
    483             G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
    484             while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    485           }
    486         } else {
    487           ++in;
    488           while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    489         }
    490         return *this;
    491       }
     433//     public:
     434//       OutEdgeIt& operator++() {
     435//      if (out_or_in) {
     436//        NodeIt v=/*resG->*/G->aNode(out);
     437//        ++out;
     438//        while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     439//        if (!out.valid()) {
     440//          out_or_in=0;
     441//          G->getFirst(in, v);
     442//          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     443//        }
     444//      } else {
     445//        ++in;
     446//        while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     447//      }
     448//      return *this;
     449//       }
    492450    };
    493451
     
    498456      EachEdgeIt() { }
    499457      //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
    500       EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
    501         out_or_in=true;
    502         G->getFirst(v);
    503         if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
    504         while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     458      EachEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : EdgeIt() {
     459        resG.G->getFirst(v);
     460        if (v.valid()) resG.G->getFirst(out, v); else out=OldOutEdgeIt();
     461        while (out.valid() && !(resG.free(out)>0) ) { ++out; }
    505462        while (v.valid() && !out.valid()) {
    506463          ++v;
    507           if (v.valid()) G->getFirst(out, v);
    508           while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     464          if (v.valid()) resG.G->getFirst(out, v);
     465          while (out.valid() && !(resG.free(out)>0) ) { ++out; }
    509466        }
    510467        if (!out.valid()) {
    511468          out_or_in=0;
    512           G->getFirst(v);
    513           if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
    514           while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     469          resG.G->getFirst(v);
     470          if (v.valid()) resG.G->getFirst(in, v); else in=OldInEdgeIt();
     471          while (in.valid() && !(resG.free(in)>0) ) { ++in; }
    515472          while (v.valid() && !in.valid()) {
    516473            ++v;
    517             if (v.valid()) G->getFirst(in, v);
    518             while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     474            if (v.valid()) resG.G->getFirst(in, v);
     475            while (in.valid() && !(resG.free(in)>0) ) { ++in; }
    519476          }
    520477        }
    521478      }
    522       EachEdgeIt& operator++() {
    523         if (out_or_in) {
    524           ++out;
    525           while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    526           while (v.valid() && !out.valid()) {
    527             ++v;
    528             if (v.valid()) G->getFirst(out, v);
    529             while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
    530           }
    531           if (!out.valid()) {
    532             out_or_in=0;
    533             G->getFirst(v);
    534             if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
    535             while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    536             while (v.valid() && !in.valid()) {
    537               ++v;
    538               if (v.valid()) G->getFirst(in, v);
    539               while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    540             } 
    541           }
    542         } else {
    543           ++in;
    544           while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    545           while (v.valid() && !in.valid()) {
    546             ++v;
    547             if (v.valid()) G->getFirst(in, v);
    548             while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
    549           }
    550         }
    551         return *this;
    552       }
    553     };
    554 
    555     void getFirst(EachNodeIt& v) const { G->getFirst(v); }
    556     void getFirst(OutEdgeIt& e, NodeIt v) const {
    557       e=OutEdgeIt(*G, v, *flow, *capacity);
    558     }
    559     void getFirst(EachEdgeIt& e) const {
    560       e=EachEdgeIt(*G, *flow, *capacity);
     479//       EachEdgeIt& operator++() {
     480//      if (out_or_in) {
     481//        ++out;
     482//        while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     483//        while (v.valid() && !out.valid()) {
     484//          ++v;
     485//          if (v.valid()) G->getFirst(out, v);
     486//          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     487//        }
     488//        if (!out.valid()) {
     489//          out_or_in=0;
     490//          G->getFirst(v);
     491//          if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
     492//          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     493//          while (v.valid() && !in.valid()) {
     494//            ++v;
     495//            if (v.valid()) G->getFirst(in, v);
     496//            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     497//          } 
     498//        }
     499//      } else {
     500//        ++in;
     501//        while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     502//        while (v.valid() && !in.valid()) {
     503//          ++v;
     504//          if (v.valid()) G->getFirst(in, v);
     505//          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     506//        }
     507//      }
     508//      return *this;
     509//       }
     510    };
     511
     512    EachNodeIt& getFirst(EachNodeIt& v) const { G->getFirst(v); }
     513    OutEdgeIt& getFirst(OutEdgeIt& e, NodeIt v) const {
     514      e=OutEdgeIt(*this, v);
     515    }
     516    EachEdgeIt& getFirst(EachEdgeIt& e) const {
     517      e=EachEdgeIt(*this);
    561518    }
    562519   
     
    567524        NodeIt v=G->aNode(e.out);
    568525        ++(e.out);
    569         while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
     526        while( G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
    570527        if (!G->valid(e.out)) {
    571528          e.out_or_in=0;
    572           G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
    573           while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     529          G->getFirst(e.in, v);
     530          while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
    574531        }
    575532      } else {
    576533        ++(e.in);
    577         while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     534        while( G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
    578535      }
    579536      return e;
     
    583540      if (e.out_or_in) {
    584541        ++(e.out);
    585         while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
     542        while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
    586543          while (G->valid(e.v) && !G->valid(e.out)) {
    587544            ++(e.v);
    588545            if (G->valid(e.v)) G->getFirst(e.out, e.v);
    589             while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
     546            while (G->valid(e.out) && !(free(e.out)>0) ) { ++(e.out); }
    590547          }
    591548          if (!G->valid(e.out)) {
     
    593550            G->getFirst(e.v);
    594551            if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
    595             while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     552            while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
    596553            while (G->valid(e.v) && !G->valid(e.in)) {
    597554              ++(e.v);
    598555              if (G->valid(e.v)) G->getFirst(e.in, e.v);
    599               while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     556              while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
    600557            } 
    601558          }
    602559        } else {
    603560          ++(e.in);
    604           while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     561          while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
    605562          while (G->valid(e.v) && !G->valid(e.in)) {
    606563            ++(e.v);
    607564            if (G->valid(e.v)) G->getFirst(e.in, e.v);
    608             while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     565            while (G->valid(e.in) && !(free(e.in)>0) ) { ++(e.in); }
    609566          }
    610567        }
     
    642599    bool valid(EdgeIt e) const {
    643600      return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
     601
     602    void augment(const EdgeIt& e, Number a) const {
     603      if (e.out_or_in) 
     604        flow->set(e.out, flow->get(e.out)+a);
     605      else 
     606        flow->set(e.in, flow->get(e.in)-a);
     607    }
     608
     609    Number free(const EdgeIt& e) const {
     610      if (e.out_or_in)
     611        return (capacity->get(e.out)-flow->get(e.out));
     612      else
     613        return (flow->get(e.in));
     614    }
     615
     616    Number free(OldOutEdgeIt out) const {
     617      return (capacity->get(out)-flow->get(out));
     618    }
     619   
     620    Number free(OldInEdgeIt in) const {
     621      return (flow->get(in));
     622    }
    644623
    645624    template<typename T> class NodeMap : public Graph::NodeMap<T> {
     
    680659      }
    681660    };
     661  };
     662
     663  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     664  class ErasingResGraphWrapper : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
     665  protected:
     666    ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
     667    //ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
     668  public:
     669    ErasingResGraphWrapper(const Graph& _G, FlowMap& _flow,
     670                           const CapacityMap& _capacity) :
     671      ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity),
     672      first_out_edges(*this) /*, dist(*this)*/ {
     673      for(EachNodeIt n=this->template first<EachNodeIt>(); this->valid(n); this->next(n)) {
     674        OutEdgeIt e;
     675        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
     676        first_out_edges.set(n, e);
     677      }
     678    }
     679
     680    //void setGraph(Graph& _graph) { graph = &_graph; }
     681    //Graph& getGraph() const { return (*graph); }
     682 
     683    //TrivGraphWrapper() : graph(0) { }
     684    //ErasingResGraphWrapper(Graph& _graph) : graph(&_graph) { }
     685
     686    //typedef Graph BaseGraph;
     687
     688    //typedef typename Graph::NodeIt NodeIt;
     689    //typedef typename Graph::EachNodeIt EachNodeIt;
     690
     691    //typedef typename Graph::EdgeIt EdgeIt;
     692    //typedef typename Graph::OutEdgeIt OutEdgeIt;
     693    //typedef typename Graph::InEdgeIt InEdgeIt;
     694    //typedef typename Graph::SymEdgeIt SymEdgeIt;
     695    //typedef typename Graph::EachEdgeIt EachEdgeIt;
     696
     697    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
     698    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
     699
     700    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
     701    typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
     702    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
     703    //typedef typename Graph::SymEdgeIt SymEdgeIt;
     704    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;
     705
     706    EachNodeIt& getFirst(EachNodeIt& n) const {
     707      return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
     708    }
     709
     710    OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
     711      e=first_out_edges.get(n);
     712      return e;
     713    }
     714   
     715    //ROSSZ template<typename I> I& getFirst(I& i) const { return getFirst(i); }
     716    //ROSSZ template<typename I, typename P> I& getFirst(I& i, const P& p) const {
     717    //  return getFirst(i, p); }
     718   
     719    //template<typename I> I getNext(const I& i) const {
     720    //  return graph->getNext(i); }
     721    //template<typename I> I& next(I &i) const { return graph->next(i); }   
     722
     723    template< typename It > It first() const {
     724      It e; getFirst(e); return e; }
     725
     726    template< typename It > It first(const NodeIt& v) const {
     727      It e; getFirst(e, v); return e; }
     728
     729    //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
     730    //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
     731
     732    //template<typename I> bool valid(const I& i) const
     733    //  { return graph->valid(i); }
     734 
     735    //int nodeNum() const { return graph->nodeNum(); }
     736    //int edgeNum() const { return graph->edgeNum(); }
     737 
     738    //template<typename I> NodeIt aNode(const I& e) const {
     739    //  return graph->aNode(e); }
     740    //template<typename I> NodeIt bNode(const I& e) const {
     741    //  return graph->bNode(e); }
     742 
     743    //NodeIt addNode() const { return graph->addNode(); }
     744    //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
     745    //  return graph->addEdge(tail, head); }
     746 
     747    //void erase(const OutEdgeIt& e) {
     748    //  first_out_edge(this->tail(e))=e;
     749    //}
     750    void erase(const EdgeIt& e) {
     751      OutEdgeIt f(e);
     752      next(f);
     753      first_out_edges.set(this->tail(e), f);
     754    }
     755    //template<typename I> void erase(const I& i) const { graph->erase(i); }
     756 
     757    //void clear() const { graph->clear(); }
     758   
     759    template<typename T> class NodeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
     760    public:
     761      NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
     762        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
     763      NodeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
     764        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
     765    };
     766
     767    template<typename T> class EdgeMap : public ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
     768    public:
     769      EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) :
     770        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
     771      EdgeMap(const ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) :
     772        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
     773    };
     774  };
     775
     776  template<typename GraphWrapper>
     777  class FilterGraphWrapper {
     778  };
     779
     780  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     781  class FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> {
     782
     783    //Graph* graph;
     784 
     785  public:
     786    //typedef Graph BaseGraph;
     787
     788    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeIt NodeIt;
     789    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachNodeIt EachNodeIt;
     790
     791    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
     792    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt OutEdgeIt;
     793    //typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::InEdgeIt InEdgeIt;
     794    //typedef typename Graph::SymEdgeIt SymEdgeIt;
     795    typedef typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EachEdgeIt EachEdgeIt;
     796
     797    //FilterGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt> first_out_edges;
     798   
     799  public:
     800    FilterGraphWrapper(const Graph& _G, FlowMap& _flow,
     801                           const CapacityMap& _capacity) :
     802      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>(_G, _flow, _capacity), dist(*this) {
     803    }
     804
     805    OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const {
     806      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(e, n);
     807      while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e))))
     808        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
     809      return e;
     810    }
     811
     812    EachNodeIt& next(EachNodeIt& e) const {
     813      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
     814    }
     815
     816    OutEdgeIt& next(OutEdgeIt& e) const {
     817      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
     818      while (valid(e) && (dist.get(tail(e))+1!=dist.get(head(e))))
     819        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
     820      return e;
     821    }
     822
     823    EachNodeIt& getFirst(EachNodeIt& n) const {
     824      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::getFirst(n);
     825    }
     826
     827    void erase(const EdgeIt& e) {
     828      OutEdgeIt f(e);
     829      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
     830      while (valid(f) && (dist.get(tail(f))+1!=dist.get(head(f))))
     831        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(f);
     832      first_out_edges.set(this->tail(e), f);
     833    }
     834
     835    //TrivGraphWrapper() : graph(0) { }
     836    //TrivGraphWrapper(Graph& _graph) : graph(&_graph) { }
     837
     838    //void setGraph(Graph& _graph) { graph = &_graph; }
     839    //Graph& getGraph() const { return (*graph); }
     840   
     841    //template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
     842    //template<typename I, typename P> I& getFirst(I& i, const P& p) const {
     843    //  return graph->getFirst(i, p); }
     844   
     845    //template<typename I> I getNext(const I& i) const {
     846    //  return graph->getNext(i); }
     847    //template<typename I> I& next(I &i) const { return graph->next(i); }   
     848
     849    template< typename It > It first() const {
     850      It e; getFirst(e); return e; }
     851
     852    template< typename It > It first(const NodeIt& v) const {
     853      It e; getFirst(e, v); return e; }
     854
     855    //NodeIt head(const EdgeIt& e) const { return graph->head(e); }
     856    //NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
     857
     858    //template<typename I> bool valid(const I& i) const
     859    //  { return graph->valid(i); }
     860 
     861    //template<typename I> void setInvalid(const I &i);
     862    //{ return graph->setInvalid(i); }
     863
     864    //int nodeNum() const { return graph->nodeNum(); }
     865    //int edgeNum() const { return graph->edgeNum(); }
     866 
     867    //template<typename I> NodeIt aNode(const I& e) const {
     868    //  return graph->aNode(e); }
     869    //template<typename I> NodeIt bNode(const I& e) const {
     870    //  return graph->bNode(e); }
     871 
     872    //NodeIt addNode() const { return graph->addNode(); }
     873    //EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
     874    //  return graph->addEdge(tail, head); }
     875 
     876    //template<typename I> void erase(const I& i) const { graph->erase(i); }
     877 
     878    //void clear() const { graph->clear(); }
     879   
     880    template<typename T> class NodeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T> {
     881    public:
     882      NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
     883        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/) { }
     884      NodeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
     885        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<T>(_G /*_G.getGraph()*/, a) { }
     886    };
     887
     888    template<typename T> class EdgeMap : public ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T> {
     889    public:
     890      EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G) :
     891        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/) { }
     892      EdgeMap(const FilterGraphWrapper<ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> >& _G, T a) :
     893        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeMap<T>(_G /*_G.getGraph()*/, a) { }
     894    };
     895
     896  public:
     897    ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<int> dist;
    682898
    683899  };
  • src/work/marci/makefile

    r125 r168  
    1717
    1818edmonds_karp_demo:
    19         $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc
    20         $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo.cc
     19        $(CXX3) $(CXXFLAGS) -g -O3 -I. -I.. -o edmonds_karp_demo edmonds_karp_demo.cc
     20        $(CXX3) $(CXXFLAGS) -g -pg -O3 -I. -I.. -o edmonds_karp_demo_prof edmonds_karp_demo_prof.cc
    2121
    2222edmonds_karp_demo_alpar:
  • src/work/marci_graph_demo.cc

    r155 r168  
    237237    }
    238238    std::cout<<std::endl;*/
    239     max_flow_test.run();
     239    //max_flow_test.run();
    240240   
    241     std::cout << "maximum flow: "<< std::endl;
    242     for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
    243       std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
    244     }
    245     std::cout<<std::endl;
     241    //std::cout << "maximum flow: "<< std::endl;
     242    while (max_flow_test.augmentOnShortestPath()) {
     243      for(EachEdgeIt e=flowG.template first<EachEdgeIt>(); e.valid(); ++e) {
     244        std::cout<<"("<<flowG.tail(e)<< "-"<<flow.get(e)<<"->"<<flowG.head(e)<<") ";
     245      }
     246      std::cout<<std::endl;
     247    }
    246248    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    247249  }
Note: See TracChangeset for help on using the changeset viewer.