1.1 --- a/src/work/marci/preflow_bug.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,224 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#include <iostream>
1.6 -#include <fstream>
1.7 -
1.8 -#include <sage_graph.h>
1.9 -#include <lemon/smart_graph.h>
1.10 -#include <lemon/dimacs.h>
1.11 -//#include <lemon/time_measure.h>
1.12 -//#include <graph_wrapper.h>
1.13 -#include <lemon/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 lemon;
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.source(e)) << "->" << 1+g.id(g.target(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.source(e)] && !cut[g.target(e)]) {
1.82 - cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(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.source(e)] && cut[g.target(e)]) {
1.89 - cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(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.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
1.112 -// std::cout << "Slackness does not hold!" << std::endl;
1.113 -// if (!cut[g.source(e)] && cut[g.target(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.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
1.128 -// std::cout << "Slackness does not hold!" << std::endl;
1.129 -// if (!cut[g.source(e)] && cut[g.target(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.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
1.155 -// std::cout << "Slackness does not hold!" << std::endl;
1.156 -// if (!cut[g.source(e)] && cut[g.target(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.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
1.184 -// std::cout << "Slackness does not hold!" << std::endl;
1.185 -// if (!cut[g.source(e)] && cut[g.target(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.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
1.202 -// std::cout << "Slackness does not hold!" << std::endl;
1.203 -// if (!cut[g.source(e)] && cut[g.target(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.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
1.220 -// std::cout << "Slackness does not hold!" << std::endl;
1.221 -// if (!cut[g.source(e)] && cut[g.target(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 -}