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 <max_flow.h>

    11 //#include <preflow_res.h>

    12 #include <hugo/for_each_macros.h>

    13 #include <graph_concept.h>

    15 using namespace hugo;

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

    18 // read_dimacs_demo < dimacs_max_flow_file

    21 //   struct Ize {

    22 //   };

    24 //   struct Mize {

    25 //     Ize bumm;

    26 //   };

    28 //   template <typename B>

    29 //     class Huha {

    30 //     public:

    31 //       int u;

    32 //       B brr;

    33 //     };

    36 int main(int, char **) {

    38   typedef SageGraph MutableGraph;

    40   //typedef FullFeatureGraphConcept Graph;

    41   typedef SmartGraph Graph;

    42   //  typedef SageGraph Graph;

    43   typedef Graph::Node Node;

    44   typedef Graph::EdgeIt EdgeIt;

    47 //   Mize mize[10];

    48 //   Mize bize[0];

    49 //   Mize zize;

    50 //   typedef Mize Tize[0];

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

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

    56 //   Huha<Tize> k;

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

    60 //   struct Bumm {

    61 //     //int a;

    62 //     bool b;

    63 //   };

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

    68   Graph g;

    70   Node s, t;

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

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

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

    74   Timer ts;

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

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

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

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

    80   {

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

    82     ts.reset();

    83     max_flow_test.run();

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

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

    86     max_flow_test.actMinCut(cut);

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

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

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

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

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

    93     }

    94   }

    96   {

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

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

    99     ts.reset();

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

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

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

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

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

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

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

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

   109     }

   110   }

   112 //   {

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

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

   115 //     ts.reset();

   116 //     pre_flow_res.run();

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

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

   119 //   }

   121   {

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

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

   124     ts.reset();

   125     int i=0;

   126     while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }

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

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

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

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

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

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

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

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

   136     }

   137   }

   139 //   {

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

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

   142 //     ts.reset();

   143 //     int i=0;

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

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

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

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

   148 //   }

   150   {

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

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

   153     ts.reset();

   154     int i=0;

   155     while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }

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

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

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

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

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

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

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

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

   165     }

   166   }

   168   {

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

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

   171     ts.reset();

   172     int i=0;

   173     while (max_flow_test.augmentOnShortestPath()) { ++i; }

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

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

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

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

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

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

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

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

   183     }

   184   }

   186   {

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

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

   189     ts.reset();

   190     int i=0;

   191     while (max_flow_test.augmentOnShortestPath2()) { ++i; }

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

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

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

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

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

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

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

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

   201     }

   202   }

   204   return 0;

   205 }

author	alpar
	Wed, 04 Aug 2004 19:04:42 +0000
changeset 755	a8c2e828ce0b
parent 651	a56e043aeab1
child 762	511200bdb71f
permissions	-rw-r--r--