COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 467:8cab0547eeae in lemon-0.x


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

preflow maxflow ...

File:
1 edited

Legend:

Unmodified
Added
Removed

  • src/work/marci/edmonds_karp.h

    r466 r467  
    1515namespace hugo {
    1616
    17   template <typename Graph, typename Number,
    18             typename CapacityMap, typename FlowMap>
     17  template <typename Graph, typename Num,
     18            typename CapMap, typename FlowMap>
    1919  class MaxFlow {
    2020  protected:
    … …  
    2727    Node s;
    2828    Node t;
    29     const CapacityMap* capacity;
     29    const CapMap* capacity;
    3030    FlowMap* flow;
    31     typedef ResGraphWrapper<const Graph, Number, CapacityMap, FlowMap> ResGW;
     31    typedef ResGraphWrapper<const Graph, Num, CapMap, FlowMap> ResGW;
    3232    typedef typename ResGW::OutEdgeIt ResGWOutEdgeIt;
    3333    typedef typename ResGW::Edge ResGWEdge;
    … …  
    3838  public:
    3939
    40     MaxFlow(const Graph& _g, Node _s, Node _t, const CapacityMap& _capacity,
     40    MaxFlow(const Graph& _g, Node _s, Node _t, const CapMap& _capacity,
    4141            FlowMap& _flow) :
    4242      g(&_g), s(_s), t(_t), capacity(&_capacity), flow(&_flow), level(_g) { }
    … …  
    5454      pred.set(s, INVALID);
    5555     
    56       typename ResGW::template NodeMap<Number> free(res_graph);
     56      typename ResGW::template NodeMap<Num> free(res_graph);
    5757       
    5858      //searching for augmenting path
    … …  
    7676      if (_augment) {
    7777        Node n=t;
    78         Number augment_value=free[t];
     78        Num augment_value=free[t];
    7979        while (res_graph.valid(pred[n])) {
    8080          ResGWEdge e=pred[n];
    … …  
    146146      typename MG::Node tF=res_graph_to_F[t];
    147147      typename MG::template EdgeMap<ResGWEdge> original_edge(F);
    148       typename MG::template EdgeMap<Number> residual_capacity(F);
     148      typename MG::template EdgeMap<Num> residual_capacity(F);
    149149
    150150      //Making F to the graph containing the edges of the residual graph
    … …  
    174174        //invalid iterators for sources
    175175
    176         typename MG::template NodeMap<Number> free(F);
     176        typename MG::template NodeMap<Num> free(F);
    177177
    178178        dfs.pushAndSetReached(sF);     
    … …  
    203203        if (__augment) {
    204204          typename MG::Node n=tF;
    205           Number augment_value=free[tF];
     205          Num augment_value=free[tF];
    206206          while (F.valid(pred[n])) {
    207207            typename MG::Edge e=pred[n];
    … …  
    249249      typename MG::Node tF=res_graph_to_F[t];
    250250      typename MG::template EdgeMap<ResGWEdge> original_edge(F);
    251       typename MG::template EdgeMap<Number> residual_capacity(F);
     251      typename MG::template EdgeMap<Num> residual_capacity(F);
    252252
    253253      while ( !bfs.finished() ) {
    … …  
    284284        //invalid iterators for sources
    285285
    286         typename MG::template NodeMap<Number> free(F);
     286        typename MG::template NodeMap<Num> free(F);
    287287
    288288        dfs.pushAndSetReached(sF);     
    … …  
    313313        if (__augment) {
    314314          typename MG::Node n=tF;
    315           Number augment_value=free[tF];
     315          Num augment_value=free[tF];
    316316          while (F.valid(pred[n])) {
    317317            typename MG::Edge e=pred[n];
    … …  
    386386        //invalid iterators for sources
    387387
    388         typename ErasingResGW::template NodeMap<Number>
     388        typename ErasingResGW::template NodeMap<Num>
    389389          free1(erasing_res_graph);
    390390
    … …  
    428428        if (__augment) {
    429429          typename ErasingResGW::Node n=typename FilterResGW::Node(typename ResGW::Node(t));
    430 //        typename ResGW::NodeMap<Number> a(res_graph);
     430//        typename ResGW::NodeMap<Num> a(res_graph);
    431431//        typename ResGW::Node b;
    432 //        Number j=a[b];
    433 //        typename FilterResGW::NodeMap<Number> a1(filter_res_graph);
     432//        Num j=a[b];
     433//        typename FilterResGW::NodeMap<Num> a1(filter_res_graph);
    434434//        typename FilterResGW::Node b1;
    435 //        Number j1=a1[b1];
    436 //        typename ErasingResGW::NodeMap<Number> a2(erasing_res_graph);
     435//        Num j1=a1[b1];
     436//        typename ErasingResGW::NodeMap<Num> a2(erasing_res_graph);
    437437//        typename ErasingResGW::Node b2;
    438 //        Number j2=a2[b2];
    439           Number augment_value=free1[n];
     438//        Num j2=a2[b2];
     439          Num augment_value=free1[n];
    440440          while (erasing_res_graph.valid(pred[n])) {
    441441            typename ErasingResGW::OutEdgeIt e=pred[n];
    … …  
    470470    }
    471471
    472     Number flowValue() {
    473       Number a=0;
     472    Num flowValue() {
     473      Num a=0;
    474474      OutEdgeIt e;
    475475      for(g->first(e, s); g->valid(e); g->next(e)) {
    … …  
    482482
    483483
    484 //   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     484//   template <typename Graph, typename Num, typename FlowMap, typename CapMap>
    485485//   class MaxMatching {
    486486//   public:
    … …  
    501501//     //Node t;
    502502//     FlowMap* flow;
    503 //     const CapacityMap* capacity;
    504 //     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
     503//     const CapMap* capacity;
     504//     typedef ResGraphWrapper<Graph, Num, FlowMap, CapMap > AugGraph;
    505505//     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    506506//     typedef typename AugGraph::Edge AugEdge;
    … …  
    508508
    509509//   public:
    510 //     MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapacityMap& _capacity) :
     510//     MaxMatching(const Graph& _G, SMap& _S, TMap& _T, FlowMap& _flow, const CapMap& _capacity) :
    511511//       G(&_G), S(&_S), T(&_T), flow(&_flow), capacity(&_capacity), used(_G) { }
    512512//     bool augmentOnShortestPath() {
    … …  
    519519//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
    520520//      if ((S->get(s)) && (used.get(s)<1) ) {
    521 //        //Number u=0;
     521//        //Num u=0;
    522522//        //for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
    523523//        //u+=flow->get(e);
    … …  
    529529//       }
    530530     
    531 //       typename AugGraph::NodeMap<Number> free(res_graph);
     531//       typename AugGraph::NodeMap<Num> free(res_graph);
    532532       
    533533//       Node n;
    … …  
    546546//        n=res_graph.head(e);
    547547//        if (T->get(n) && (used.get(n)<1) ) {
    548 //          //Number u=0;
     548//          //Num u=0;
    549549//          //for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
    550550//          //u+=flow->get(f);
    … …  
    562562//      //Node n=t;
    563563//      used.set(n, 1); //mind2 vegen jav
    564 //      Number augment_value=free.get(n);
     564//      Num augment_value=free.get(n);
    565565//      while (res_graph.valid(pred.get(n))) {
    566566//        AugEdge e=pred.get(n);
    … …  
    589589// //       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
    590590// //   if (S->get(s)) {
    591 // //     Number u=0;
     591// //     Num u=0;
    592592// //     for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
    593593// //       u+=flow->get(e);
    … …  
    624624
    625625// //       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
    626 // //       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
     626// //       typename MutableGraph::EdgeMap<Num> residual_capacity(F);
    627627
    628628// //       //Making F to the graph containing the edges of the residual graph
    … …  
    649649// //   //invalid iterators for sources
    650650
    651 // //   typename MutableGraph::NodeMap<Number> free(F);
     651// //   typename MutableGraph::NodeMap<Num> free(F);
    652652
    653653// //   dfs.pushAndSetReached(sF);     
    … …  
    678678// //   if (__augment) {
    679679// //     typename MutableGraph::Node n=tF;
    680 // //     Number augment_value=free.get(tF);
     680// //     Num augment_value=free.get(tF);
    681681// //     while (F.valid(pred.get(n))) {
    682682// //       typename MutableGraph::Edge e=pred.get(n);
    … …  
    697697//       bool _augment=false;
    698698
    699 //       //typedef ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> EAugGraph;
    700 //       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap> > EAugGraph;
     699//       //typedef ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap> EAugGraph;
     700//       typedef FilterGraphWrapper< ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap> > EAugGraph;
    701701//       typedef typename EAugGraph::OutEdgeIt EAugOutEdgeIt;
    702702//       typedef typename EAugGraph::Edge EAugEdge;
    … …  
    706706//       //typedef typename EAugGraph::NodeMap<bool> ReachedMap;
    707707//       BfsIterator<
    708 //      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>,
    709 //      /*typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt,*/
    710 //      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::NodeMap<bool> > bfs(res_graph);
     708//      ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>,
     709//      /*typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt,*/
     710//      ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::NodeMap<bool> > bfs(res_graph);
    711711
    712712
    … …  
    714714//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
    715715//      if (S->get(s)) {
    716 //        Number u=0;
     716//        Num u=0;
    717717//        for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
    718718//          u+=flow->get(e);
    … …  
    727727//       //bfs.pushAndSetReached(s);
    728728
    729 //       typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::
     729//       typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::
    730730//      NodeMap<int>& dist=res_graph.dist;
    731731
    732732//       while ( !bfs.finished() ) {
    733 //      typename ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::OutEdgeIt e=bfs;
     733//      typename ErasingResGraphWrapper<Graph, Num, FlowMap, CapMap>::OutEdgeIt e=bfs;
    734734//      if (res_graph.valid(e) && bfs.isBNodeNewlyReached()) {
    735735//        dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    … …  
    751751//      //invalid iterators for sources
    752752
    753 //      typename EAugGraph::NodeMap<Number> free(res_graph);
     753//      typename EAugGraph::NodeMap<Num> free(res_graph);
    754754
    755755
    … …  
    757757//       for(NodeIt s=G->template first<NodeIt>(); G->valid(s); G->next(s)) {
    758758//      if (S->get(s)) {
    759 //        Number u=0;
     759//        Num u=0;
    760760//        for(OutEdgeIt e=G->template first<OutEdgeIt>(s); G->valid(e); G->next(e))
    761761//          u+=flow->get(e);
    … …  
    788788//            n=w;
    789789//            if (T->get(w)) {
    790 //              Number u=0;
     790//              Num u=0;
    791791//              for(InEdgeIt f=G->template first<InEdgeIt>(n); G->valid(f); G->next(f))
    792792//                u+=flow->get(f);
    … …  
    806806//      if (__augment) {
    807807//        // typename EAugGraph::Node n=t;
    808 //        Number augment_value=free.get(n);
     808//        Num augment_value=free.get(n);
    809809//        while (res_graph.valid(pred.get(n))) {
    810810//          EAugEdge e=pred.get(n);
    … …  
    836836// //       }
    837837// //     }
    838 //     Number flowValue() {
    839 //       Number a=0;
     838//     Num flowValue() {
     839//       Num a=0;
    840840//       EdgeIt e;
    841841//       for(G->/*getF*/first(e); G->valid(e); G->next(e)) {
    … …  
    851851
    852852 
    853 // //   template <typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     853// //   template <typename Graph, typename Num, typename FlowMap, typename CapMap>
    854854// //   class MaxFlow2 {
    855855// //   public:
    … …  
    864864// //     std::list<Node>& T;
    865865// //     FlowMap& flow;
    866 // //     const CapacityMap& capacity;
    867 // //     typedef ResGraphWrapper<Graph, Number, FlowMap, CapacityMap > AugGraph;
     866// //     const CapMap& capacity;
     867// //     typedef ResGraphWrapper<Graph, Num, FlowMap, CapMap > AugGraph;
    868868// //     typedef typename AugGraph::OutEdgeIt AugOutEdgeIt;
    869869// //     typedef typename AugGraph::Edge AugEdge;
    … …  
    871871// //     typename Graph::NodeMap<bool> TMap;
    872872// //   public:
    873 // //     MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapacityMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
     873// //     MaxFlow2(const Graph& _G, std::list<Node>& _S, std::list<Node>& _T, FlowMap& _flow, const CapMap& _capacity) : G(_G), S(_S), T(_T), flow(_flow), capacity(_capacity), SMap(_G), TMap(_G) {
    874874// //       for(typename std::list<Node>::const_iterator i=S.begin();
    875875// //     i!=S.end(); ++i) {
    … …  
    897897// //       //filled up with invalid iterators
    898898     
    899 // //       typename AugGraph::NodeMap<Number> free(res_graph);
     899// //       typename AugGraph::NodeMap<Num> free(res_graph);
    900900       
    901901// //       //searching for augmenting path
    … …  
    923923// //       if (_augment) {
    924924// //   Node n=reached_t_node;
    925 // //   Number augment_value=free.get(reached_t_node);
     925// //   Num augment_value=free.get(reached_t_node);
    926926// //   while (pred.get(n).valid()) {
    927927// //     AugEdge e=pred.get(n);
    … …  
    936936// //       while (augment()) { }
    937937// //     }
    938 // //     Number flowValue() {
    939 // //       Number a=0;
     938// //     Num flowValue() {
     939// //       Num a=0;
    940940// //       for(typename std::list<Node>::const_iterator i=S.begin();
    941941// //     i!=S.end(); ++i) {
Note: See TracChangeset for help on using the changeset viewer.