COIN-OR::LEMON - Graph Library

Changeset 206:47f62d789fe7 in lemon-0.x


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

.

Location:
src/work
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/edmonds_karp.h

    r198 r206  
    357357        }
    358358      }
     359
     360      bool __augment=true;
     361
     362      while (__augment) {
     363        __augment=false;
     364        //computing blocking flow with dfs
     365        typedef typename MutableGraph::NodeMap<bool> BlockingReachedMap;
     366        DfsIterator4< MutableGraph, typename MutableGraph::OutEdgeIt, BlockingReachedMap > dfs(F);
     367        typename MutableGraph::NodeMap<typename MutableGraph::Edge> pred(F);
     368        pred.set(sF, typename MutableGraph::Edge(INVALID));
     369        //invalid iterators for sources
     370
     371        typename MutableGraph::NodeMap<Number> free(F);
     372
     373        dfs.pushAndSetReached(sF);     
     374        while (!dfs.finished()) {
     375          ++dfs;
     376          if (F.valid(typename MutableGraph::OutEdgeIt(dfs))) {
     377            if (dfs.isBNodeNewlyReached()) {
     378              typename MutableGraph::Node v=F.aNode(dfs);
     379              typename MutableGraph::Node w=F.bNode(dfs);
     380              pred.set(w, dfs);
     381              if (F.valid(pred.get(v))) {
     382                free.set(w, std::min(free.get(v), residual_capacity.get(dfs)));
     383              } else {
     384                free.set(w, residual_capacity.get(dfs));
     385              }
     386              if (w==tF) {
     387                __augment=true;
     388                _augment=true;
     389                break;
     390              }
     391             
     392            } else {
     393              F.erase(typename MutableGraph::OutEdgeIt(dfs));
     394            }
     395          }
     396        }
     397
     398        if (__augment) {
     399          typename MutableGraph::Node n=tF;
     400          Number augment_value=free.get(tF);
     401          while (F.valid(pred.get(n))) {
     402            typename MutableGraph::Edge e=pred.get(n);
     403            res_graph.augment(original_edge.get(e), augment_value);
     404            n=F.tail(e);
     405            if (residual_capacity.get(e)==augment_value)
     406              F.erase(e);
     407            else
     408              residual_capacity.set(e, residual_capacity.get(e)-augment_value);
     409          }
     410        }
     411       
     412      }
     413           
     414      return _augment;
     415    }
     416    template<typename MutableGraph> bool augmentOnBlockingFlow1() {     
     417      bool _augment=false;
     418
     419      AugGraph res_graph(*G, *flow, *capacity);
     420
     421      //bfs for distances on the residual graph
     422      typedef typename AugGraph::NodeMap<bool> ReachedMap;
     423      BfsIterator4< AugGraph, AugOutEdgeIt, ReachedMap > bfs(res_graph);
     424      bfs.pushAndSetReached(s);
     425      typename AugGraph::NodeMap<int> dist(res_graph); //filled up with 0's
     426
     427      //F will contain the physical copy of the residual graph
     428      //with the set of edges which areon shortest paths
     429      MutableGraph F;
     430      typename AugGraph::NodeMap<typename MutableGraph::Node>
     431        res_graph_to_F(res_graph);
     432      for(typename AugGraph::NodeIt n=res_graph.template first<typename AugGraph::NodeIt>(); res_graph.valid(n); res_graph.next(n)) {
     433        res_graph_to_F.set(n, F.addNode());
     434      }
     435      typename MutableGraph::Node sF=res_graph_to_F.get(s);
     436      typename MutableGraph::Node tF=res_graph_to_F.get(t);
     437      typename MutableGraph::EdgeMap<AugEdge> original_edge(F);
     438      typename MutableGraph::EdgeMap<Number> residual_capacity(F);
     439
     440      while ( !bfs.finished() ) {
     441        AugOutEdgeIt e=bfs;
     442        if (res_graph.valid(e)) {
     443          if (bfs.isBNodeNewlyReached()) {
     444            dist.set(res_graph.head(e), dist.get(res_graph.tail(e))+1);
     445            typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     446            original_edge.update();
     447            original_edge.set(f, e);
     448            residual_capacity.update();
     449            residual_capacity.set(f, res_graph.free(e));
     450          } else {
     451            if (dist.get(res_graph.head(e))==(dist.get(res_graph.tail(e))+1)) {
     452              typename MutableGraph::Edge f=F.addEdge(res_graph_to_F.get(res_graph.tail(e)), res_graph_to_F.get(res_graph.head(e)));
     453              original_edge.update();
     454              original_edge.set(f, e);
     455              residual_capacity.update();
     456              residual_capacity.set(f, res_graph.free(e));
     457            }
     458          }
     459        }
     460        ++bfs;
     461      } //computing distances from s in the residual graph
    359462
    360463      bool __augment=true;
  • src/work/marci/dimacs.h

    r180 r206  
    2626        getline(is, str);
    2727        break;
    28 //       case 't': //type
    29 //      getline(is, str);
    30 //      break;
    3128      case 'p': //problem definition
    3229        is >> problem >> n >> m;
  • src/work/marci/edmonds_karp_demo.cc

    r188 r206  
    3535  typedef ListGraph MutableGraph;
    3636
    37 //  typedef SmartGraph Graph;
    38   typedef ListGraph Graph;
     37  typedef SmartGraph Graph;
     38  //typedef ListGraph Graph;
    3939  typedef Graph::Node Node;
    4040  typedef Graph::EdgeIt EdgeIt;
     
    115115
    116116  {
     117    std::cout << "SmartGraph..." << std::endl;
     118    std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
     119    Graph::EdgeMap<int> flow(G); //0 flow
     120
     121    Timer ts;
     122    ts.reset();
     123
     124    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
     125    //max_flow_test.augmentWithBlockingFlow<Graph>();
     126    int i=0;
     127    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
     128//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
     129//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     130//     }
     131//     std::cout<<std::endl;
     132      ++i;
     133    }
     134
     135//   std::cout << "maximum flow: "<< std::endl;
     136//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
     137//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     138//   }
     139//   std::cout<<std::endl;
     140    std::cout << "elapsed time: " << ts << std::endl;
     141    std::cout << "number of augmentation phases: " << i << std::endl;
     142    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     143  }
     144
     145  {
    117146    std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
    118147    Graph::EdgeMap<int> flow(G); //0 flow
Note: See TracChangeset for help on using the changeset viewer.