source: lemon-0.x/src/work/marci/preflow_bug.cc @ 1309:b3ce42a4d7d2

// -*- c++ -*-
#include <iostream>
#include <fstream>

#include <sage_graph.h>
#include <lemon/smart_graph.h>
#include <lemon/dimacs.h>
//#include <lemon/time_measure.h>
//#include <graph_wrapper.h>
#include <lemon/max_flow.h>
//#include <preflow_res.h>
#include <for_each_macros.h>
#include <graph_concept.h>

using std::cout;
using std::endl;

using namespace lemon;

// Use a DIMACS min cost flow file as stdin.
// read_dimacs_demo < dimacs_max_flow_file

int main(int, char **) {

  //typedef SageGraph MutableGraph;
  //typedef FullFeatureGraphConcept Graph;
  //typedef SmartGraph Graph;
  typedef SageGraph Graph;
  typedef Graph::Node Node;
  typedef Graph::EdgeIt EdgeIt;

  Graph g;

  Node s, t;
  Graph::EdgeMap<int> cap(g);
  Graph::EdgeMap<int> flow(g); //0 flow
  //readDimacs(std::cin, g, cap, s, t);
  readDimacs(std::cin, g, cap, s, t, flow);
//  Timer ts;
  MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    max_flow_test(g, s, t, cap, flow);
  
  Graph::NodeMap<bool> cut(g);

  {
    Graph::EdgeIt e;
    for (g.first(e); g.valid(e); g.next(e))
      cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) << " cap: " << cap[e] << " preflow: " << flow[e] << endl;
  }
  {
    Graph::NodeIt n;
    for (g.first(n); g.valid(n); g.next(n)) {
      int a=0;
      {
        Graph::InEdgeIt e;
        for (g.first(e, n); g.valid(e); g.next(e)) a+=flow[e];
      }
      {
        Graph::OutEdgeIt e;
        for (g.first(e, n); g.valid(e); g.next(e)) a-=flow[e];
      }
      cout << 1+g.id(n) << " excess: " << a << endl;
    }
  }


  {
//    std::cout << "preflow ..." << std::endl;
//    ts.reset();
    max_flow_test.preflowPhase1(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::PRE_FLOW);
//    std::cout << "elapsed time: " << ts << std::endl;
    std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    std::cout << "flow value 2: "<< max_flow_test.flowValue2() << std::endl;
    max_flow_test.actMinCut(cut);
    
    Graph::EdgeIt e;
    for (g.first(e); g.valid(e); g.next(e)) {
      if (cut[g.source(e)] && !cut[g.target(e)]) {
        cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) 
             << "(forward edge) flow: " << flow[e] 
             << " cap: " << cap[e]<< endl;
        if (flow[e]!=cap[e]) 
        std::cout << "Slackness does not hold!" << std::endl;
      }
      if (!cut[g.source(e)] && cut[g.target(e)]) {
        cout << 1+g.id(g.source(e)) << "->" << 1+g.id(g.target(e)) 
             << "(backward edge) flow: " << flow[e] << endl;
        if (flow[e]!=0) 
        std::cout << "Slackness does not hold!" << std::endl;
      }
    }
    Graph::NodeIt n;
    for (g.first(n); g.valid(n); g.next(n)) {
      if (cut[n]) 
        cout << "in cut: " << 1+g.id(n) << endl;
    }
  }

//   {
//     std::cout << "preflow ..." << std::endl;
//     ts.reset();
//     max_flow_test.run();
//     std::cout << "elapsed time: " << ts << std::endl;
//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
//     max_flow_test.actMinCut(cut);

//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
//       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
//      std::cout << "Slackness does not hold!" << std::endl;
//       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
//      std::cout << "Slackness does not hold!" << std::endl;
//     }
//   }

//   {
//     std::cout << "preflow ..." << std::endl;
//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
//     ts.reset();
//     max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
//     std::cout << "elapsed time: " << ts << std::endl;
//     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;

//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
//       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
//      std::cout << "Slackness does not hold!" << std::endl;
//       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
//      std::cout << "Slackness does not hold!" << std::endl;
//     }
//   }

// //   {
// //     std::cout << "wrapped preflow ..." << std::endl;
// //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
// //     ts.reset();
// //     pre_flow_res.run();
// //     std::cout << "elapsed time: " << ts << std::endl;
// //     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
// //   }

//   {
//     std::cout << "physical blocking flow augmentation ..." << std::endl;
//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
//     ts.reset();
//     int i=0;
//     while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
//     std::cout << "elapsed time: " << ts << std::endl;
//     std::cout << "number of augmentation phases: " << i << std::endl; 
//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
//       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
//      std::cout << "Slackness does not hold!" << std::endl;
//       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
//      std::cout << "Slackness does not hold!" << std::endl;
//     }
//   }

// //   {
// //     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
// //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
// //     ts.reset();
// //     int i=0;
// //     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
// //     std::cout << "elapsed time: " << ts << std::endl;
// //     std::cout << "number of augmentation phases: " << i << std::endl; 
// //     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
// //   }

//   {
//     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
//     ts.reset();
//     int i=0;
//     while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }
//     std::cout << "elapsed time: " << ts << std::endl;
//     std::cout << "number of augmentation phases: " << i << std::endl; 
//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
//       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
//      std::cout << "Slackness does not hold!" << std::endl;
//       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
//      std::cout << "Slackness does not hold!" << std::endl;
//     }
//   }

//   {
//     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
//     ts.reset();
//     int i=0;
//     while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }
//     std::cout << "elapsed time: " << ts << std::endl;
//     std::cout << "number of augmentation phases: " << i << std::endl; 
//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
//       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
//      std::cout << "Slackness does not hold!" << std::endl;
//       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
//      std::cout << "Slackness does not hold!" << std::endl;
//     }
//   }

//   {
//     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
//     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
//     ts.reset();
//     int i=0;
//     while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; }
//     std::cout << "elapsed time: " << ts << std::endl;
//     std::cout << "number of augmentation phases: " << i << std::endl; 
//     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

//     FOR_EACH_LOC(Graph::EdgeIt, e, g) {
//       if (cut[g.source(e)] && !cut[g.target(e)] && !flow[e]==cap[e]) 
//      std::cout << "Slackness does not hold!" << std::endl;
//       if (!cut[g.source(e)] && cut[g.target(e)] && flow[e]>0) 
//      std::cout << "Slackness does not hold!" << std::endl;
//     }
//   }

  return 0;
}