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 349 42c660f58702
parent 174 44700ed9ffaa
child 379 a5bff2813c4d
equal deleted inserted replaced
0:de6c40a35bf6 1:0ba3299dcfd4 
     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>
 
     9 #include <edmonds_karp.h>
 
       
    10 #include <preflow.h>
 
    10 #include <time_measure.h>
 
    11 #include <time_measure.h>
 
    11 #include <graph_wrapper.h>
 
    12 #include <for_each_macros.h>
 
    12 
    13 
    13 using namespace hugo;
 
    14 using namespace hugo;
 
    14 
    15 
    15 // Use a DIMACS max flow file as stdin.
 
    16 // Use a DIMACS max flow file as stdin.
 
    16 // read_dimacs_demo dimacs_max_flow_file
 
    17 // read_dimacs_demo dimacs_max_flow_file
 
    29     Node s, t;
 
    30     Node s, t;
 
    30     Graph::EdgeMap<int> cap(G);
 
    31     Graph::EdgeMap<int> cap(G);
 
    31     std::ifstream ins(in.c_str());
 
    32     std::ifstream ins(in.c_str());
 
    32     readDimacsMaxFlow(ins, G, s, t, cap);
 
    33     readDimacsMaxFlow(ins, G, s, t, cap);
 
    33 
    34 
       
    35     Timer ts;
 
       
    36     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);
 
       
    39     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
       
    40       max_flow_test(G, s, t, cap, flow);
 
       
    41 
       
    42     std::cout << "ListGraph ..." << std::endl;
 
       
    43 
    34     {
 
    44     {
 
    35       std::cout << "ListGraph..." << std::endl;
 
    45       std::cout << "preflow ..." << std::endl;
 
    36       std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
 
    46       ts.reset();
 
    37       Graph::EdgeMap<int> flow(G); //0 flow
 
    47       pre_flow_test.run();
 
       
    48       std::cout << "elapsed time: " << ts << std::endl;
 
       
    49       std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
 
       
    50     }
 
    38 
    51 
    39       Timer ts;
 
    52     {
 
       
    53       std::cout << "physical blocking flow augmentation ..." << std::endl;
 
       
    54       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
    40       ts.reset();
 
    55       ts.reset();
 
    41 
       
    42       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
 
       
    43       int i=0;
 
    56       int i=0;
 
    44       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
 
    57       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
 
    45 
       
    46       std::cout << "elapsed time: " << ts << std::endl;
 
    58       std::cout << "elapsed time: " << ts << std::endl;
 
    47       std::cout << "number of augmentation phases: " << i << std::endl; 
    59       std::cout << "number of augmentation phases: " << i << std::endl; 
    48       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    60       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    49     }
 
    61     }
 
    50 
    62 
    51     {
 
    63     {
 
    52       std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
 
    64       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
 
    53       Graph::EdgeMap<int> flow(G); //0 flow
 
    65       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
    54 
       
    55       Timer ts;
 
       
    56       ts.reset();
 
    66       ts.reset();
 
    57 
       
    58       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
 
       
    59       int i=0;
 
    67       int i=0;
 
    60       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
 
    68       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
 
    61 
       
    62       std::cout << "elapsed time: " << ts << std::endl;
 
    69       std::cout << "elapsed time: " << ts << std::endl;
 
    63       std::cout << "number of augmentation phases: " << i << std::endl; 
    70       std::cout << "number of augmentation phases: " << i << std::endl; 
    64       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    71       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    65     }
 
    72     }
 
    66 
    73 
    67     {
 
    74     {
 
    68       std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
 
    75       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
 
    69       Graph::EdgeMap<int> flow(G); //0 flow
 
    76       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
       
    77       ts.reset();
 
       
    78       int i=0;
 
       
    79       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
 
       
    80       std::cout << "elapsed time: " << ts << std::endl;
 
       
    81       std::cout << "number of augmentation phases: " << i << std::endl; 
       
    82       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
       
    83     }
 
    70 
    84 
    71       Timer ts;
 
    85     {
 
       
    86       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
 
       
    87       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
    72       ts.reset();
 
    88       ts.reset();
 
    73 
       
    74       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
 
       
    75       int i=0;
 
    89       int i=0;
 
    76       while (max_flow_test.augmentOnShortestPath()) { ++i; }
 
    90       while (max_flow_test.augmentOnShortestPath()) { ++i; }
 
    77 
       
    78       std::cout << "elapsed time: " << ts << std::endl;
 
    91       std::cout << "elapsed time: " << ts << std::endl;
 
    79       std::cout << "number of augmentation phases: " << i << std::endl; 
    92       std::cout << "number of augmentation phases: " << i << std::endl; 
    80       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    93       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    81     }
 
    94     }
 
    82   }
 
    95   }
 
    91     Node s, t;
 
   104     Node s, t;
 
    92     Graph::EdgeMap<int> cap(G);
 
   105     Graph::EdgeMap<int> cap(G);
 
    93     std::ifstream ins(in.c_str());
 
   106     std::ifstream ins(in.c_str());
 
    94     readDimacsMaxFlow(ins, G, s, t, cap);
 
   107     readDimacsMaxFlow(ins, G, s, t, cap);
 
    95 
   108 
       
   109     Timer ts;
 
       
   110     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);
 
       
   113     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
       
   114       max_flow_test(G, s, t, cap, flow);
 
       
   115 
       
   116     std::cout << "SmatrGraph ..." << std::endl;
 
       
   117 
    96     {
 
   118     {
 
    97       std::cout << "SmartGraph..." << std::endl;
 
   119       std::cout << "preflow ..." << std::endl;
 
    98       std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
 
   120       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
    99       Graph::EdgeMap<int> flow(G); //0 flow
 
   121       ts.reset();
 
       
   122       pre_flow_test.run();
 
       
   123       std::cout << "elapsed time: " << ts << std::endl;
 
       
   124       std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
 
       
   125     }
 
   100 
   126 
   101       Timer ts;
 
   127     {
 
       
   128       std::cout << "physical blocking flow augmentation ..." << std::endl;
 
       
   129       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   102       ts.reset();
 
   130       ts.reset();
 
   103 
       
   104       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
 
       
   105       int i=0;
 
   131       int i=0;
 
   106       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
 
   132       while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
 
   107 
       
   108       std::cout << "elapsed time: " << ts << std::endl;
 
   133       std::cout << "elapsed time: " << ts << std::endl;
 
   109       std::cout << "number of augmentation phases: " << i << std::endl; 
   134       std::cout << "number of augmentation phases: " << i << std::endl; 
   110       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   135       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   111     }
 
   136     }
 
   112 
   137 
   113     {
 
   138     {
 
   114       std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
 
   139       std::cout << "faster physical blocking flow augmentation ..." << std::endl;
 
   115       Graph::EdgeMap<int> flow(G); //0 flow
 
   140       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   116 
       
   117       Timer ts;
 
       
   118       ts.reset();
 
   141       ts.reset();
 
   119 
       
   120       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
 
       
   121       int i=0;
 
   142       int i=0;
 
   122       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
 
   143       while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
 
   123 
       
   124       std::cout << "elapsed time: " << ts << std::endl;
 
   144       std::cout << "elapsed time: " << ts << std::endl;
 
   125       std::cout << "number of augmentation phases: " << i << std::endl; 
   145       std::cout << "number of augmentation phases: " << i << std::endl; 
   126       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   146       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   127     }
 
   147     }
 
   128 
   148 
   129     {
 
   149     {
 
   130       std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
 
   150       std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
 
   131       Graph::EdgeMap<int> flow(G); //0 flow
 
   151       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
       
   152       ts.reset();
 
       
   153       int i=0;
 
       
   154       while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
 
       
   155       std::cout << "elapsed time: " << ts << std::endl;
 
       
   156       std::cout << "number of augmentation phases: " << i << std::endl; 
       
   157       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
       
   158     }
 
   132 
   159 
   133       Timer ts;
 
   160     {
 
       
   161       std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
 
       
   162       FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   134       ts.reset();
 
   163       ts.reset();
 
   135 
       
   136       MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
 
       
   137       int i=0;
 
   164       int i=0;
 
   138       while (max_flow_test.augmentOnShortestPath()) { ++i; }
 
   165       while (max_flow_test.augmentOnShortestPath()) { ++i; }
 
   139 
       
   140       std::cout << "elapsed time: " << ts << std::endl;
 
   166       std::cout << "elapsed time: " << ts << std::endl;
 
   141       std::cout << "number of augmentation phases: " << i << std::endl; 
   167       std::cout << "number of augmentation phases: " << i << std::endl; 
   142       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   168       std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   143     }
 
   169     }
 
   144   }
 
   170   }
 
   145 
   171 
       
   172 
       
   173 
       
   174 
   146   return 0;
 
   175   return 0;
 
   147 }
 
   176 }
lemon-0.x