src/work/marci/edmonds_karp_demo.cc
changeset 472 052af4060f3e
parent 465 d72e56f1730d
equal deleted inserted replaced
30:76ec1617af14 31:b10b132db63e
     3 #include <fstream>
     3 #include <fstream>
     4 
     4 
     5 #include <list_graph.h>
     5 #include <list_graph.h>
     6 #include <smart_graph.h>
     6 #include <smart_graph.h>
     7 #include <dimacs.h>
     7 #include <dimacs.h>
     8 #include <edmonds_karp.h>
     8 //#include <edmonds_karp.h>
     9 #include <time_measure.h>
     9 #include <time_measure.h>
    10 //#include <graph_wrapper.h>
    10 //#include <graph_wrapper.h>
    11 #include <preflow.h>
    11 #include <preflow.h>
    12 #include <preflow_res.h>
    12 //#include <preflow_res.h>
    13 #include <for_each_macros.h>
    13 #include <for_each_macros.h>
    14 
    14 
    15 using namespace hugo;
    15 using namespace hugo;
    16 
    16 
    17 // Use a DIMACS max flow file as stdin.
    17 // Use a DIMACS max flow file as stdin.
    70   readDimacsMaxFlow(std::cin, G, s, t, cap);
    70   readDimacsMaxFlow(std::cin, G, s, t, cap);
    71   Timer ts;
    71   Timer ts;
    72   Graph::EdgeMap<int> flow(G); //0 flow
    72   Graph::EdgeMap<int> flow(G); //0 flow
    73   Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    73   Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    74     pre_flow_test(G, s, t, cap, flow/*, true*/);
    74     pre_flow_test(G, s, t, cap, flow/*, true*/);
    75   Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    75   //  Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    76     pre_flow_ize(G, s, t, cap, flow/*, false*/);
    76   //  pre_flow_ize(G, s, t, cap, flow/*, false*/);
    77 //   PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    77 //   PreflowRes<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    78 //     pre_flow_res(G, s, t, cap, flow/*, true*/);
    78 //     pre_flow_res(G, s, t, cap, flow/*, true*/);
    79   MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    79   //MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    80     max_flow_test(G, s, t, cap, flow);
    80   //  max_flow_test(G, s, t, cap, flow);
    81 
    81 
    82   {
    82   {
    83     std::cout << "preflow ..." << std::endl;
    83     std::cout << "preflow ..." << std::endl;
    84     ts.reset();
    84     ts.reset();
    85     pre_flow_test.run();
    85     pre_flow_test.run();
    89 
    89 
    90   {
    90   {
    91     std::cout << "preflow ..." << std::endl;
    91     std::cout << "preflow ..." << std::endl;
    92     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    92     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
    93     ts.reset();
    93     ts.reset();
    94     pre_flow_ize.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
    94     pre_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
    95     std::cout << "elapsed time: " << ts << std::endl;
    95     std::cout << "elapsed time: " << ts << std::endl;
    96     std::cout << "flow value: "<< pre_flow_ize.flowValue() << std::endl;
    96     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
    97   }
    97   }
    98 
    98 
    99 //   {
    99 //   {
   100 //     std::cout << "wrapped preflow ..." << std::endl;
   100 //     std::cout << "wrapped preflow ..." << std::endl;
   101 //     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   101 //     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   108   {
   108   {
   109     std::cout << "physical blocking flow augmentation ..." << std::endl;
   109     std::cout << "physical blocking flow augmentation ..." << std::endl;
   110     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   110     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   111     ts.reset();
   111     ts.reset();
   112     int i=0;
   112     int i=0;
   113     while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
   113     while (pre_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
   114     std::cout << "elapsed time: " << ts << std::endl;
   114     std::cout << "elapsed time: " << ts << std::endl;
   115     std::cout << "number of augmentation phases: " << i << std::endl; 
   115     std::cout << "number of augmentation phases: " << i << std::endl; 
   116     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   116     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
   117   }
   117   }
   118 
   118 
   119   {
   119 //   {
   120     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
   120 //     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
   121     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   121 //     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   122     ts.reset();
   122 //     ts.reset();
   123     int i=0;
   123 //     int i=0;
   124     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
   124 //     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
   125     std::cout << "elapsed time: " << ts << std::endl;
   125 //     std::cout << "elapsed time: " << ts << std::endl;
   126     std::cout << "number of augmentation phases: " << i << std::endl; 
   126 //     std::cout << "number of augmentation phases: " << i << std::endl; 
   127     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   127 //     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   128   }
   128 //   }
   129 
   129 
   130   {
   130   {
   131     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
   131     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
   132     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   132     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   133     ts.reset();
   133     ts.reset();
   134     int i=0;
   134     int i=0;
   135     while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
   135     while (pre_flow_test.augmentOnBlockingFlow2()) { ++i; }
   136     std::cout << "elapsed time: " << ts << std::endl;
   136     std::cout << "elapsed time: " << ts << std::endl;
   137     std::cout << "number of augmentation phases: " << i << std::endl; 
   137     std::cout << "number of augmentation phases: " << i << std::endl; 
   138     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   138     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
   139   }
   139   }
   140 
   140 
   141   {
   141   {
   142     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
   142     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
   143     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   143     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
   144     ts.reset();
   144     ts.reset();
   145     int i=0;
   145     int i=0;
   146     while (max_flow_test.augmentOnShortestPath()) { ++i; }
   146     while (pre_flow_test.augmentOnShortestPath()) { ++i; }
   147     std::cout << "elapsed time: " << ts << std::endl;
   147     std::cout << "elapsed time: " << ts << std::endl;
   148     std::cout << "number of augmentation phases: " << i << std::endl; 
   148     std::cout << "number of augmentation phases: " << i << std::endl; 
   149     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
   149     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
   150   }
   150   }
   151 
   151 
   152 
   152 
   153   return 0;
   153   return 0;
   154 }
   154 }