src/work/marci/max_flow_demo.cc
author marci
Thu, 20 May 2004 17:21:55 +0000
changeset 652 4dfa1f79bf3e
parent 651 a56e043aeab1
child 762 511200bdb71f
permissions -rw-r--r--
misc
marci@475
     1
// -*- c++ -*-
marci@475
     2
#include <iostream>
marci@475
     3
#include <fstream>
marci@475
     4
marci@642
     5
#include <sage_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@640
    12
#include <hugo/for_each_macros.h>
marci@651
    13
#include <graph_concept.h>
marci@475
    14
marci@475
    15
using namespace hugo;
marci@475
    16
marci@475
    17
// Use a DIMACS max flow file as stdin.
marci@475
    18
// read_dimacs_demo < dimacs_max_flow_file
marci@475
    19
marci@475
    20
marci@475
    21
//   struct Ize {
marci@475
    22
//   };
marci@475
    23
  
marci@475
    24
//   struct Mize {
marci@475
    25
//     Ize bumm;
marci@475
    26
//   };
marci@475
    27
marci@475
    28
//   template <typename B>
marci@475
    29
//     class Huha {
marci@475
    30
//     public:
marci@475
    31
//       int u;
marci@475
    32
//       B brr;
marci@475
    33
//     };
marci@475
    34
marci@475
    35
marci@475
    36
int main(int, char **) {
marci@475
    37
marci@642
    38
  typedef SageGraph MutableGraph;
marci@475
    39
marci@651
    40
  //typedef FullFeatureGraphConcept Graph;
marci@475
    41
  typedef SmartGraph Graph;
marci@642
    42
  //  typedef SageGraph Graph;
marci@475
    43
  typedef Graph::Node Node;
marci@475
    44
  typedef Graph::EdgeIt EdgeIt;
marci@475
    45
marci@475
    46
marci@475
    47
//   Mize mize[10];
marci@475
    48
//   Mize bize[0];
marci@475
    49
//   Mize zize;
marci@475
    50
//   typedef Mize Tize[0];
marci@475
    51
marci@475
    52
//   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
marci@475
    53
//   std::cout << sizeof(bize) << std::endl;
marci@475
    54
marci@475
    55
marci@475
    56
//   Huha<Tize> k;
marci@475
    57
//   std::cout << sizeof(k) << std::endl;
marci@475
    58
marci@475
    59
marci@475
    60
//   struct Bumm {
marci@475
    61
//     //int a;
marci@475
    62
//     bool b;
marci@475
    63
//   };
marci@475
    64
marci@475
    65
//   std::cout << sizeof(Bumm) << std::endl;
marci@475
    66
marci@475
    67
marci@577
    68
  Graph g;
marci@652
    69
marci@475
    70
  Node s, t;
marci@577
    71
  Graph::EdgeMap<int> cap(g);
marci@577
    72
  //readDimacsMaxFlow(std::cin, g, s, t, cap);
marci@577
    73
  readDimacs(std::cin, g, cap, s, t);
marci@475
    74
  Timer ts;
marci@577
    75
  Graph::EdgeMap<int> flow(g); //0 flow
marci@476
    76
  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
marci@577
    77
    max_flow_test(g, s, t, cap, flow);
marci@646
    78
  Graph::NodeMap<bool> cut(g);
marci@475
    79
marci@475
    80
  {
marci@475
    81
    std::cout << "preflow ..." << std::endl;
marci@475
    82
    ts.reset();
marci@476
    83
    max_flow_test.run();
marci@475
    84
    std::cout << "elapsed time: " << ts << std::endl;
marci@476
    85
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@646
    86
    max_flow_test.actMinCut(cut);
marci@646
    87
marci@646
    88
    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
marci@646
    89
      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
marci@646
    90
	std::cout << "Slackness does not hold!" << std::endl;
marci@646
    91
      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
marci@646
    92
	std::cout << "Slackness does not hold!" << std::endl;
marci@646
    93
    }
marci@475
    94
  }
marci@475
    95
marci@475
    96
  {
marci@475
    97
    std::cout << "preflow ..." << std::endl;
marci@577
    98
    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@475
    99
    ts.reset();
marci@476
   100
    max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
marci@475
   101
    std::cout << "elapsed time: " << ts << std::endl;
marci@476
   102
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@646
   103
marci@646
   104
    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
marci@646
   105
      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
marci@646
   106
	std::cout << "Slackness does not hold!" << std::endl;
marci@646
   107
      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
marci@646
   108
	std::cout << "Slackness does not hold!" << std::endl;
marci@646
   109
    }
