COIN-OR::LEMON - Graph Library

Changeset 268:f4eb1ae59b50 in lemon-0.x for src/work/marci


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

blocking flows

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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.