COIN-OR::LEMON - Graph Library

Ignore:
Timestamp:
02/27/04 13:39:15 (16 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@180
Message:

Dinits blocking flow added to edmonds_karp_demo.hh.

File:
1 edited

Legend:

Unmodified
Added
Removed
  • src/work/marci/edmonds_karp_demo.cc

    r105 r133  
    2020  readDimacsMaxFlow(std::cin, G, s, t, cap);
    2121
    22 /*
    23   double pre_time_copy=currTime();
    24   ListGraph F;
    25   ListGraph::NodeMap<NodeIt> G_to_F(G);
    26   typedef ListGraph::EachNodeIt EachNodeIt;
    27   for(EachNodeIt n=G.first<EachNodeIt>(); n.valid(); ++n) {
    28     G_to_F.set(n, F.addNode());
    29   }
    30   for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
    31     F.addEdge(G_to_F.get(G.tail(e)), G_to_F.get(G.head(e)));
    32   }
    33   double post_time_copy=currTime();
    34   std::cout << "copy time: " << post_time_copy-pre_time_copy << " sec"<< std::endl;
    35 */
    36 
    37   std::cout << "edmonds karp demo..." << std::endl;
     22  {
     23  std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
    3824  ListGraph::EdgeMap<int> flow(G); //0 flow
    3925
    4026  double pre_time=currTime();
    4127  MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    42   max_flow_test.augmentWithBlockingFlow();
    43   max_flow_test.run();
     28  //max_flow_test.augmentWithBlockingFlow<ListGraph>();
     29  max_flow_test.run<ListGraph>();
    4430  double post_time=currTime();
     31
    4532  //std::cout << "maximum flow: "<< std::endl;
    4633  //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
     
    5037  std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl;
    5138  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     39  }
     40
     41  {
     42  std::cout << "edmonds karp demo (shortest path augmentation)..." << std::endl;
     43  ListGraph::EdgeMap<int> flow(G); //0 flow
     44
     45  double pre_time=currTime();
     46  MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
     47  //max_flow_test.augmentWithBlockingFlow<ListGraph>();
     48  max_flow_test.run();
     49  double post_time=currTime();
     50
     51  //std::cout << "maximum flow: "<< std::endl;
     52  //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
     53  //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     54  //}
     55  //std::cout<<std::endl;
     56  std::cout << "elapsed time: " << post_time-pre_time << " sec"<< std::endl;
     57  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     58  }
    5259
    5360  return 0;
Note: See TracChangeset for help on using the changeset viewer.