Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci/lg_vs_sg.cc
changeset 476 cfe550761745
parent 465 d72e56f1730d
child 480 4fb0d1e166ea
equal deleted inserted replaced
3:484539aad7e7 4:f56fbc4a6dfd 
     4 #include <string>
 
     4 #include <string>
 
     5 
     5 
     6 #include <list_graph.h>
 
     6 #include <list_graph.h>
 
     7 #include <smart_graph.h>
 
     7 #include <smart_graph.h>
 
     8 #include <dimacs.h>
 
     8 #include <dimacs.h>
 
     9 #include <edmonds_karp.h>
 
       
    10 #include <preflow.h>
 
     9 #include <preflow.h>
 
    11 #include <time_measure.h>
 
    10 #include <time_measure.h>
 
    12 #include <for_each_macros.h>
 
    11 #include <for_each_macros.h>
 
    13 
    12 
    14 using namespace hugo;
 
    13 using namespace hugo;
 
    32     std::ifstream ins(in.c_str());
 
    31     std::ifstream ins(in.c_str());
 
    33     readDimacsMaxFlow(ins, G, s, t, cap);
 
    32     readDimacsMaxFlow(ins, G, s, t, cap);
 
    34 
    33 
    35     Timer ts;
 
    34     Timer ts;
 
    36     Graph::EdgeMap<int> flow(G); //0 flow
 
    35     Graph::EdgeMap<int> flow(G); //0 flow
 
    37     Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
       
    38       pre_flow_test(G, s, t, cap, flow/*, true*/);
 
       
    39     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    36     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
    40       max_flow_test(G, s, t, cap, flow);
 
    37       max_flow_test(G, s, t, cap, flow/*, true*/);
 
    41 
    38 
    42     std::cout << "ListGraph ..." << std::endl;
 
    39     std::cout << "ListGraph ..." << std::endl;
 
    43 
    40 
    44     {
 
    41     {
 
    45       std::cout << "preflow ..." << std::endl;
 
    42       std::cout << "preflow ..." << std::endl;
 
    46       ts.reset();
 
    43       ts.reset();
 
    47       pre_flow_test.run();
 
    44       max_flow_test.run();
 
    48       std::cout << "elapsed time: " << ts << std::endl;
 
    45       std::cout << "elapsed time: " << ts << std::endl;
 
    49       std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
 
    46       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    50     }
 
    47     }
 
    51 
    48 
    52     {
 
    49     {
 
    53       std::cout << "physical blocking flow augmentation ..." << std::endl;
 
    50       std::cout << "physical blocking flow augmentation ..." << std::endl;
 
    54       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
    51       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
    58       std::cout << "elapsed time: " << ts << std::endl;
 
    55       std::cout << "elapsed time: " << ts << std::endl;
 
    59       std::cout << "number of augmentation phases: " << i << std::endl; 
    56       std::cout << "number of augmentation phases: " << i << std::endl; 
    60       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    57       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    61     }
 
    58     }
 
    62 
    59 
    63     {
 
    60 //     {
 
    64       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
 
    61 //       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
 
    65       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
    62 //       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
    66       ts.reset();
 
    63 //       ts.reset();
 
    67       int i=0;
 
    64 //       int i=0;
 
    68       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
 
    65 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
 
    69       std::cout << "elapsed time: " << ts << std::endl;
 
    66 //       std::cout << "elapsed time: " << ts << std::endl;
 
    70       std::cout << "number of augmentation phases: " << i << std::endl; 
    67 //       std::cout << "number of augmentation phases: " << i << std::endl; 
    71       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    68 //       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    72     }
 
    69 //     }
 
    73 
    70 
    74     {
 
    71     {
 
    75       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
 
    72       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
 
    76       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
    73       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
    77       ts.reset();
 
    74       ts.reset();
 
   106     std::ifstream ins(in.c_str());
 
   103     std::ifstream ins(in.c_str());
 
   107     readDimacsMaxFlow(ins, G, s, t, cap);
 
   104     readDimacsMaxFlow(ins, G, s, t, cap);
 
   108 
   105 
   109     Timer ts;
 
   106     Timer ts;
 
   110     Graph::EdgeMap<int> flow(G); //0 flow
 
   107     Graph::EdgeMap<int> flow(G); //0 flow
 
   111     Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
       
   112       pre_flow_test(G, s, t, cap, flow/*, true*/);
 
       
   113     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
   108     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
   114       max_flow_test(G, s, t, cap, flow);
 
   109       max_flow_test(G, s, t, cap, flow/*, true*/);
 
       
   110     //    MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
       
   111     //  max_flow_test(G, s, t, cap, flow);
 
   115 
   112 
   116     std::cout << "SmatrGraph ..." << std::endl;
 
   113     std::cout << "SmatrGraph ..." << std::endl;
 
   117 
   114 
   118     {
 
   115     {
 
   119       std::cout << "preflow ..." << std::endl;
 
   116       std::cout << "preflow ..." << std::endl;
 
   120       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   117       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   121       ts.reset();
 
   118       ts.reset();
 
   122       pre_flow_test.run();
 
   119       max_flow_test.run();
 
   123       std::cout << "elapsed time: " << ts << std::endl;
 
   120       std::cout << "elapsed time: " << ts << std::endl;
 
   124       std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
 
   121       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   125     }
 
   122     }
 
   126 
   123 
   127     {
 
   124     {
 
   128       std::cout << "physical blocking flow augmentation ..." << std::endl;
 
   125       std::cout << "physical blocking flow augmentation ..." << std::endl;
 
   129       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   126       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   133       std::cout << "elapsed time: " << ts << std::endl;
 
   130       std::cout << "elapsed time: " << ts << std::endl;
 
   134       std::cout << "number of augmentation phases: " << i << std::endl; 
   131       std::cout << "number of augmentation phases: " << i << std::endl; 
   135       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   132       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   136     }
 
   133     }
 
   137 
   134 
   138     {
 
   135 //     {
 
   139       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
 
   136 //       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
 
   140       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   137 //       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   141       ts.reset();
 
   138 //       ts.reset();
 
   142       int i=0;
 
   139 //       int i=0;
 
   143       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
 
   140 //       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
 
   144       std::cout << "elapsed time: " << ts << std::endl;
 
   141 //       std::cout << "elapsed time: " << ts << std::endl;
 
   145       std::cout << "number of augmentation phases: " << i << std::endl; 
   142 //       std::cout << "number of augmentation phases: " << i << std::endl; 
   146       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   143 //       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   147     }
 
   144 //     }
 
   148 
   145 
   149     {
 
   146     {
 
   150       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
 
   147       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
 
   151       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   148       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   152       ts.reset();
 
   149       ts.reset();
lemon-0.x