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