src/work/marci/lg_vs_sg.cc
author marci
Fri, 14 May 2004 18:28:57 +0000
changeset 642 e812963087f0
parent 640 d426dca0aaf7
permissions -rw-r--r--
To avoid confusion my old ListGraph is can be used under name SageGraph, work/sage_graph.h contains it.
marci@174
     1
// -*- c++ -*-
marci@174
     2
#include <iostream>
marci@174
     3
#include <fstream>
marci@174
     4
#include <string>
marci@174
     5
marci@642
     6
#include <sage_graph.h>
marci@642
     7
#include <hugo/list_graph.h>
marci@555
     8
#include <hugo/smart_graph.h>
marci@555
     9
#include <hugo/dimacs.h>
marci@480
    10
#include <max_flow.h>
marci@555
    11
#include <hugo/time_measure.h>
marci@640
    12
#include <hugo/for_each_macros.h>
marci@174
    13
marci@174
    14
using namespace hugo;
marci@174
    15
marci@174
    16
// Use a DIMACS max flow file as stdin.
marci@174
    17
// read_dimacs_demo dimacs_max_flow_file
marci@174
    18
marci@174
    19
int main(int, char** argv) {
marci@174
    20
marci@174
    21
  std::string in=argv[1];
marci@642
    22
  typedef SageGraph MutableGraph;
marci@174
    23
marci@174
    24
  {
marci@642
    25
    typedef SageGraph Graph;
marci@174
    26
    typedef Graph::Node Node;
marci@174
    27
    typedef Graph::EdgeIt EdgeIt;
marci@174
    28
marci@577
    29
    Graph g;
marci@174
    30
    Node s, t;
marci@577
    31
    Graph::EdgeMap<int> cap(g);
marci@174
    32
    std::ifstream ins(in.c_str());
marci@577
    33
    //readDimacsMaxFlow(ins, g, s, t, cap);
marci@577
    34
    readDimacs(ins, g, cap, s, t);
marci@174
    35
marci@334
    36
    Timer ts;
marci@577
    37
    Graph::EdgeMap<int> flow(g); //0 flow
marci@334
    38
    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
marci@577
    39
      max_flow_test(g, s, t, cap, flow/*, true*/);
marci@334
    40
marci@642
    41
    std::cout << "SageGraph ..." << std::endl;
marci@334
    42
marci@174
    43
    {
marci@334
    44
      std::cout << "preflow ..." << std::endl;
marci@334
    45
      ts.reset();
marci@476
    46
      max_flow_test.run();
marci@334
    47
      std::cout << "elapsed time: " << ts << std::endl;
marci@476
    48
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@334
    49
    }
marci@174
    50
marci@334
    51
    {
marci@334
    52
      std::cout << "physical blocking flow augmentation ..." << std::endl;
marci@577
    53
      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@174
    54
      ts.reset();
marci@174
    55
      int i=0;
marci@174
    56
      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
marci@174
    57
      std::cout << "elapsed time: " << ts << std::endl;
marci@174
    58
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@174
    59
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@174
    60
    }
marci@174
    61
marci@476
    62
//     {
marci@476
    63
//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
marci@577
    64
//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@476
    65
//       ts.reset();
marci@476
    66
//       int i=0;
marci@476
    67
//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
marci@476
    68
//       std::cout << "elapsed time: " << ts << std::endl;
marci@476
    69
//       std::cout << "number of augmentation phases: " << i << std::endl; 
marci@476
    70
//       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@476
    71
//     }
marci@174
    72
marci@174
    73
    {
marci@334
    74
      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
marci@577
    75
      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@334
    76
      ts.reset();
marci@334
    77
      int i=0;
marci@334
    78
      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
marci@334
    79
      std::cout << "elapsed time: " << ts << std::endl;
marci@334
    80
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@334
    81
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@334
    82
    }
marci@174
    83
marci@334
    84
    {
marci@334
    85
      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
marci@577
    86
      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@174
    87
      ts.reset();
marci@174
    88
      int i=0;
marci@174
    89
      while (max_flow_test.augmentOnShortestPath()) { ++i; }
marci@174
    90
      std::cout << "elapsed time: " << ts << std::endl;
marci@174
    91
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@174
    92
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@174
    93
    }
marci@174
    94
  }
marci@174
    95
marci@174
    96
  {
marci@174
    97
    typedef SmartGraph Graph;
marci@174
    98
    typedef Graph::Node Node;
marci@174
    99
    typedef Graph::EdgeIt EdgeIt;
marci@174
   100
marci@577
   101
    Graph g;
marci@174
   102
    Node s, t;
marci@577
   103
    Graph::EdgeMap<int> cap(g);
marci@174
   104
    std::ifstream ins(in.c_str());
marci@577
   105
    //readDimacsMaxFlow(ins, g, s, t, cap);
marci@577
   106
    readDimacs(ins, g, cap, s, t);
marci@174
   107
marci@334
   108
    Timer ts;
marci@577
   109
    Graph::EdgeMap<int> flow(g); //0 flow
marci@334
   110
    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
marci@577
   111
      max_flow_test(g, s, t, cap, flow/*, true*/);
marci@476
   112
    //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
marci@577
   113
    //  max_flow_test(g, s, t, cap, flow);
marci@334
   114
marci@642
   115
    std::cout << "SmartGraph ..." << std::endl;
marci@334
   116
marci@174
   117
    {
marci@334
   118
      std::cout << "preflow ..." << std::endl;
marci@577
   119
      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@334
   120
      ts.reset();
marci@476
   121
      max_flow_test.run();
marci@334
   122
      std::cout << "elapsed time: " << ts << std::endl;
marci@476
   123
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@334
   124
    }
marci@174
   125
marci@334
   126
    {
marci@334
   127
      std::cout << "physical blocking flow augmentation ..." << std::endl;
marci@577
   128
      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@174
   129
      ts.reset();
marci@174
   130
      int i=0;
marci@174
   131
      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
marci@174
   132
      std::cout << "elapsed time: " << ts << std::endl;
marci@174
   133
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@174
   134
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@174
   135
    }
marci@174
   136
marci@476
   137
//     {
marci@476
   138
//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
marci@577
   139
//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@476
   140
//       ts.reset();
marci@476
   141
//       int i=0;
marci@476
   142
//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
marci@476
   143
//       std::cout << "elapsed time: " << ts << std::endl;
marci@476
   144
//       std::cout << "number of augmentation phases: " << i << std::endl; 
marci@476
   145
//       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@476
   146
//     }
marci@174
   147
marci@174
   148
    {
marci@334
   149
      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
marci@577
   150
      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@334
   151
      ts.reset();
marci@334
   152
      int i=0;
marci@334
   153
      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
marci@334
   154
      std::cout << "elapsed time: " << ts << std::endl;
marci@334
   155
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@334
   156
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@334
   157
    }
marci@174
   158
marci@334
   159
    {
marci@334
   160
      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
marci@577
   161
      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@174
   162
      ts.reset();
marci@174
   163
      int i=0;
marci@174
   164
      while (max_flow_test.augmentOnShortestPath()) { ++i; }
marci@174
   165
      std::cout << "elapsed time: " << ts << std::endl;
marci@174
   166
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@174
   167
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@174
   168
    }
marci@174
   169
  }
marci@174
   170
marci@642
   171
  {
marci@642
   172
    typedef ListGraph Graph;
marci@642
   173
    typedef Graph::Node Node;
marci@642
   174
    typedef Graph::EdgeIt EdgeIt;
marci@642
   175
marci@642
   176
    Graph g;
marci@642
   177
    Node s, t;
marci@642
   178
    Graph::EdgeMap<int> cap(g);
marci@642
   179
    std::ifstream ins(in.c_str());
marci@642
   180
    //readDimacsMaxFlow(ins, g, s, t, cap);
marci@642
   181
    readDimacs(ins, g, cap, s, t);
marci@642
   182
marci@642
   183
    Timer ts;
marci@642
   184
    Graph::EdgeMap<int> flow(g); //0 flow
marci@642
   185
    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
marci@642
   186
      max_flow_test(g, s, t, cap, flow/*, true*/);
marci@642
   187
    //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
marci@642
   188
    //  max_flow_test(g, s, t, cap, flow);
marci@642
   189
marci@642
   190
    std::cout << "ListGraph ..." << std::endl;
marci@642
   191
marci@642
   192
    {
marci@642
   193
      std::cout << "preflow ..." << std::endl;
marci@642
   194
      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@642
   195
      ts.reset();
marci@642
   196
      max_flow_test.run();
marci@642
   197
      std::cout << "elapsed time: " << ts << std::endl;
marci@642
   198
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@642
   199
    }
marci@642
   200
marci@642
   201
    {
marci@642
   202
      std::cout << "physical blocking flow augmentation ..." << std::endl;
marci@642
   203
      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@642
   204
      ts.reset();
marci@642
   205
      int i=0;
marci@642
   206
      while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
marci@642
   207
      std::cout << "elapsed time: " << ts << std::endl;
marci@642
   208
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@642
   209
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@642
   210
    }
marci@642
   211
marci@642
   212
//     {
marci@642
   213
//       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
marci@642
   214
//       FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@642
   215
//       ts.reset();
marci@642
   216
//       int i=0;
marci@642
   217
//       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
marci@642
   218
//       std::cout << "elapsed time: " << ts << std::endl;
marci@642
   219
//       std::cout << "number of augmentation phases: " << i << std::endl; 
marci@642
   220
//       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@642
   221
//     }
marci@642
   222
marci@642
   223
    {
marci@642
   224
      std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
marci@642
   225
      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@642
   226
      ts.reset();
marci@642
   227
      int i=0;
marci@642
   228
      while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
marci@642
   229
      std::cout << "elapsed time: " << ts << std::endl;
marci@642
   230
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@642
   231
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@642
   232
    }
marci@642
   233
marci@642
   234
    {
marci@642
   235
      std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
marci@642
   236
      FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@642
   237
      ts.reset();
marci@642
   238
      int i=0;
marci@642
   239
      while (max_flow_test.augmentOnShortestPath()) { ++i; }
marci@642
   240
      std::cout << "elapsed time: " << ts << std::endl;
marci@642
   241
      std::cout << "number of augmentation phases: " << i << std::endl; 
marci@642
   242
      std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@642
   243
    }
marci@642
   244
  }
marci@642
   245
marci@334
   246
marci@334
   247
marci@334
   248
marci@174
   249
  return 0;
marci@174
   250
}