src/work/marci/gw_vs_not.cc
author marci
Fri, 07 May 2004 06:33:02 +0000
changeset 565 18787f6db0db
child 921 818510fa3d99
permissions -rw-r--r--
ResGraphWrapper mods.
marci@270
     1
// -*- c++ -*-
marci@270
     2
#include <iostream>
marci@270
     3
#include <fstream>
marci@270
     4
marci@270
     5
#include <list_graph.h>
marci@270
     6
#include <smart_graph.h>
marci@270
     7
#include <dimacs.h>
marci@270
     8
#include <edmonds_karp.h>
marci@270
     9
#include <time_measure.h>
marci@270
    10
#include <graph_wrapper.h>
marci@270
    11
marci@270
    12
using namespace hugo;
marci@270
    13
marci@270
    14
// Use a DIMACS max flow file as stdin.
marci@270
    15
// read_dimacs_demo < dimacs_max_flow_file
marci@270
    16
marci@270
    17
int main(int, char **) {
marci@270
    18
marci@270
    19
  typedef ListGraph MutableGraph;
marci@270
    20
  //typedef SmartGraph Graph;
marci@270
    21
  typedef ListGraph Graph;
marci@270
    22
  typedef Graph::Node Node;
marci@270
    23
  typedef Graph::EdgeIt EdgeIt;
marci@270
    24
marci@270
    25
  Graph G;
marci@270
    26
  Node s, t;
marci@270
    27
  Graph::EdgeMap<int> cap(G);
marci@270
    28
  readDimacsMaxFlow(std::cin, G, s, t, cap);
marci@270
    29
marci@270
    30
  {
marci@270
    31
    typedef TrivGraphWrapper<const Graph> GW;
marci@270
    32
    GW gw(G);
marci@270
    33
    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
marci@270
    34
    EMW cw(cap);
marci@270
    35
    Timer ts;
marci@270
    36
    GW::EdgeMap<int> flow(gw); 
marci@270
    37
    MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
marci@270
    38
    int i;
marci@270
    39
marci@270
    40
    {
marci@270
    41
      std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
marci@270
    42
      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
marci@270
    43
      ts.reset();
marci@270
    44
marci@270
    45
      i=0;
marci@270
    46
      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
marci@270
    47
marci@270
    48
      std::cout << "elapsed time: " << ts << std::endl;
marci@270
    49
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@270
    50
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@270
    51
    }
marci@270
    52
marci@270
    53
    {
marci@270
    54
      std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
marci@270
    55
      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
marci@270
    56
      ts.reset();
marci@270
    57
marci@270
    58
      i=0;
marci@270
    59
      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
marci@270
    60
marci@270
    61
      std::cout << "elapsed time: " << ts << std::endl;
marci@270
    62
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@270
    63
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@270
    64
    }
marci@270
    65
marci@270
    66
    {
marci@270
    67
      std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
marci@270
    68
      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
marci@270
    69
      ts.reset();
marci@270
    70
marci@270
    71
      i=0;
marci@270
    72
      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
marci@270
    73
marci@270
    74
      std::cout << "elapsed time: " << ts << std::endl;
marci@270
    75
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@270
    76
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@270
    77
    }
marci@270
    78
marci@270
    79
    {
marci@270
    80
      std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
marci@270
    81
      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
marci@270
    82
      ts.reset();
marci@270
    83
marci@270
    84
      i=0;
marci@270
    85
      while (max_flow_test.augmentOnShortestPath()) { ++i; }
marci@270
    86
marci@270
    87
      std::cout << "elapsed time: " << ts << std::endl;
marci@270
    88
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@270
    89
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@270
    90
    }
marci@270
    91
  }
marci@270
    92
marci@270
    93
marci@270
    94
marci@270
    95
marci@270
    96
  {
marci@270
    97
    typedef TrivGraphWrapper<const Graph> GW1;
marci@270
    98
    GW1 gw1(G);
marci@270
    99
    typedef TrivGraphWrapper<const GW1> GW2;
marci@270
   100
    GW2 gw2(gw1);
marci@270
   101
    typedef TrivGraphWrapper<const GW2> GW3;
marci@270
   102
    GW3 gw3(gw2);
marci@270
   103
    typedef TrivGraphWrapper<const GW3> GW4;
marci@270
   104
    GW4 gw4(gw3);
marci@270
   105
    typedef TrivGraphWrapper<const GW4> GW5;
marci@270
   106
    GW5 gw5(gw4);
marci@270
   107
    typedef TrivGraphWrapper<const GW5> GW6;
marci@270
   108
    GW6 gw6(gw5);
marci@270
   109
    typedef TrivGraphWrapper<const GW6> GW7;
marci@270
   110
    GW7 gw7(gw6);
marci@270
   111
    typedef TrivGraphWrapper<const GW7> GW8;
marci@270
   112
    GW8 gw8(gw7);
marci@270
   113
    typedef TrivGraphWrapper<const GW8> GW9;
marci@270
   114
    GW9 gw9(gw8);
marci@270
   115
    typedef TrivGraphWrapper<const GW9> GW;
marci@270
   116
    GW gw(gw9);
marci@270
   117
    typedef GW::EdgeMapWrapper< Graph::EdgeMap<int>, int > EMW;
marci@270
   118
    EMW cw(cap);
marci@270
   119
    Timer ts;
marci@270
   120
    GW::EdgeMap<int> flow(gw); 
marci@270
   121
    MaxFlow<GW, int, GW::EdgeMap<int>, EMW > max_flow_test(gw, s, t, flow, cw);
marci@270
   122
    int i;
marci@270
   123
marci@270
   124
    {
marci@270
   125
      std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
marci@270
   126
      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
marci@270
   127
      ts.reset();
marci@270
   128
marci@270
   129
      i=0;
marci@270
   130
      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
marci@270
   131
marci@270
   132
      std::cout << "elapsed time: " << ts << std::endl;
marci@270
   133
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@270
   134
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@270
   135
    }
marci@270
   136
marci@270
   137
    {
marci@270
   138
      std::cout << "edmonds karp demo (physical blocking flow 1 augmentation)..." << std::endl;
marci@270
   139
      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
marci@270
   140
      ts.reset();
marci@270
   141
marci@270
   142
      i=0;
marci@270
   143
      while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
marci@270
   144
marci@270
   145
      std::cout << "elapsed time: " << ts << std::endl;
marci@270
   146
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@270
   147
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@270
   148
    }
marci@270
   149
marci@270
   150
    {
marci@270
   151
      std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
marci@270
   152
      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
marci@270
   153
      ts.reset();
marci@270
   154
marci@270
   155
      i=0;
marci@270
   156
      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
marci@270
   157
marci@270
   158
      std::cout << "elapsed time: " << ts << std::endl;
marci@270
   159
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@270
   160
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@270
   161
    }
marci@270
   162
marci@270
   163
    {
marci@270
   164
      std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
marci@270
   165
      for (GW::EdgeIt e(gw); gw.valid(e); gw.next(e)) flow.set(e, 0);
marci@270
   166
      ts.reset();
marci@270
   167
marci@270
   168
      i=0;
marci@270
   169
      while (max_flow_test.augmentOnShortestPath()) { ++i; }
marci@270
   170
marci@270
   171
      std::cout << "elapsed time: " << ts << std::endl;
marci@270
   172
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@270
   173
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@270
   174
    }
marci@270
   175
  }
marci@270
   176
marci@270
   177
marci@270
   178
  return 0;
marci@270
   179
}