src/work/marci/edmonds_karp_demo.cc
author marci
Mon, 05 Apr 2004 15:02:39 +0000
changeset 301 7eb324ed5da3
parent 269 07af3069c0b8
child 303 1b377a730d02
permissions -rw-r--r--
kicsi moveolgatas
marci@174
     1
// -*- c++ -*-
marci@73
     2
#include <iostream>
marci@73
     3
#include <fstream>
marci@73
     4
marci@174
     5
#include <list_graph.h>
marci@174
     6
#include <smart_graph.h>
marci@174
     7
#include <dimacs.h>
marci@174
     8
#include <edmonds_karp.h>
marci@73
     9
#include <time_measure.h>
marci@155
    10
#include <graph_wrapper.h>
marci@73
    11
marci@266
    12
class CM {
marci@266
    13
public:
marci@266
    14
  template<typename T> int get(T) const {return 1;}
marci@266
    15
};
marci@266
    16
alpar@105
    17
using namespace hugo;
marci@73
    18
marci@73
    19
// Use a DIMACS max flow file as stdin.
marci@73
    20
// read_dimacs_demo < dimacs_max_flow_file
marci@139
    21
marci@174
    22
marci@174
    23
//   struct Ize {
marci@174
    24
//   };
marci@139
    25
  
marci@174
    26
//   struct Mize {
marci@174
    27
//     Ize bumm;
marci@174
    28
//   };
marci@139
    29
marci@174
    30
//   template <typename B>
marci@174
    31
//     class Huha {
marci@174
    32
//     public:
marci@174
    33
//       int u;
marci@174
    34
//       B brr;
marci@174
    35
//     };
marci@174
    36
marci@139
    37
marci@73
    38
int main(int, char **) {
marci@73
    39
marci@174
    40
  typedef ListGraph MutableGraph;
marci@139
    41
marci@243
    42
  //typedef SmartGraph Graph;
marci@243
    43
  typedef ListGraph Graph;
marci@174
    44
  typedef Graph::Node Node;
marci@174
    45
  typedef Graph::EdgeIt EdgeIt;
marci@139
    46
marci@139
    47
marci@174
    48
//   Mize mize[10];
marci@174
    49
//   Mize bize[0];
marci@174
    50
//   Mize zize;
marci@174
    51
//   typedef Mize Tize[0];
marci@146
    52
marci@174
    53
//   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
marci@174
    54
//   std::cout << sizeof(bize) << std::endl;
marci@146
    55
marci@146
    56
marci@174
    57
//   Huha<Tize> k;
marci@174
    58
//   std::cout << sizeof(k) << std::endl;
marci@139
    59
marci@174
    60
marci@174
    61
//   struct Bumm {
marci@174
    62
//     //int a;
marci@174
    63
//     bool b;
marci@174
    64
//   };
marci@174
    65
marci@174
    66
//   std::cout << sizeof(Bumm) << std::endl;
marci@174
    67
marci@174
    68
marci@174
    69
  Graph G;
marci@174
    70
  Node s, t;
marci@174
    71
  Graph::EdgeMap<int> cap(G);
marci@73
    72
  readDimacsMaxFlow(std::cin, G, s, t, cap);
marci@155
    73
marci@174
    74
//   typedef TrivGraphWrapper<Graph> TGW;
marci@174
    75
//   TGW gw(G);
marci@174
    76
//   TGW::NodeIt sw;
marci@174
    77
//   gw./*getF*/first(sw);
marci@174
    78
//   std::cout << "p1:" << gw.nodeNum() << std::endl;
marci@174
    79
//   gw.erase(sw);
marci@174
    80
//   std::cout << "p2:" << gw.nodeNum() << std::endl;
marci@174
    81
marci@174
    82
//   typedef const Graph cLG;
marci@174
    83
//   typedef TrivGraphWrapper<const cLG> CTGW;
marci@174
    84
//   CTGW cgw(G);
marci@174
    85
//   CTGW::NodeIt csw;
marci@174
    86
//   cgw./*getF*/first(csw);
marci@174
    87
//   std::cout << "p1:" << cgw.nodeNum() << std::endl;
marci@174
    88
//   //cgw.erase(csw);
marci@174
    89
//   std::cout << "p2:" << cgw.nodeNum() << std::endl;
marci@174
    90
marci@73
    91
marci@133
    92
  {
marci@266
    93
    typedef TrivGraphWrapper<const Graph> GW;
marci@266
    94
    GW gw(G);
marci@174
    95
    std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
marci@271
    96
    GW::EdgeMap<int> flow(gw); //0 flow
marci@73
    97
marci@174
    98
    Timer ts;
marci@174
    99
    ts.reset();
marci@174
   100
marci@266
   101
    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
marci@266
   102
    EMW cw(cap);
marci@267
   103
    MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
marci@174
   104
    int i=0;
marci@174
   105
    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 
marci@174
   106
//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
marci@168
   107
//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
marci@168
   108
//     }
marci@168
   109
//     std::cout<<std::endl;
marci@174
   110
      ++i; 
marci@174
   111
    }
marci@168
   112
marci@174
   113
//   std::cout << "maximum flow: "<< std::endl;
marci@174
   114
//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
marci@174
   115
//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
marci@174
   116
//   }
marci@174
   117
//   std::cout<<std::endl;
marci@174
   118
    std::cout << "elapsed time: " << ts << std::endl;
marci@174
   119
    std::cout << "number of augmentation phases: " << i << std::endl; 
marci@174
   120
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@168
   121
  }
