src/work/marci/preflow_bug.cc
author marci
Wed, 26 Jan 2005 15:54:06 +0000
changeset 1097 c91e765266d7
parent 921 818510fa3d99
permissions -rw-r--r--
A proposal or test implementation for linear expression`
     1 // -*- c++ -*-
     2 #include <iostream>
     3 #include <fstream>
     4 
     5 #include <sage_graph.h>
     6 #include <lemon/smart_graph.h>
     7 #include <lemon/dimacs.h>
     8 //#include <lemon/time_measure.h>
     9 //#include <graph_wrapper.h>
    10 #include <lemon/max_flow.h>
    11 //#include <preflow_res.h>
    12 #include <for_each_macros.h>
    13 #include <graph_concept.h>
    14 
    15 using std::cout;
    16 using std::endl;
    17 
    18 using namespace lemon;
    19 
    20 // Use a DIMACS min cost flow file as stdin.
    21 // read_dimacs_demo < dimacs_max_flow_file
    22 
    23 int main(int, char **) {
    24 
    25   //typedef SageGraph MutableGraph;
    26   //typedef FullFeatureGraphConcept Graph;
    27   //typedef SmartGraph Graph;
    28   typedef SageGraph Graph;
    29   typedef Graph::Node Node;
    30   typedef Graph::EdgeIt EdgeIt;
    31 
    32   Graph g;
    33 
    34   Node s, t;
    35   Graph::EdgeMap<int> cap(g);
    36   Graph::EdgeMap<int> flow(g); //0 flow
    37   //readDimacs(std::cin, g, cap, s, t);
    38   readDimacs(std::cin, g, cap, s, t, flow);
    39 //  Timer ts;
    40   MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    41     max_flow_test(g, s, t, cap, flow);
    42   
    43   Graph::NodeMap<bool> cut(g);
    44 
    45   {
    46     Graph::EdgeIt e;
    47     for (g.first(e); g.valid(e); g.next(e))
    48       cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) << " cap: " << cap[e] << " preflow: " << flow[e] << endl;
    49   }
    50   {
    51     Graph::NodeIt n;
    52     for (g.first(n); g.valid(n); g.next(n)) {
    53       int a=0;
    54       {
    55 	Graph::InEdgeIt e;
    56 	for (g.first(e, n); g.valid(e); g.next(e)) a+=flow[e];
    57       }
    58       {
    59 	Graph::OutEdgeIt e;
    60 	for (g.first(e, n); g.valid(e); g.next(e)) a-=flow[e];
    61       }
    62       cout << 1+g.id(n) << " excess: " << a << endl;
    63     }
    64   }
    65 
    66 
    67   {
    68 //    std::cout << "preflow ..." << std::endl;
    69 //    ts.reset();
    70     max_flow_test.preflowPhase1(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::PRE_FLOW);
    71 //    std::cout << "elapsed time: " << ts << std::endl;
    72     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    73     std::cout << "flow value 2: "<< max_flow_test.flowValue2() << std::endl;
    74     max_flow_test.actMinCut(cut);
    75     
    76     Graph::EdgeIt e;
    77     for (g.first(e); g.valid(e); g.next(e)) {
    78       if (cut[g.source(e)] && !cut[g.target(e)]) {
    79 	cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) 
    80 	     << "(forward edge) flow: " << flow[e] 
    81 	     << " cap: " << cap[e]<< endl;
    82 	if (flow[e]!=cap[e]) 
    83 	std::cout << "Slackness does not hold!" << std::endl;
    84       }
    85       if (!cut[g.source(e)] && cut[g.target(e)]) {
    86 	cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) 
    87 	     << "(backward edge) flow: " << flow[e] << endl;
    88 	if (flow[e]!=0) 
    89 	std::cout << "Slackness does not hold!" << std::endl;
    90       }
    91     }
    92     Graph::NodeIt n;
    93     for (g.first(n); g.valid(n); g.next(n)) {
    94       if (cut[n]) 
    95 	cout << "in cut: " << 1+g.id(n) << endl;
    96     }
    97   }
    98 
    99 //   {
   100 //     std::cout << "preflow ..." << std::endl;
   101 //     ts.reset();
   102 //     max_flow_test.run();
   103 //     std::cout << "elapsed time: " << ts << std::endl;
   104 //     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   105 //     max_flow_test.actMinCut(cut);
   106 
   107 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
   108 //       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
   109 // 	std::cout << "Slackness does not hold!" << std::endl;
   110 //       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
   111 // 	std::cout << "Slackness does not hold!" << std::endl;
   112 //     }
   113 //   }
   114 
   115 //   {
   116 //     std::cout << "preflow ..." << std::endl;
   117 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   118 //     ts.reset();
   119 //     max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
   120 //     std::cout << "elapsed time: " << ts << std::endl;
   121 //     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   122 
   123 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
   124 //       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
   125 // 	std::cout << "Slackness does not hold!" << std::endl;
   126 //       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
   127 // 	std::cout << "Slackness does not hold!" << std::endl;
   128 //     }
   129 //   }
   130 
   131 // //   {
   132 // //     std::cout << "wrapped preflow ..." << std::endl;
   133 // //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   134 // //     ts.reset();
   135 // //     pre_flow_res.run();
   136 // //     std::cout << "elapsed time: " << ts << std::endl;
   137 // //     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
   138 // //   }
   139 
   140 //   {
   141 //     std::cout << "physical blocking flow augmentation ..." << std::endl;
   142 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   143 //     ts.reset();
   144 //     int i=0;
   145 //     while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
   146 //     std::cout << "elapsed time: " << ts << std::endl;
   147 //     std::cout << "number of augmentation phases: " << i << std::endl; 
   148 //     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
   149 
   150 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
   151 //       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
   152 // 	std::cout << "Slackness does not hold!" << std::endl;
   153 //       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
   154 // 	std::cout << "Slackness does not hold!" << std::endl;
   155 //     }
   156 //   }
   157 
   158 // //   {
   159 // //     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
   160 // //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   161 // //     ts.reset();
   162 // //     int i=0;
   163 // //     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
   164 // //     std::cout << "elapsed time: " << ts << std::endl;
   165 // //     std::cout << "number of augmentation phases: " << i << std::endl; 
   166 // //     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   167 // //   }
   168 
   169 //   {
   170 //     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
   171 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   172 //     ts.reset();
   173 //     int i=0;
   174 //     while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
   175 //     std::cout << "elapsed time: " << ts << std::endl;
   176 //     std::cout << "number of augmentation phases: " << i << std::endl; 
   177 //     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
   178 
   179 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
   180 //       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
   181 // 	std::cout << "Slackness does not hold!" << std::endl;
   182 //       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
   183 // 	std::cout << "Slackness does not hold!" << std::endl;
   184 //     }
   185 //   }
   186 
   187 //   {
   188 //     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
   189 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   190 //     ts.reset();
   191 //     int i=0;
   192 //     while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
   193 //     std::cout << "elapsed time: " << ts << std::endl;
   194 //     std::cout << "number of augmentation phases: " << i << std::endl; 
   195 //     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
   196 
   197 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
   198 //       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
   199 // 	std::cout << "Slackness does not hold!" << std::endl;
   200 //       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
   201 // 	std::cout << "Slackness does not hold!" << std::endl;
   202 //     }
   203 //   }
   204 
   205 //   {
   206 //     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
   207 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
   208 //     ts.reset();
   209 //     int i=0;
   210 //     while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; }
   211 //     std::cout << "elapsed time: " << ts << std::endl;
   212 //     std::cout << "number of augmentation phases: " << i << std::endl; 
   213 //     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;
   214 
   215 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
   216 //       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
   217 // 	std::cout << "Slackness does not hold!" << std::endl;
   218 //       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
   219 // 	std::cout << "Slackness does not hold!" << std::endl;
   220 //     }
   221 //   }
   222 
   223   return 0;
   224 }