1.1 --- a/src/work/marci/max_flow_demo.cc Tue Sep 14 17:42:43 2004 +0000
1.2 +++ b/src/work/marci/max_flow_demo.cc Wed Sep 15 10:34:12 2004 +0000
1.3 @@ -3,30 +3,23 @@
1.4 // Use a DIMACS max flow file as stdin.
1.5 // max_flow_demo < dimacs_max_flow_file
1.6
1.7 -
1.8 #include <iostream>
1.9 #include <fstream>
1.10
1.11 -#include <sage_graph.h>
1.12 #include <hugo/smart_graph.h>
1.13 +#include <hugo/list_graph.h>
1.14 #include <hugo/dimacs.h>
1.15 #include <hugo/time_measure.h>
1.16 -//#include <graph_wrapper.h>
1.17 #include <hugo/preflow.h>
1.18 #include <augmenting_flow.h>
1.19 -//#include <preflow_res.h>
1.20 -#include <for_each_macros.h>
1.21 #include <graph_concept.h>
1.22
1.23 using namespace hugo;
1.24
1.25 int main(int, char **) {
1.26
1.27 - typedef SageGraph MutableGraph;
1.28 -
1.29 - //typedef FullFeatureGraphConcept Graph;
1.30 - //typedef SmartGraph Graph;
1.31 - typedef SageGraph Graph;
1.32 + typedef ListGraph MutableGraph;
1.33 + typedef SmartGraph Graph;
1.34 typedef Graph::Node Node;
1.35 typedef Graph::EdgeIt EdgeIt;
1.36
1.37 @@ -53,7 +46,7 @@
1.38 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.39 max_flow_test.minCut(cut);
1.40
1.41 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.42 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.43 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
1.44 std::cout << "Slackness does not hold!" << std::endl;
1.45 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
1.46 @@ -63,13 +56,13 @@
1.47
1.48 {
1.49 std::cout << "preflow ..." << std::endl;
1.50 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.51 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
1.52 ts.reset();
1.53 - max_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
1.54 + max_flow_test.run(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
1.55 std::cout << "elapsed time: " << ts << std::endl;
1.56 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.57
1.58 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.59 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.60 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
1.61 std::cout << "Slackness does not hold!" << std::endl;
1.62 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
1.63 @@ -88,7 +81,7 @@
1.64
1.65 {
1.66 std::cout << "physical blocking flow augmentation ..." << std::endl;
1.67 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.68 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
1.69 ts.reset();
1.70 int i=0;
1.71 while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.72 @@ -96,7 +89,7 @@
1.73 std::cout << "number of augmentation phases: " << i << std::endl;
1.74 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.75
1.76 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.77 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.78 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
1.79 std::cout << "Slackness does not hold!" << std::endl;
1.80 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
1.81 @@ -106,7 +99,7 @@
1.82
1.83 {
1.84 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
1.85 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.86 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
1.87 ts.reset();
1.88 int i=0;
1.89 while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.90 @@ -114,7 +107,7 @@
1.91 std::cout << "number of augmentation phases: " << i << std::endl;
1.92 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.93
1.94 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.95 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.96 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
1.97 std::cout << "Slackness does not hold!" << std::endl;
1.98 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
1.99 @@ -124,7 +117,7 @@
1.100
1.101 {
1.102 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
1.103 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.104 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
1.105 ts.reset();
1.106 int i=0;
1.107 while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
1.108 @@ -132,7 +125,7 @@
1.109 std::cout << "number of augmentation phases: " << i << std::endl;
1.110 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.111
1.112 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.113 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.114 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
1.115 std::cout << "Slackness does not hold!" << std::endl;
1.116 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
1.117 @@ -142,7 +135,7 @@
1.118
1.119 {
1.120 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
1.121 - FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.122 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
1.123 ts.reset();
1.124 int i=0;
1.125 while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; }
1.126 @@ -150,7 +143,7 @@
1.127 std::cout << "number of augmentation phases: " << i << std::endl;
1.128 std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.129
1.130 - FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.131 + for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.132 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
1.133 std::cout << "Slackness does not hold!" << std::endl;
1.134 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)