COIN-OR::LEMON - Graph Library

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

GraphWrappers?, MapWrappers?

File:
1 edited

Legend:

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

    r243 r266  
    99#include <time_measure.h>
    1010#include <graph_wrapper.h>
     11
     12class CM {
     13public:
     14  template<typename T> int get(T) const {return 1;}
     15};
    1116
    1217using namespace hugo;
     
    8792  {
    8893    //std::cout << "SmartGraph..." << std::endl;
     94    typedef TrivGraphWrapper<const Graph> GW;
     95    GW gw(G);
    8996    std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
    90     Graph::EdgeMap<int> flow(G); //0 flow
     97    GW::EdgeMap<int> flow(G); //0 flow
    9198
    9299    Timer ts;
    93100    ts.reset();
    94101
    95     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    96     //max_flow_test.augmentWithBlockingFlow<Graph>();
     102    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
     103    EMW cw(cap);
     104    MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(G, s, t, flow, cw);
    97105    int i=0;
    98106    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) {
     
    114122  }
    115123
     124//   {
     125//     //std::cout << "SmartGraph..." << std::endl;
     126//     std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
     127//     Graph::EdgeMap<int> flow(G); //0 flow
     128
     129//     Timer ts;
     130//     ts.reset();
     131
     132//     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
     133//     int i=0;
     134//     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
     135// //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
     136// //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     137// //     }
     138// //     std::cout<<std::endl;
     139//       ++i;
     140//     }
     141
     142// //   std::cout << "maximum flow: "<< std::endl;
     143// //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
     144// //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     145// //   }
     146// //   std::cout<<std::endl;
     147//     std::cout << "elapsed time: " << ts << std::endl;
     148//     std::cout << "number of augmentation phases: " << i << std::endl;
     149//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
     150//   }
     151
     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
    116179  {
    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
     180    typedef TrivGraphWrapper<const Graph> GW;
     181    GW gw(G);
     182    std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
     183    GW::EdgeMap<int> flow(gw); //0 flow
    120184
    121185    Timer ts;
    122186    ts.reset();
    123187
    124     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    125     //max_flow_test.augmentWithBlockingFlow<Graph>();
     188    //CM cm;
     189    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
     190    EMW cw(cap);
     191    MaxFlow<GW, int, GW::EdgeMap<int>, EMW> max_flow_test(gw, s, t, flow, cw);
    126192    int i=0;
    127     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) {
     193    while (max_flow_test.augmentOnShortestPath()) {
    128194//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    129195//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
     
    143209  }
    144210
    145   {
    146     std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
    147     Graph::EdgeMap<int> flow(G); //0 flow
    148 
    149     Timer ts;
    150     ts.reset();
    151 
    152     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    153     //max_flow_test.augmentWithBlockingFlow<Graph>();
    154     int i=0;
    155     while (max_flow_test.augmentOnBlockingFlow2()) {
    156 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    157 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    158 //     }
    159 //     std::cout<<std::endl;
    160       ++i;
    161     }
    162 
    163 //   std::cout << "maximum flow: "<< std::endl;
    164 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
    165 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    166 //   }
    167 //   std::cout<<std::endl;
    168     std::cout << "elapsed time: " << ts << std::endl;
    169     std::cout << "number of augmentation phases: " << i << std::endl;
    170     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    171   }
    172 
    173   {
    174     std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
    175     Graph::EdgeMap<int> flow(G); //0 flow
    176 
    177     Timer ts;
    178     ts.reset();
    179 
    180     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
    181     //max_flow_test.augmentWithBlockingFlow<Graph>();
    182     int i=0;
    183     while (max_flow_test.augmentOnShortestPath()) {
    184 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) {
    185 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    186 //     }
    187 //     std::cout<<std::endl;
    188       ++i;
    189     }
    190 
    191 //   std::cout << "maximum flow: "<< std::endl;
    192 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) {
    193 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
    194 //   }
    195 //   std::cout<<std::endl;
    196     std::cout << "elapsed time: " << ts << std::endl;
    197     std::cout << "number of augmentation phases: " << i << std::endl;
    198     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    199   }
    200 
    201211
    202212  return 0;
Note: See TracChangeset for help on using the changeset viewer.