src/work/marci/max_flow_demo.cc
author marci
Wed, 12 May 2004 14:07:00 +0000
changeset 626 0015642b0990
parent 555 995bc1f1a3ce
child 640 d426dca0aaf7
permissions -rw-r--r--
:wq
marci@475
     1
// -*- c++ -*-
marci@475
     2
#include <iostream>
marci@475
     3
#include <fstream>
marci@475
     4
marci@475
     5
#include <list_graph.h>
marci@555
     6
#include <hugo/smart_graph.h>
marci@555
     7
#include <hugo/dimacs.h>
marci@555
     8
#include <hugo/time_measure.h>
marci@475
     9
//#include <graph_wrapper.h>
marci@480
    10
#include <max_flow.h>
marci@475
    11
//#include <preflow_res.h>
marci@475
    12
#include <for_each_macros.h>
marci@475
    13
marci@475
    14
using namespace hugo;
marci@475
    15
marci@475
    16
// Use a DIMACS max flow file as stdin.
marci@475
    17
// read_dimacs_demo < dimacs_max_flow_file
marci@475
    18
marci@475
    19
marci@475
    20
//   struct Ize {
marci@475
    21
//   };
marci@475
    22
  
marci@475
    23
//   struct Mize {
marci@475
    24
//     Ize bumm;
marci@475
    25
//   };
marci@475
    26
marci@475
    27
//   template <typename B>
marci@475
    28
//     class Huha {
marci@475
    29
//     public:
marci@475
    30
//       int u;
marci@475
    31
//       B brr;
marci@475
    32
//     };
marci@475
    33
marci@475
    34
marci@475
    35
int main(int, char **) {
marci@475
    36
marci@475
    37
  typedef ListGraph MutableGraph;
marci@475
    38
marci@475
    39
  typedef SmartGraph Graph;
marci@475
    40
  //  typedef ListGraph Graph;
marci@475
    41
  typedef Graph::Node Node;
marci@475
    42
  typedef Graph::EdgeIt EdgeIt;
marci@475
    43
marci@475
    44
marci@475
    45
//   Mize mize[10];
marci@475
    46
//   Mize bize[0];
marci@475
    47
//   Mize zize;
marci@475
    48
//   typedef Mize Tize[0];
marci@475
    49
marci@475
    50
//   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
marci@475
    51
//   std::cout << sizeof(bize) << std::endl;
marci@475
    52
marci@475
    53
marci@475
    54
//   Huha<Tize> k;
marci@475
    55
//   std::cout << sizeof(k) << std::endl;
marci@475
    56
marci@475
    57
marci@475
    58
//   struct Bumm {
marci@475
    59
//     //int a;
marci@475
    60
//     bool b;
marci@475
    61
//   };
marci@475
    62
marci@475
    63
//   std::cout << sizeof(Bumm) << std::endl;
marci@475
    64
marci@475
    65
marci@577
    66
  Graph g;
marci@475
    67
  Node s, t;
marci@577
    68
  Graph::EdgeMap<int> cap(g);
marci@577
    69
  //readDimacsMaxFlow(std::cin, g, s, t, cap);
marci@577
    70
  readDimacs(std::cin, g, cap, s, t);
marci@475
    71
  Timer ts;
marci@577
    72
  Graph::EdgeMap<int> flow(g); //0 flow
marci@476
    73
  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
marci@577
    74
    max_flow_test(g, s, t, cap, flow);
marci@475
    75
marci@475
    76
  {
marci@475
    77
    std::cout << "preflow ..." << std::endl;
marci@475
    78
    ts.reset();
marci@476
    79
    max_flow_test.run();
marci@475
    80
    std::cout << "elapsed time: " << ts << std::endl;
marci@476
    81
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@475
    82
  }
marci@475
    83
marci@475
    84
  {
marci@475
    85
    std::cout << "preflow ..." << std::endl;
marci@577
    86
    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@475
    87
    ts.reset();
marci@476
    88
    max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
marci@475
    89
    std::cout << "elapsed time: " << ts << std::endl;
marci@476
    90
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@475
    91
  }
marci@475
    92
marci@475
    93
//   {
marci@475
    94
//     std::cout << "wrapped preflow ..." << std::endl;
marci@577
    95
//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@475
    96
//     ts.reset();
marci@475
    97
//     pre_flow_res.run();
marci@475
    98
//     std::cout << "elapsed time: " << ts << std::endl;
marci@475
    99
//     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
marci@475
   100
//   }
marci@475
   101
marci@475
   102
  {
marci@475
   103
    std::cout << "physical blocking flow augmentation ..." << std::endl;
marci@577
   104
    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@475
   105
    ts.reset();
marci@475
   106
    int i=0;
marci@476
   107
    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
marci@475
   108
    std::cout << "elapsed time: " << ts << std::endl;
marci@475
   109
    std::cout << "number of augmentation phases: " << i << std::endl; 
marci@476
   110
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@475
   111
  }
marci@475
   112
marci@475
   113
//   {
marci@475
   114
//     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
marci@577
   115
//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@475
   116
//     ts.reset();
marci@475
   117
//     int i=0;
marci@475
   118
//     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
marci@475
   119
//     std::cout << "elapsed time: " << ts << std::endl;
marci@475
   120
//     std::cout << "number of augmentation phases: " << i << std::endl; 
marci@475
   121
//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@475
   122
//   }
marci@475
   123
marci@475
   124
  {
marci@475
   125
    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
marci@577
   126
    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@475
   127
    ts.reset();
marci@475
   128
    int i=0;
marci@476
   129
    while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
marci@475
   130
    std::cout << "elapsed time: " << ts << std::endl;
marci@475
   131
    std::cout << "number of augmentation phases: " << i << std::endl; 
marci@476
   132
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@475
   133
  }
marci@475
   134
marci@475
   135
  {
marci@475
   136
    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
marci@577
   137
    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@475
   138
    ts.reset();
marci@475
   139
    int i=0;
marci@476
   140
    while (max_flow_test.augmentOnShortestPath()) { ++i; }
marci@475
   141
    std::cout << "elapsed time: " << ts << std::endl;
marci@475
   142
    std::cout << "number of augmentation phases: " << i << std::endl; 
marci@476
   143
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@475
   144
  }
marci@475
   145
marci@475
   146
marci@475
   147
  return 0;
marci@475
   148
}