lemon-0.x: src/work/marci/max_flow

     1 // -*- c++ -*-

     2 #include <iostream>

     3 #include <fstream>

     5 #include <sage_graph.h>

     6 #include <hugo/smart_graph.h>

     7 #include <hugo/dimacs.h>

     8 #include <hugo/time_measure.h>

     9 //#include <graph_wrapper.h>

    10 #include <hugo/max_flow.h>

    11 #include <augmenting_flow.h>

    12 //#include <preflow_res.h>

    13 #include <for_each_macros.h>

    14 #include <graph_concept.h>

    16 using namespace hugo;

    18 // Use a DIMACS max flow file as stdin.

    19 // read_dimacs_demo < dimacs_max_flow_file

    22 //   struct Ize {

    23 //   };

    25 //   struct Mize {

    26 //     Ize bumm;

    27 //   };

    29 //   template <typename B>

    30 //     class Huha {

    31 //     public:

    32 //       int u;

    33 //       B brr;

    34 //     };

    37 int main(int, char **) {

    39   typedef SageGraph MutableGraph;

    41   //typedef FullFeatureGraphConcept Graph;

    42   //typedef SmartGraph Graph;

    43   typedef SageGraph Graph;

    44   typedef Graph::Node Node;

    45   typedef Graph::EdgeIt EdgeIt;

    48 //   Mize mize[10];

    49 //   Mize bize[0];

    50 //   Mize zize;

    51 //   typedef Mize Tize[0];

    53 //   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;

    54 //   std::cout << sizeof(bize) << std::endl;

    57 //   Huha<Tize> k;

    58 //   std::cout << sizeof(k) << std::endl;

    61 //   struct Bumm {

    62 //     //int a;

    63 //     bool b;

    64 //   };

    66 //   std::cout << sizeof(Bumm) << std::endl;

    69   Graph g;

    71   Node s, t;

    72   Graph::EdgeMap<int> cap(g);

    73   //readDimacsMaxFlow(std::cin, g, s, t, cap);

    74   readDimacs(std::cin, g, cap, s, t);

    75   Timer ts;

    76   Graph::EdgeMap<int> flow(g); //0 flow

    77   MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >

    78     max_flow_test(g, s, t, cap, flow);

    79   AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >

    80     augmenting_flow_test(g, s, t, cap, flow);

    82   Graph::NodeMap<bool> cut(g);

    84   {

    85     std::cout << "preflow ..." << std::endl;

    86     ts.reset();

    87     max_flow_test.run();

    88     std::cout << "elapsed time: " << ts << std::endl;

    89     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;

    90     max_flow_test.actMinCut(cut);

    92     FOR_EACH_LOC(Graph::EdgeIt, e, g) {

    93       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])

    94 	std::cout << "Slackness does not hold!" << std::endl;

    95       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)

    96 	std::cout << "Slackness does not hold!" << std::endl;

    97     }

    98   }

   100   {

   101     std::cout << "preflow ..." << std::endl;

   102     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);

   103     ts.reset();

   104     max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);

   105     std::cout << "elapsed time: " << ts << std::endl;

   106     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;

   108     FOR_EACH_LOC(Graph::EdgeIt, e, g) {

   109       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])

   110 	std::cout << "Slackness does not hold!" << std::endl;

   111       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)

   112 	std::cout << "Slackness does not hold!" << std::endl;

   113     }

   114   }

   116 //   {

   117 //     std::cout << "wrapped preflow ..." << std::endl;

   118 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);

   119 //     ts.reset();

   120 //     pre_flow_res.run();

   121 //     std::cout << "elapsed time: " << ts << std::endl;

   122 //     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;

   123 //   }

   125   {

   126     std::cout << "physical blocking flow augmentation ..." << std::endl;

   127     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);

   128     ts.reset();

   129     int i=0;

   130     while (augmenting_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }

   131     std::cout << "elapsed time: " << ts << std::endl;

   132     std::cout << "number of augmentation phases: " << i << std::endl;

   133     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   135     FOR_EACH_LOC(Graph::EdgeIt, e, g) {

   136       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])

   137 	std::cout << "Slackness does not hold!" << std::endl;

   138       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)

   139 	std::cout << "Slackness does not hold!" << std::endl;

   140     }

   141   }

   143 //   {

   144 //     std::cout << "faster physical blocking flow augmentation ..." << std::endl;

   145 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);

   146 //     ts.reset();

   147 //     int i=0;

   148 //     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }

   149 //     std::cout << "elapsed time: " << ts << std::endl;

   150 //     std::cout << "number of augmentation phases: " << i << std::endl;

   151 //     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;

   152 //   }

   154   {

   155     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;

   156     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);

   157     ts.reset();

   158     int i=0;

   159     while (augmenting_flow_test.augmentOnBlockingFlow2()) { ++i; }

   160     std::cout << "elapsed time: " << ts << std::endl;

   161     std::cout << "number of augmentation phases: " << i << std::endl;

   162     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   164     FOR_EACH_LOC(Graph::EdgeIt, e, g) {

   165       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])

   166 	std::cout << "Slackness does not hold!" << std::endl;

   167       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)

   168 	std::cout << "Slackness does not hold!" << std::endl;

   169     }

   170   }

   172   {

   173     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;

   174     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);

   175     ts.reset();

   176     int i=0;

   177     while (augmenting_flow_test.augmentOnShortestPath()) { ++i; }

   178     std::cout << "elapsed time: " << ts << std::endl;

   179     std::cout << "number of augmentation phases: " << i << std::endl;

   180     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   182     FOR_EACH_LOC(Graph::EdgeIt, e, g) {

   183       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])

   184 	std::cout << "Slackness does not hold!" << std::endl;

   185       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)

   186 	std::cout << "Slackness does not hold!" << std::endl;

   187     }

   188   }

   190   {

   191     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;

   192     FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);

   193     ts.reset();

   194     int i=0;

   195     while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; }

   196     std::cout << "elapsed time: " << ts << std::endl;

   197     std::cout << "number of augmentation phases: " << i << std::endl;

   198     std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl;

   200     FOR_EACH_LOC(Graph::EdgeIt, e, g) {

   201       if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])

   202 	std::cout << "Slackness does not hold!" << std::endl;

   203       if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)

   204 	std::cout << "Slackness does not hold!" << std::endl;

   205     }

   206   }

   208   return 0;

   209 }

author	marci
	Tue, 17 Aug 2004 13:20:46 +0000
changeset 764	615aca7091d2
parent 652	4dfa1f79bf3e
child 775	e46a1f0623a0
permissions	-rw-r--r--