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

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

    12 #include <for_each_macros.h>

    13 #include <graph_concept.h>

    15 using std::cout;

    16 using std::endl;

    18 using namespace hugo;

    20 // Use a DIMACS min cost flow file as stdin.

    21 // read_dimacs_demo < dimacs_max_flow_file

    23 int main(int, char **) {

    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;

    32   Graph g;

    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);

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

    45   {

    46     Graph::EdgeIt e;

    47     for (g.first(e); g.valid(e); g.next(e))

    48       cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(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   }

    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);

    76     Graph::EdgeIt e;

    77     for (g.first(e); g.valid(e); g.next(e)) {

    78       if (cut[g.tail(e)] && !cut[g.head(e)]) {

    79 	cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(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.tail(e)] && cut[g.head(e)]) {

    86 	cout << 1+g.id(g.tail(e)) << "->" << 1+g.id(g.head(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   }

    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);

   107 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) {

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

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

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

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

   112 //     }

   113 //   }

   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;

   123 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) {

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

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

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

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

   128 //     }

   129 //   }

   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 // //   }

   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;

   150 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) {

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

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

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

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

   155 //     }

   156 //   }

   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 // //   }

   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;

   179 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) {

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

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

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

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

   184 //     }

   185 //   }

   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;

   197 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) {

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

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

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

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

   202 //     }

   203 //   }

   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;

   215 //     FOR_EACH_LOC(Graph::EdgeIt, e, g) {

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

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

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

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

   220 //     }

   221 //   }

   223   return 0;

   224 }

author	deba
	Wed, 08 Sep 2004 12:06:45 +0000 (2004-09-08)
changeset 822	88226d9fe821
child 921	818510fa3d99
permissions	-rw-r--r--