1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/max_flow_demo.cc Thu Apr 29 16:08:16 2004 +0000
1.3 @@ -0,0 +1,154 @@
1.4 +// -*- c++ -*-
1.5 +#include <iostream>
1.6 +#include <fstream>
1.7 +
1.8 +#include <list_graph.h>
1.9 +#include <smart_graph.h>
1.10 +#include <dimacs.h>
1.11 +//#include <edmonds_karp.h>
1.12 +#include <time_measure.h>
1.13 +//#include <graph_wrapper.h>
1.14 +#include <preflow.h>
1.15 +//#include <preflow_res.h>
1.16 +#include <for_each_macros.h>
1.17 +
1.18 +using namespace hugo;
1.19 +
1.20 +// Use a DIMACS max flow file as stdin.
1.21 +// read_dimacs_demo < dimacs_max_flow_file
1.22 +
1.23 +
1.24 +// struct Ize {
1.25 +// };
1.26 +
1.27 +// struct Mize {
1.28 +// Ize bumm;
1.29 +// };
1.30 +
1.31 +// template <typename B>
1.32 +// class Huha {
1.33 +// public:
1.34 +// int u;
1.35 +// B brr;
1.36 +// };
1.37 +
1.38 +
1.39 +int main(int, char **) {
1.40 +
1.41 + typedef ListGraph MutableGraph;
1.42 +
1.43 + typedef SmartGraph Graph;
1.44 + // typedef ListGraph Graph;
1.45 + typedef Graph::Node Node;
1.46 + typedef Graph::EdgeIt EdgeIt;
1.47 +
1.48 +
1.49 +// Mize mize[10];
1.50 +// Mize bize[0];
1.51 +// Mize zize;
1.52 +// typedef Mize Tize[0];
1.53 +
1.54 +// std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
1.55 +// std::cout << sizeof(bize) << std::endl;
1.56 +
1.57 +
1.58 +// Huha<Tize> k;
1.59 +// std::cout << sizeof(k) << std::endl;
1.60 +
1.61 +
1.62 +// struct Bumm {
1.63 +// //int a;
1.64 +// bool b;
1.65 +// };
1.66 +
1.67 +// std::cout << sizeof(Bumm) << std::endl;
1.68 +
1.69 +
1.70 + Graph G;
1.71 + Node s, t;
1.72 + Graph::EdgeMap<int> cap(G);
1.73 + readDimacsMaxFlow(std::cin, G, s, t, cap);
1.74 + Timer ts;
1.75 + Graph::EdgeMap<int> flow(G); //0 flow
1.76 + Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.77 + pre_flow_test(G, s, t, cap, flow/*, true*/);
1.78 + // Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.79 + // pre_flow_ize(G, s, t, cap, flow/*, false*/);
1.80 +// PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.81 +// pre_flow_res(G, s, t, cap, flow/*, true*/);
1.82 + //MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.83 + // max_flow_test(G, s, t, cap, flow);
1.84 +
1.85 + {
1.86 + std::cout << "preflow ..." << std::endl;
1.87 + ts.reset();
1.88 + pre_flow_test.run();
1.89 + std::cout << "elapsed time: " << ts << std::endl;
1.90 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
1.91 + }
1.92 +
1.93 + {
1.94 + std::cout << "preflow ..." << std::endl;
1.95 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.96 + ts.reset();
1.97 + pre_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
1.98 + std::cout << "elapsed time: " << ts << std::endl;
1.99 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
1.100 + }
1.101 +
1.102 +// {
1.103 +// std::cout << "wrapped preflow ..." << std::endl;
1.104 +// FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.105 +// ts.reset();
1.106 +// pre_flow_res.run();
1.107 +// std::cout << "elapsed time: " << ts << std::endl;
1.108 +// std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
1.109 +// }
1.110 +
1.111 + {
1.112 + std::cout << "physical blocking flow augmentation ..." << std::endl;
1.113 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.114 + ts.reset();
1.115 + int i=0;
1.116 + while (pre_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.117 + std::cout << "elapsed time: " << ts << std::endl;
1.118 + std::cout << "number of augmentation phases: " << i << std::endl;
1.119 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
1.120 + }
1.121 +
1.122 +// {
1.123 +// std::cout << "faster physical blocking flow augmentation ..." << std::endl;
1.124 +// FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.125 +// ts.reset();
1.126 +// int i=0;
1.127 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
1.128 +// std::cout << "elapsed time: " << ts << std::endl;
1.129 +// std::cout << "number of augmentation phases: " << i << std::endl;
1.130 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.131 +// }
1.132 +
1.133 + {
1.134 + std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
1.135 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.136 + ts.reset();
1.137 + int i=0;
1.138 + while (pre_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.139 + std::cout << "elapsed time: " << ts << std::endl;
1.140 + std::cout << "number of augmentation phases: " << i << std::endl;
1.141 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
1.142 + }
1.143 +
1.144 + {
1.145 + std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
1.146 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.147 + ts.reset();
1.148 + int i=0;
1.149 + while (pre_flow_test.augmentOnShortestPath()) { ++i; }
1.150 + std::cout << "elapsed time: " << ts << std::endl;
1.151 + std::cout << "number of augmentation phases: " << i << std::endl;
1.152 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
1.153 + }
1.154 +
1.155 +
1.156 + return 0;
1.157 +}