1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/marci/preflow_bug.cc Thu Jul 29 17:20:51 2004 +0000
1.3 @@ -0,0 +1,224 @@
1.4 +// -*- c++ -*-
1.5 +#include <iostream>
1.6 +#include <fstream>
1.7 +
1.8 +#include <sage_graph.h>
1.9 +#include <hugo/smart_graph.h>
1.10 +#include <hugo/dimacs.h>
1.11 +//#include <hugo/time_measure.h>
1.12 +//#include <graph_wrapper.h>
1.13 +#include <hugo/max_flow.h>
1.14 +//#include <preflow_res.h>
1.15 +#include <for_each_macros.h>
1.16 +#include <graph_concept.h>
1.17 +
1.18 +using std::cout;
1.19 +using std::endl;
1.20 +
1.21 +using namespace hugo;
1.22 +
1.23 +// Use a DIMACS min cost flow file as stdin.
1.24 +// read_dimacs_demo < dimacs_max_flow_file
1.25 +
1.26 +int main(int, char **) {
1.27 +
1.28 + //typedef SageGraph MutableGraph;
1.29 + //typedef FullFeatureGraphConcept Graph;
1.30 + //typedef SmartGraph Graph;
1.31 + typedef SageGraph Graph;
1.32 + typedef Graph::Node Node;
1.33 + typedef Graph::EdgeIt EdgeIt;
1.34 +
1.35 + Graph g;
1.36 +
1.37 + Node s, t;
1.38 + Graph::EdgeMap<int> cap(g);
1.39 + Graph::EdgeMap<int> flow(g); //0 flow
1.40 + //readDimacs(std::cin, g, cap, s, t);
1.41 + readDimacs(std::cin, g, cap, s, t, flow);
1.42 +// Timer ts;
1.43 + MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.44 + max_flow_test(g, s, t, cap, flow);
1.45 +
1.46 + Graph::NodeMap<bool> cut(g);
1.47 +
1.48 + {
1.49 + Graph::EdgeIt e;
1.50 + for (g.first(e); g.valid(e); g.next(e))
1.51 + cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(e)) << " cap: " << cap[e] << " preflow: " << flow[e] << endl;
1.52 + }
1.53 + {
1.54 + Graph::NodeIt n;
1.55 + for (g.first(n); g.valid(n); g.next(n)) {
1.56 + int a=0;
1.57 + {
1.58 + Graph::InEdgeIt e;
1.59 + for (g.first(e, n); g.valid(e); g.next(e)) a+=flow[e];
1.60 + }
1.61 + {
1.62 + Graph::OutEdgeIt e;
1.63 + for (g.first(e, n); g.valid(e); g.next(e)) a-=flow[e];
1.64 + }
1.65 + cout << 1+g.id(n) << " excess: " << a << endl;
1.66 + }
1.67 + }
1.68 +
1.69 +
1.70 + {
1.71 +// std::cout << "preflow ..." << std::endl;
1.72 +// ts.reset();
1.73 + max_flow_test.preflowPhase1(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::PRE_FLOW);
1.74 +// std::cout << "elapsed time: " << ts << std::endl;
1.75 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.76 + std::cout << "flow value 2: "<< max_flow_test.flowValue2() << std::endl;
1.77 + max_flow_test.actMinCut(cut);
1.78 +
1.79 + Graph::EdgeIt e;
1.80 + for (g.first(e); g.valid(e); g.next(e)) {
1.81 + if (cut[g.tail(e)] && !cut[g.head(e)]) {
1.82 + cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(e))
1.83 + << "(forward edge) flow: " << flow[e]
1.84 + << " cap: " << cap[e]<< endl;
1.85 + if (flow[e]!=cap[e])
1.86 + std::cout << "Slackness does not hold!" << std::endl;
1.87 + }
1.88 + if (!cut[g.tail(e)] && cut[g.head(e)]) {
1.89 + cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(e))
1.90 + << "(backward edge) flow: " << flow[e] << endl;
1.91 + if (flow[e]!=0)
1.92 + std::cout << "Slackness does not hold!" << std::endl;
1.93 + }
1.94 + }
1.95 + Graph::NodeIt n;
1.96 + for (g.first(n); g.valid(n); g.next(n)) {
1.97 + if (cut[n])
1.98 + cout << "in cut: " << 1+g.id(n) << endl;
1.99 + }
1.100 + }
1.101 +
1.102 +// {
1.103 +// std::cout << "preflow ..." << std::endl;
1.104 +// ts.reset();
1.105 +// max_flow_test.run();
1.106 +// std::cout << "elapsed time: " << ts << std::endl;
1.107 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.108 +// max_flow_test.actMinCut(cut);
1.109 +
1.110 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.111 +// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
1.112 +// std::cout << "Slackness does not hold!" << std::endl;
1.113 +// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
1.114 +// std::cout << "Slackness does not hold!" << std::endl;
1.115 +// }
1.116 +// }
1.117 +
1.118 +// {
1.119 +// std::cout << "preflow ..." << std::endl;
1.120 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.121 +// ts.reset();
1.122 +// max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
1.123 +// std::cout << "elapsed time: " << ts << std::endl;
1.124 +// std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.125 +
1.126 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.127 +// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
1.128 +// std::cout << "Slackness does not hold!" << std::endl;
1.129 +// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
1.130 +// std::cout << "Slackness does not hold!" << std::endl;
1.131 +// }
1.132 +// }
1.133 +
1.134 +// // {
1.135 +// // std::cout << "wrapped preflow ..." << std::endl;
1.136 +// // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.137 +// // ts.reset();
1.138 +// // pre_flow_res.run();
1.139 +// // std::cout << "elapsed time: " << ts << std::endl;
1.140 +// // std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
1.141 +// // }
1.142 +
1.143 +// {
1.144 +// std::cout << "physical blocking flow augmentation ..." << std::endl;
1.145 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.146 +// ts.reset();
1.147 +// int i=0;
1.148 +// while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.149 +// std::cout << "elapsed time: " << ts << std::endl;
1.150 +// std::cout << "number of augmentation phases: " << i << std::endl;
1.151 +// std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.152 +
1.153 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.154 +// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
1.155 +// std::cout << "Slackness does not hold!" << std::endl;
1.156 +// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
1.157 +// std::cout << "Slackness does not hold!" << std::endl;
1.158 +// }
1.159 +// }
1.160 +
1.161 +// // {
1.162 +// // std::cout << "faster physical blocking flow augmentation ..." << std::endl;
1.163 +// // FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.164 +// // ts.reset();
1.165 +// // int i=0;
1.166 +// // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
1.167 +// // std::cout << "elapsed time: " << ts << std::endl;
1.168 +// // std::cout << "number of augmentation phases: " << i << std::endl;
1.169 +// // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.170 +// // }
1.171 +
1.172 +// {
1.173 +// std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
1.174 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.175 +// ts.reset();
1.176 +// int i=0;
1.177 +// while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.178 +// std::cout << "elapsed time: " << ts << std::endl;
1.179 +// std::cout << "number of augmentation phases: " << i << std::endl;
1.180 +// std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.181 +
1.182 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.183 +// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
1.184 +// std::cout << "Slackness does not hold!" << std::endl;
1.185 +// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
1.186 +// std::cout << "Slackness does not hold!" << std::endl;
1.187 +// }
1.188 +// }
1.189 +
1.190 +// {
1.191 +// std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
1.192 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.193 +// ts.reset();
1.194 +// int i=0;
1.195 +// while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
1.196 +// std::cout << "elapsed time: " << ts << std::endl;
1.197 +// std::cout << "number of augmentation phases: " << i << std::endl;
1.198 +// std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.199 +
1.200 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.201 +// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
1.202 +// std::cout << "Slackness does not hold!" << std::endl;
1.203 +// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
1.204 +// std::cout << "Slackness does not hold!" << std::endl;
1.205 +// }
1.206 +// }
1.207 +
1.208 +// {
1.209 +// std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
1.210 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.211 +// ts.reset();
1.212 +// int i=0;
1.213 +// while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; }
1.214 +// std::cout << "elapsed time: " << ts << std::endl;
1.215 +// std::cout << "number of augmentation phases: " << i << std::endl;
1.216 +// std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.217 +
1.218 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) {
1.219 +// if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
1.220 +// std::cout << "Slackness does not hold!" << std::endl;
1.221 +// if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
1.222 +// std::cout << "Slackness does not hold!" << std::endl;
1.223 +// }
1.224 +// }
1.225 +
1.226 + return 0;
1.227 +}