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 -}