marci@475
   110
  }
marci@475
   111
marci@475
   112
//   {
marci@475
   113
//     std::cout << "wrapped preflow ..." << std::endl;
marci@577
   114
//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@475
   115
//     ts.reset();
marci@475
   116
//     pre_flow_res.run();
marci@475
   117
//     std::cout << "elapsed time: " << ts << std::endl;
marci@475
   118
//     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
marci@475
   119
//   }
marci@475
   120
marci@475
   121
  {
marci@475
   122
    std::cout << "physical blocking flow augmentation ..." << std::endl;
marci@577
   123
    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@475
   124
    ts.reset();
marci@475
   125
    int i=0;
marci@476
   126
    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
marci@475
   127
    std::cout << "elapsed time: " << ts << std::endl;
marci@475
   128
    std::cout << "number of augmentation phases: " << i << std::endl; 
marci@476
   129
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@646
   130
marci@646
   131
    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
marci@646
   132
      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
marci@646
   133
	std::cout << "Slackness does not hold!" << std::endl;
marci@646
   134
      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
marci@646
   135
	std::cout << "Slackness does not hold!" << std::endl;
marci@646
   136
    }
marci@475
   137
  }
marci@475
   138
marci@475
   139
//   {
marci@475
   140
//     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
marci@577
   141
//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@475
   142
//     ts.reset();
marci@475
   143
//     int i=0;
marci@475
   144
//     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
marci@475
   145
//     std::cout << "elapsed time: " << ts << std::endl;
marci@475
   146
//     std::cout << "number of augmentation phases: " << i << std::endl; 
marci@475
   147
//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@475
   148
//   }
marci@475
   149
marci@475
   150
  {
marci@475
   151
    std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
marci@577
   152
    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@475
   153
    ts.reset();
marci@475
   154
    int i=0;
marci@476
   155
    while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
marci@475
   156
    std::cout << "elapsed time: " << ts << std::endl;
marci@475
   157
    std::cout << "number of augmentation phases: " << i << std::endl; 
marci@476
   158
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@646
   159
marci@646
   160
    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
marci@646
   161
      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
marci@646
   162
	std::cout << "Slackness does not hold!" << std::endl;
marci@646
   163
      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
marci@646
   164
	std::cout << "Slackness does not hold!" << std::endl;
marci@646
   165
    }
marci@475
   166
  }
marci@475
   167
marci@475
   168
  {
marci@475
   169
    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
marci@577
   170
    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@475
   171
    ts.reset();
marci@475
   172
    int i=0;
marci@476
   173
    while (max_flow_test.augmentOnShortestPath()) { ++i; }
marci@475
   174
    std::cout << "elapsed time: " << ts << std::endl;
marci@475
   175
    std::cout << "number of augmentation phases: " << i << std::endl; 
marci@476
   176
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@646
   177
marci@646
   178
    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
marci@646
   179
      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
marci@646
   180
	std::cout << "Slackness does not hold!" << std::endl;
marci@646
   181
      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
marci@646
   182
	std::cout << "Slackness does not hold!" << std::endl;
marci@646
   183
    }
marci@475
   184
  }
marci@475
   185
marci@646
   186
  {
marci@646
   187
    std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
marci@646
   188
    FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
marci@646
   189
    ts.reset();
marci@646
   190
    int i=0;
marci@646
   191
    while (max_flow_test.augmentOnShortestPath2()) { ++i; }
marci@646
   192
    std::cout << "elapsed time: " << ts << std::endl;
marci@646
   193
    std::cout << "number of augmentation phases: " << i << std::endl; 
marci@646
   194
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@646
   195
marci@646
   196
    FOR_EACH_LOC(Graph::EdgeIt, e, g) {
marci@646
   197
      if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) 
marci@646
   198
	std::cout << "Slackness does not hold!" << std::endl;
marci@646
   199
      if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) 
marci@646
   200
	std::cout << "Slackness does not hold!" << std::endl;
marci@646
   201
    }
marci@646
   202
  }
marci@475
   203
marci@475
   204
  return 0;
marci@475
   205
}