1.1 --- a/src/work/marci/max_flow_demo.cc Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,155 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -
1.6 -// Use a DIMACS max flow file as stdin.
1.7 -// max_flow_demo < dimacs_max_flow_file
1.8 -
1.9 -#include <iostream>
1.10 -#include <fstream>
1.11 -
1.12 -#include <lemon/smart_graph.h>
1.13 -#include <lemon/list_graph.h>
1.14 -#include <lemon/dimacs.h>
1.15 -#include <lemon/time_measure.h>
1.16 -#include <lemon/preflow.h>
1.17 -#include <augmenting_flow.h>
1.18 -#include <graph_concept.h>
1.19 -
1.20 -using namespace lemon;
1.21 -
1.22 -int main(int, char **) {
1.23 -
1.24 - typedef ListGraph MutableGraph;
1.25 - typedef SmartGraph Graph;
1.26 - typedef Graph::Node Node;
1.27 - typedef Graph::EdgeIt EdgeIt;
1.28 -
1.29 - Graph g;
1.30 -
1.31 - Node s, t;
1.32 - Graph::EdgeMap<int> cap(g);
1.33 - //readDimacsMaxFlow(std::cin, g, s, t, cap);
1.34 - readDimacs(std::cin, g, cap, s, t);
1.35 - Timer ts;
1.36 - Graph::EdgeMap<int> flow(g); //0 flow
1.37 - Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.38 - max_flow_test(g, s, t, cap, flow);
1.39 - AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
1.40 - augmenting_flow_test(g, s, t, cap, flow);
1.41 -
1.42 - Graph::NodeMap<bool> cut(g);
1.43 -
1.44 - {
1.45 - std::cout << "preflow ..." << std::endl;
1.46 - ts.reset();
1.47 - max_flow_test.run();
1.48 - std::cout << "elapsed time: " << ts << std::endl;
1.49 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.50 - max_flow_test.minCut(cut);
1.51 -
1.52 - for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.53 - if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
1.54 - std::cout << "Slackness does not hold!" << std::endl;
1.55 - if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
1.56 - std::cout << "Slackness does not hold!" << std::endl;
1.57 - }
1.58 - }
1.59 -
1.60 - {
1.61 - std::cout << "preflow ..." << std::endl;
1.62 - for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
1.63 - ts.reset();
1.64 - max_flow_test.run(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
1.65 - std::cout << "elapsed time: " << ts << std::endl;
1.66 - std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
1.67 -
1.68 - for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.69 - if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
1.70 - std::cout << "Slackness does not hold!" << std::endl;
1.71 - if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
1.72 - std::cout << "Slackness does not hold!" << std::endl;
1.73 - }
1.74 - }
1.75 -
1.76 -// {
1.77 -// std::cout << "wrapped preflow ..." << std::endl;
1.78 -// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
1.79 -// ts.reset();
1.80 -// pre_flow_res.run();
1.81 -// std::cout << "elapsed time: " << ts << std::endl;
1.82 -// std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
1.83 -// }
1.84 -
1.85 - {
1.86 - std::cout << "physical blocking flow augmentation ..." << std::endl;
1.87 - for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
1.88 - ts.reset();
1.89 - int i=0;
1.90 - while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
1.91 - std::cout << "elapsed time: " << ts << std::endl;
1.92 - std::cout << "number of augmentation phases: " << i << std::endl;
1.93 - std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.94 -
1.95 - for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.96 - if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
1.97 - std::cout << "Slackness does not hold!" << std::endl;
1.98 - if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
1.99 - std::cout << "Slackness does not hold!" << std::endl;
1.100 - }
1.101 - }
1.102 -
1.103 - {
1.104 - std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
1.105 - for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
1.106 - ts.reset();
1.107 - int i=0;
1.108 - while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
1.109 - std::cout << "elapsed time: " << ts << std::endl;
1.110 - std::cout << "number of augmentation phases: " << i << std::endl;
1.111 - std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.112 -
1.113 - for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.114 - if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
1.115 - std::cout << "Slackness does not hold!" << std::endl;
1.116 - if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
1.117 - std::cout << "Slackness does not hold!" << std::endl;
1.118 - }
1.119 - }
1.120 -
1.121 - {
1.122 - std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
1.123 - for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
1.124 - ts.reset();
1.125 - int i=0;
1.126 - while (augmenting_flow_test.augmentOnShortestPath()) { ++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: "<< augmenting_flow_test.flowValue() << std::endl;
1.130 -
1.131 - for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.132 - if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
1.133 - std::cout << "Slackness does not hold!" << std::endl;
1.134 - if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
1.135 - std::cout << "Slackness does not hold!" << std::endl;
1.136 - }
1.137 - }
1.138 -
1.139 - {
1.140 - std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
1.141 - for(Graph::EdgeIt e(g); e!=INVALID; ++e) flow.set(e, 0);
1.142 - ts.reset();
1.143 - int i=0;
1.144 - while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; }
1.145 - std::cout << "elapsed time: " << ts << std::endl;
1.146 - std::cout << "number of augmentation phases: " << i << std::endl;
1.147 - std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
1.148 -
1.149 - for(Graph::EdgeIt e(g); e!=INVALID; ++e) {
1.150 - if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e])
1.151 - std::cout << "Slackness does not hold!" << std::endl;
1.152 - if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0)
1.153 - std::cout << "Slackness does not hold!" << std::endl;
1.154 - }
1.155 - }
1.156 -
1.157 - return 0;
1.158 -}