marci@168
   122
marci@268
   123
  {
marci@268
   124
    typedef TrivGraphWrapper<const Graph> GW;
marci@268
   125
    GW gw(G);
marci@268
   126
    std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
marci@271
   127
    GW::EdgeMap<int> flow(gw); //0 flow
marci@266
   128
marci@268
   129
    Timer ts;
marci@268
   130
    ts.reset();
marci@266
   131
marci@268
   132
    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
marci@268
   133
    EMW cw(cap);
marci@268
   134
    MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
marci@268
   135
    int i=0;
marci@268
   136
    while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 
marci@268
   137
//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
marci@268
   138
//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
marci@266
   139
//     }
marci@268
   140
//     std::cout<<std::endl;
marci@268
   141
      ++i; 
marci@268
   142
    }
marci@266
   143
marci@268
   144
//   std::cout << "maximum flow: "<< std::endl;
marci@268
   145
//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
marci@268
   146
//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
marci@266
   147
//   }
marci@268
   148
//   std::cout<<std::endl;
marci@268
   149
    std::cout << "elapsed time: " << ts << std::endl;
marci@268
   150
    std::cout << "number of augmentation phases: " << i << std::endl; 
marci@268
   151
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@268
   152
  }
marci@266
   153
marci@269
   154
  {
marci@269
   155
    typedef TrivGraphWrapper<const Graph> GW;
marci@269
   156
    GW gw(G);
marci@269
   157
    std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
marci@271
   158
    GW::EdgeMap<int> flow(gw); //0 flow
marci@266
   159
marci@269
   160
    Timer ts;
marci@269
   161
    ts.reset();
marci@266
   162
marci@269
   163
    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
marci@269
   164
    EMW cw(cap);
marci@269
   165
    MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
marci@269
   166
    int i=0;
marci@269
   167
    while (max_flow_test.augmentOnBlockingFlow2()) { 
marci@269
   168
//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
marci@269
   169
//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
marci@266
   170
//     }
marci@269
   171
//     std::cout<<std::endl;
marci@269
   172
      ++i; 
marci@269
   173
    }
marci@266
   174
marci@269
   175
//   std::cout << "maximum flow: "<< std::endl;
marci@269
   176
//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
marci@269
   177
//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
marci@266
   178
//   }
marci@269
   179
//   std::cout<<std::endl;
marci@269
   180
    std::cout << "elapsed time: " << ts << std::endl;
marci@269
   181
    std::cout << "number of augmentation phases: " << i << std::endl; 
marci@269
   182
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@269
   183
  }
marci@266
   184
marci@168
   185
  {
marci@266
   186
    typedef TrivGraphWrapper<const Graph> GW;
marci@266
   187
    GW gw(G);
marci@266
   188
    std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
marci@266
   189
    GW::EdgeMap<int> flow(gw); //0 flow
marci@206
   190
marci@206
   191
    Timer ts;
marci@206
   192
    ts.reset();
marci@206
   193
marci@266
   194
    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
marci@266
   195
    EMW cw(cap);
marci@266
   196
    MaxFlow<GW, int, GW::EdgeMap<int>, EMW> max_flow_test(gw, s, t, flow, cw);
marci@174
   197
    int i=0;
marci@174
   198
    while (max_flow_test.augmentOnShortestPath()) { 
marci@174
   199
//     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
marci@168
   200
//       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
marci@168
   201
//     }
marci@168
   202
//     std::cout<<std::endl;
marci@174
   203
      ++i; 
marci@174
   204
    }
marci@174
   205
marci@174
   206
//   std::cout << "maximum flow: "<< std::endl;
marci@174
   207
//   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
marci@174
   208
//     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
marci@174
   209
//   }
marci@174
   210
//   std::cout<<std::endl;
marci@174
   211
    std::cout << "elapsed time: " << ts << std::endl;
marci@174
   212
    std::cout << "number of augmentation phases: " << i << std::endl; 
marci@174
   213
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@168
   214
  }
marci@133
   215
marci@73
   216
marci@73
   217
  return 0;
marci@73
   218
}