1.1 --- a/src/work/marci/edmonds_karp_demo.cc Thu Apr 29 16:07:10 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,154 +0,0 @@
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 -}
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/marci/max_flow_demo.cc Thu Apr 29 16:08:16 2004 +0000
2.3 @@ -0,0 +1,154 @@
2.4 +// -*- c++ -*-
2.5 +#include <iostream>
2.6 +#include <fstream>
2.7 +
2.8 +#include <list_graph.h>
2.9 +#include <smart_graph.h>
2.10 +#include <dimacs.h>
2.11 +//#include <edmonds_karp.h>
2.12 +#include <time_measure.h>
2.13 +//#include <graph_wrapper.h>
2.14 +#include <preflow.h>
2.15 +//#include <preflow_res.h>
2.16 +#include <for_each_macros.h>
2.17 +
2.18 +using namespace hugo;
2.19 +
2.20 +// Use a DIMACS max flow file as stdin.
2.21 +// read_dimacs_demo < dimacs_max_flow_file
2.22 +
2.23 +
2.24 +// struct Ize {
2.25 +// };
2.26 +
2.27 +// struct Mize {
2.28 +// Ize bumm;
2.29 +// };
2.30 +
2.31 +// template <typename B>
2.32 +// class Huha {
2.33 +// public:
2.34 +// int u;
2.35 +// B brr;
2.36 +// };
2.37 +
2.38 +
2.39 +int main(int, char **) {
2.40 +
2.41 + typedef ListGraph MutableGraph;
2.42 +
2.43 + typedef SmartGraph Graph;
2.44 + // typedef ListGraph Graph;
2.45 + typedef Graph::Node Node;
2.46 + typedef Graph::EdgeIt EdgeIt;
2.47 +
2.48 +
2.49 +// Mize mize[10];
2.50 +// Mize bize[0];
2.51 +// Mize zize;
2.52 +// typedef Mize Tize[0];
2.53 +
2.54 +// std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
2.55 +// std::cout << sizeof(bize) << std::endl;
2.56 +
2.57 +
2.58 +// Huha<Tize> k;
2.59 +// std::cout << sizeof(k) << std::endl;
2.60 +
2.61 +
2.62 +// struct Bumm {
2.63 +// //int a;
2.64 +// bool b;
2.65 +// };
2.66 +
2.67 +// std::cout << sizeof(Bumm) << std::endl;
2.68 +
2.69 +
2.70 + Graph G;
2.71 + Node s, t;
2.72 + Graph::EdgeMap<int> cap(G);
2.73 + readDimacsMaxFlow(std::cin, G, s, t, cap);
2.74 + Timer ts;
2.75 + Graph::EdgeMap<int> flow(G); //0 flow
2.76 + Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
2.77 + pre_flow_test(G, s, t, cap, flow/*, true*/);
2.78 + // Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
2.79 + // pre_flow_ize(G, s, t, cap, flow/*, false*/);
2.80 +// PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
2.81 +// pre_flow_res(G, s, t, cap, flow/*, true*/);
2.82 + //MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
2.83 + // max_flow_test(G, s, t, cap, flow);
2.84 +
2.85 + {
2.86 + std::cout << "preflow ..." << std::endl;
2.87 + ts.reset();
2.88 + pre_flow_test.run();
2.89 + std::cout << "elapsed time: " << ts << std::endl;
2.90 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
2.91 + }
2.92 +
2.93 + {
2.94 + std::cout << "preflow ..." << std::endl;
2.95 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
2.96 + ts.reset();
2.97 + pre_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
2.98 + std::cout << "elapsed time: " << ts << std::endl;
2.99 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
2.100 + }
2.101 +
2.102 +// {
2.103 +// std::cout << "wrapped preflow ..." << std::endl;
2.104 +// FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
2.105 +// ts.reset();
2.106 +// pre_flow_res.run();
2.107 +// std::cout << "elapsed time: " << ts << std::endl;
2.108 +// std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
2.109 +// }
2.110 +
2.111 + {
2.112 + std::cout << "physical blocking flow augmentation ..." << std::endl;
2.113 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
2.114 + ts.reset();
2.115 + int i=0;
2.116 + while (pre_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
2.117 + std::cout << "elapsed time: " << ts << std::endl;
2.118 + std::cout << "number of augmentation phases: " << i << std::endl;
2.119 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
2.120 + }
2.121 +
2.122 +// {
2.123 +// std::cout << "faster physical blocking flow augmentation ..." << std::endl;
2.124 +// FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
2.125 +// ts.reset();
2.126 +// int i=0;
2.127 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
2.128 +// std::cout << "elapsed time: " << ts << std::endl;
2.129 +// std::cout << "number of augmentation phases: " << i << std::endl;
2.130 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
2.131 +// }
2.132 +
2.133 + {
2.134 + std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
2.135 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
2.136 + ts.reset();
2.137 + int i=0;
2.138 + while (pre_flow_test.augmentOnBlockingFlow2()) { ++i; }
2.139 + std::cout << "elapsed time: " << ts << std::endl;
2.140 + std::cout << "number of augmentation phases: " << i << std::endl;
2.141 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
2.142 + }
2.143 +
2.144 + {
2.145 + std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
2.146 + FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
2.147 + ts.reset();
2.148 + int i=0;
2.149 + while (pre_flow_test.augmentOnShortestPath()) { ++i; }
2.150 + std::cout << "elapsed time: " << ts << std::endl;
2.151 + std::cout << "number of augmentation phases: " << i << std::endl;
2.152 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
2.153 + }
2.154 +
2.155 +
2.156 + return 0;
2.157 +}