COIN-OR::LEMON - Graph Library

Changeset 268:f4eb1ae59b50 in lemon-0.x


Ignore:
Timestamp:
03/30/04 19:47:51 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@374
Message:

blocking flows

Location:
src/work
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/edmonds_karp.h

    r266 r268  
    433433    }
    434434
    435 //     template<typename MutableGraph> bool augmentOnBlockingFlow1() {     
    436 //       bool _augment=false;
    437 
    438 //       AugGraph res_graph(*G, *flow, *capacity);
    439 
    440 //       //bfs for distances on the residual graph
    441 //       typedef typename AugGraph::NodeMap<bool> ReachedMap;
    442 //       BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
    443 //       bfs.pushAndSetReached(s);
    444 //       typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
    445 
    446 //       //F will contain the physical copy of the residual graph
    447 //       //with the set of edges which areon shortest paths
    448 //       MutableGraph F;
    449 //       typename AugGraph::NodeMap<typename MutableGraph::Node>
    450 //      res_graph_to_F(res_graph);
    451 //       for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
    452 //      res_graph_to_F.set(n, F.addNode());
    453 //       }
    454 //       typename MutableGraph::Node sF=res_graph_to_F.get(s);
    455 //       typename MutableGraph::Node tF=res_graph_to_F.get(t);
    456 //       typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
    457 //       typename MutableGraph::EdgeMap<Number> residual_capacity(F);
    458 
    459 //       while ( !bfs.finished() ) {
    460 //      AugOutEdgeIt e=bfs;
    461 //      if (res_graph.valid(e)) {
    462 //        if (bfs.isBNodeNewlyReached()) {
    463 //          dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
    464 //          typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    465 //          original_edge.update();
    466 //          original_edge.set(f, e);
    467 //          residual_capacity.update();
    468 //          residual_capacity.set(f, res_graph.free(e));
    469 //        } else {
    470 //          if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
    471 //            typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
    472 //            original_edge.update();
    473 //            original_edge.set(f, e);
    474 //            residual_capacity.update();
    475 //            residual_capacity.set(f, res_graph.free(e));
    476 //          }
    477 //        }
    478 //      }
    479 //      ++bfs;
    480 //       } //computing distances from s in the residual graph
    481 
    482 //       bool __augment=true;
    483 
    484 //       while (__augment) {
    485 //      __augment=false;
    486 //      //computing blocking flow with dfs
    487 //      typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
    488 //      DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
    489 //      typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
    490 //      pred.set(sF, typename MutableGraph::Edge(INVALID));
    491 //      //invalid iterators for sources
    492 
    493 //      typename MutableGraph::NodeMap<Number> free(F);
    494 
    495 //      dfs.pushAndSetReached(sF);     
    496 //      while (!dfs.finished()) {
    497 //        ++dfs;
    498 //        if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
    499 //          if (dfs.isBNodeNewlyReached()) {
    500 //            typename MutableGraph::Node v=F.aNode(dfs);
    501 //            typename MutableGraph::Node w=F.bNode(dfs);
    502 //            pred.set(w, dfs);
    503 //            if (F.valid(pred.get(v))) {
    504 //              free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
    505 //            } else {
    506 //              free.set(w, residual_capacity.get(dfs));
    507 //            }
    508 //            if (w==tF) {
    509 //              __augment=true;
    510 //              _augment=true;
    511 //              break;
    512 //            }
     435    template<typename MutableGraph> bool augmentOnBlockingFlow1() {     
     436      bool _augment=false;
     437
     438      AugGraph res_graph(gw, *flow, *capacity);
     439
     440      //bfs for distances on the residual graph
     441      typedef typename AugGraph::NodeMap<bool> ReachedMap;
     442      BfsIterator5< AugGraph, ReachedMap > bfs(res_graph);
     443      bfs.pushAndSetReached(s);
     444      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
     445
     446      //F will contain the physical copy of the residual graph
     447      //with the set of edges which areon shortest paths
     448      MutableGraph F;
     449      typename AugGraph::NodeMap<typename MutableGraph::Node>
     450        res_graph_to_F(res_graph);
     451      for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
     452        res_graph_to_F.set(n, F.addNode());
     453      }
     454      typename MutableGraph::Node sF=res_graph_to_F.get(s);
     455      typename MutableGraph::Node tF=res_graph_to_F.get(t);
     456      typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
     457      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
     458
     459      while ( !bfs.finished() ) {
     460        AugOutEdgeIt e=bfs;
     461        if (res_graph.valid(e)) {
     462          if (bfs.isBNodeNewlyReached()) {
     463            dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     464            typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     465            original_edge.update();
     466            original_edge.set(f, e);
     467            residual_capacity.update();
     468            residual_capacity.set(f, res_graph.free(e));
     469          } else {
     470            if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
     471              typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     472              original_edge.update();
     473              original_edge.set(f, e);
     474              residual_capacity.update();
     475              residual_capacity.set(f, res_graph.free(e));
     476            }
     477          }
     478        }
     479        ++bfs;
     480      } //computing distances from s in the residual graph
     481
     482      bool __augment=true;
     483
     484      while (__augment) {
     485        __augment=false;
     486        //computing blocking flow with dfs
     487        typedef typename TrivGraphWrapper<MutableGraph>::NodeMap<bool> BlockingReachedMap;
     488        DfsIterator5< TrivGraphWrapper<MutableGraph>/*, typename MutableGraph::OutEdgeIt*/, BlockingReachedMap > dfs(F);
     489        typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
     490        pred.set(sF, typename MutableGraph::Edge(INVALID));
     491        //invalid iterators for sources
     492
     493        typename MutableGraph::NodeMap<Number> free(F);
     494
     495        dfs.pushAndSetReached(sF);     
     496        while (!dfs.finished()) {
     497          ++dfs;
     498          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
     499            if (dfs.isBNodeNewlyReached()) {
     500              typename MutableGraph::Node v=F.aNode(dfs);
     501              typename MutableGraph::Node w=F.bNode(dfs);
     502              pred.set(w, dfs);
     503              if (F.valid(pred.get(v))) {
     504                free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
     505              } else {
     506                free.set(w, residual_capacity.get(dfs));
     507              }
     508              if (w==tF) {
     509                __augment=true;
     510                _augment=true;
     511                break;
     512              }
    513513             
    514 //          } else {
    515 //            F.erase(typename MutableGraph::OutEdgeIt(dfs));
    516 //          }
    517 //        }
    518 //      }
    519 
    520 //      if (__augment) {
    521 //        typename MutableGraph::Node n=tF;
    522 //        Number augment_value=free.get(tF);
    523 //        while (F.valid(pred.get(n))) {
    524 //          typename MutableGraph::Edge e=pred.get(n);
    525 //          res_graph.augment(original_edge.get(e), augment_value);
    526 //          n=F.tail(e);
    527 //          if (residual_capacity.get(e)==augment_value)
    528 //            F.erase(e);
    529 //          else
    530 //            residual_capacity.set(e, residual_capacity.get(e)-augment_value);
    531 //        }
    532 //      }
     514            } else {
     515              F.erase(typename MutableGraph::OutEdgeIt(dfs));
     516            }
     517          }
     518        }
     519
     520        if (__augment) {
     521          typename MutableGraph::Node n=tF;
     522          Number augment_value=free.get(tF);
     523          while (F.valid(pred.get(n))) {
     524            typename MutableGraph::Edge e=pred.get(n);
     525            res_graph.augment(original_edge.get(e), augment_value);
     526            n=F.tail(e);
     527            if (residual_capacity.get(e)==augment_value)
     528              F.erase(e);
     529            else
     530              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
     531          }
     532        }
    533533       
    534 //       }
     534      }
    535535           
    536 //       return _augment;
    537 //     }
     536      return _augment;
     537    }
     538
    538539//     bool augmentOnBlockingFlow2() {
    539540//       bool _augment=false;
  • src/work/marci/edmonds_karp_demo.cc

    r267 r268  
    122122  }
    123123
     124  {
     125    //std::cout << "SmartGraph..." << std::endl;
     126    typedef TrivGraphWrapper<const Graph> GW;
     127    GW gw(G);
     128    std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
     129    GW::EdgeMap<int> flow(G); //0 flow
     130
     131    Timer ts;
     132    ts.reset();
     133
     134    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
     135    EMW cw(cap);
     136    MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
     137    int i=0;
     138    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
     139//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
     140//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     141//     }
     142//     std::cout<<std::endl;
     143      ++i;
     144    }
     145
     146//   std::cout << "maximum flow: "<< std::endl;
     147//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
     148//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     149//   }
     150//   std::cout<<std::endl;
     151    std::cout << "elapsed time: " << ts << std::endl;
     152    std::cout << "number of augmentation phases: " << i << std::endl;
     153    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     154  }
     155
    124156//   {
    125 //     //std::cout << "SmartGraph..." << std::endl;
    126 //     std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
     157//     std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
    127158//     Graph::EdgeMap<int> flow(G); //0 flow
    128159
     
    132163//     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    133164//     int i=0;
    134 //     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
     165//     while (max_flow_test.augmentOnBlockingFlow2()) {
    135166// //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    136167// //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     
    150181//   }
    151182
    152 //   {
    153 //     std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
    154 //     Graph::EdgeMap<int> flow(G); //0 flow
    155 
    156 //     Timer ts;
    157 //     ts.reset();
    158 
    159 //     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    160 //     int i=0;
    161 //     while (max_flow_test.augmentOnBlockingFlow2()) {
    162 // //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    163 // //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    164 // //     }
    165 // //     std::cout<<std::endl;
    166 //       ++i;
    167 //     }
    168 
    169 // //   std::cout << "maximum flow: "<< std::endl;
    170 // //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
    171 // //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    172 // //   }
    173 // //   std::cout<<std::endl;
    174 //     std::cout << "elapsed time: " << ts << std::endl;
    175 //     std::cout << "number of augmentation phases: " << i << std::endl;
    176 //     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    177 //   }
    178 
    179183  {
    180184    typedef TrivGraphWrapper<const Graph> GW;
Note: See TracChangeset for help on using the changeset viewer.