1.1 --- a/src/work/marci/edmonds_karp_demo.cc Thu Apr 29 15:01:52 2004 +0000
1.2 +++ b/src/work/marci/edmonds_karp_demo.cc Thu Apr 29 15:58:34 2004 +0000
1.3 @@ -5,11 +5,11 @@
1.4 #include <list_graph.h>
1.5 #include <smart_graph.h>
1.6 #include <dimacs.h>
1.7 -#include <edmonds_karp.h>
1.8 +//#include <edmonds_karp.h>
1.9 #include <time_measure.h>
1.10 //#include <graph_wrapper.h>
1.11 #include <preflow.h>
1.12 -#include <preflow_res.h>
1.13 +//#include <preflow_res.h>
1.14 #include <for_each_macros.h>
1.15
1.16 using namespace hugo;
1.17 @@ -72,12 +72,12 @@
1.18 Graph::EdgeMap<int> flow(G); //0 flow
1.19 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.20 pre_flow_test(G, s, t, cap, flow/*, true*/);
1.21 - Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.22 - pre_flow_ize(G, s, t, cap, flow/*, false*/);
1.23 + // Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.24 + // pre_flow_ize(G, s, t, cap, flow/*, false*/);
1.25 // PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.26 // pre_flow_res(G, s, t, cap, flow/*, true*/);
1.27 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.28 - max_flow_test(G, s, t, cap, flow);
1.29 + //MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.30 + // max_flow_test(G, s, t, cap, flow);
1.31
1.32 {
1.33 std::cout << "preflow ..." << std::endl;
1.34 @@ -91,9 +91,9 @@
1.35 std::cout << "preflow ..." << std::endl;
1.36 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.37 ts.reset();
1.38 - pre_flow_ize.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
1.39 + pre_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
1.40 std::cout << "elapsed time: " << ts << std::endl;
1.41 - std::cout << "flow value: "<< pre_flow_ize.flowValue() << std::endl;
1.42 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
1.43 }
1.44
1.45 // {
1.46 @@ -110,32 +110,32 @@
1.47 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.48 ts.reset();
1.49 int i=0;
1.50 - while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.51 + while (pre_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.52 std::cout << "elapsed time: " << ts << std::endl;
1.53 std::cout << "number of augmentation phases: " << i << std::endl;
1.54 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.55 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
1.56 }
1.57
1.58 - {
1.59 - std::cout << "faster physical blocking flow augmentation ..." << std::endl;
1.60 - FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.61 - ts.reset();
1.62 - int i=0;
1.63 - while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
1.64 - std::cout << "elapsed time: " << ts << std::endl;
1.65 - std::cout << "number of augmentation phases: " << i << std::endl;
1.66 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.67 - }
1.68 +// {
1.69 +// std::cout << "faster physical blocking flow augmentation ..." << std::endl;
1.70 +// FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.71 +// ts.reset();
1.72 +// int i=0;
1.73 +// while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
1.74 +// std::cout << "elapsed time: " << ts << std::endl;
1.75 +// std::cout << "number of augmentation phases: " << i << std::endl;
1.76 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.77 +// }
1.78
1.79 {
1.80 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
1.81 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.82 ts.reset();
1.83 int i=0;
1.84 - while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.85 + while (pre_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.86 std::cout << "elapsed time: " << ts << std::endl;
1.87 std::cout << "number of augmentation phases: " << i << std::endl;
1.88 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.89 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
1.90 }
1.91
1.92 {
1.93 @@ -143,10 +143,10 @@
1.94 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
1.95 ts.reset();
1.96 int i=0;
1.97 - while (max_flow_test.augmentOnShortestPath()) { ++i; }
1.98 + while (pre_flow_test.augmentOnShortestPath()) { ++i; }
1.99 std::cout << "elapsed time: " << ts << std::endl;
1.100 std::cout << "number of augmentation phases: " << i << std::endl;
1.101 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.102 + std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
1.103 }
1.104
1.105