1.1 --- a/src/work/marci/lg_vs_sg_vs_sg.cc Tue Aug 17 10:24:19 2004 +0000
1.2 +++ b/src/work/marci/lg_vs_sg_vs_sg.cc Tue Aug 17 11:20:16 2004 +0000
1.3 @@ -7,9 +7,10 @@
1.4 #include <hugo/list_graph.h>
1.5 #include <hugo/smart_graph.h>
1.6 #include <hugo/dimacs.h>
1.7 -#include <max_flow.h>
1.8 +#include <hugo/max_flow.h>
1.9 +#include <augmenting_flow.h>
1.10 #include <hugo/time_measure.h>
1.11 -#include <hugo/for_each_macros.h>
1.12 +#include <for_each_macros.h>
1.13
1.14 using namespace hugo;
1.15
1.16 @@ -37,6 +38,8 @@
1.17 Graph::EdgeMap<int> flow(g); //0 flow
1.18 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.19 max_flow_test(g, s, t, cap, flow/*, true*/);
1.20 + AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.21 + augmenting_flow_test(g, s, t, cap, flow/*, true*/);
1.22
1.23 std::cout << "SageGraph ..." << std::endl;
1.24
1.25 @@ -53,10 +56,10 @@
1.26 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.27 ts.reset();
1.28 int i=0;
1.29 - while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.30 + while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.31 std::cout << "elapsed time: " << ts << std::endl;
1.32 std::cout << "number of augmentation phases: " << i << std::endl;
1.33 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.34 + std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.35 }
1.36
1.37 // {
1.38 @@ -75,10 +78,10 @@
1.39 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.40 ts.reset();
1.41 int i=0;
1.42 - while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.43 + while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.44 std::cout << "elapsed time: " << ts << std::endl;
1.45 std::cout << "number of augmentation phases: " << i << std::endl;
1.46 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.47 + std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.48 }
1.49
1.50 {
1.51 @@ -86,10 +89,10 @@
1.52 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.53 ts.reset();
1.54 int i=0;
1.55 - while (max_flow_test.augmentOnShortestPath()) { ++i; }
1.56 + while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
1.57 std::cout << "elapsed time: " << ts << std::endl;
1.58 std::cout << "number of augmentation phases: " << i << std::endl;
1.59 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.60 + std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.61 }
1.62 }
1.63
1.64 @@ -109,6 +112,8 @@
1.65 Graph::EdgeMap<int> flow(g); //0 flow
1.66 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.67 max_flow_test(g, s, t, cap, flow/*, true*/);
1.68 + AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.69 + augmenting_flow_test(g, s, t, cap, flow/*, true*/);
1.70 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.71 // max_flow_test(g, s, t, cap, flow);
1.72
1.73 @@ -128,10 +133,10 @@
1.74 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.75 ts.reset();
1.76 int i=0;
1.77 - while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.78 + while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.79 std::cout << "elapsed time: " << ts << std::endl;
1.80 std::cout << "number of augmentation phases: " << i << std::endl;
1.81 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.82 + std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.83 }
1.84
1.85 // {
1.86 @@ -150,10 +155,10 @@
1.87 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.88 ts.reset();
1.89 int i=0;
1.90 - while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.91 + while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.92 std::cout << "elapsed time: " << ts << std::endl;
1.93 std::cout << "number of augmentation phases: " << i << std::endl;
1.94 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.95 + std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.96 }
1.97
1.98 {
1.99 @@ -161,10 +166,10 @@
1.100 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.101 ts.reset();
1.102 int i=0;
1.103 - while (max_flow_test.augmentOnShortestPath()) { ++i; }
1.104 + while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
1.105 std::cout << "elapsed time: " << ts << std::endl;
1.106 std::cout << "number of augmentation phases: " << i << std::endl;
1.107 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.108 + std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.109 }
1.110 }
1.111
1.112 @@ -184,6 +189,8 @@
1.113 Graph::EdgeMap<int> flow(g); //0 flow
1.114 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.115 max_flow_test(g, s, t, cap, flow/*, true*/);
1.116 + AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.117 + augmenting_flow_test(g, s, t, cap, flow/*, true*/);
1.118 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.119 // max_flow_test(g, s, t, cap, flow);
1.120
1.121 @@ -203,10 +210,10 @@
1.122 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.123 ts.reset();
1.124 int i=0;
1.125 - while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.126 + while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.127 std::cout << "elapsed time: " << ts << std::endl;
1.128 std::cout << "number of augmentation phases: " << i << std::endl;
1.129 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.130 + std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.131 }
1.132
1.133 // {
1.134 @@ -225,10 +232,10 @@
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 (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.139 + while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.140 std::cout << "elapsed time: " << ts << std::endl;
1.141 std::cout << "number of augmentation phases: " << i << std::endl;
1.142 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.143 + std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.144 }
1.145
1.146 {
1.147 @@ -236,15 +243,12 @@
1.148 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.149 ts.reset();
1.150 int i=0;
1.151 - while (max_flow_test.augmentOnShortestPath()) { ++i; }
1.152 + while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
1.153 std::cout << "elapsed time: " << ts << std::endl;
1.154 std::cout << "number of augmentation phases: " << i << std::endl;
1.155 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.156 + std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.157 }
1.158 }
1.159
1.160 -
1.161 -
1.162 -
1.163 return 0;
1.164 }