Mercuriallemon-0.x / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
src/work/marci/edmonds_karp_demo.cc
changeset 351 01fb9da7a363
parent 330 7ac0d4e8a31c
child 376 5c12f3515452
equal deleted inserted replaced
23:c25d3f91f2db 24:9cee39e0e72b 
     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 <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
 
    64 
    65 
    65   Graph G;
 
    66   Graph G;
 
    66   Node s, t;
 
    67   Node s, t;
 
    67   Graph::EdgeMap<int> cap(G);
 
    68   Graph::EdgeMap<int> cap(G);
 
    68   readDimacsMaxFlow(std::cin, G, s, t, cap);
 
    69   readDimacsMaxFlow(std::cin, G, s, t, cap);
 
       
    70   Timer ts;
 
       
    71   Graph::EdgeMap<int> flow(G); //0 flow
 
       
    72   Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
       
    73     pre_flow_test(G, s, t, cap, flow);
 
       
    74   MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
       
    75     max_flow_test(G, s, t, cap, flow);
 
    69 
    76 
    70   {
 
    77   {
 
    71     std::cout << "preflow ..." << std::endl;
 
    78     std::cout << "preflow ..." << std::endl;
 
    72     Graph::EdgeMap<int> flow(G); //0 flow
 
       
    73 
       
    74     Timer ts;
 
       
    75     ts.reset();
 
    79     ts.reset();
 
    76 
    80     pre_flow_test.run();
 
    77     Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
       
    78       max_flow_test(G, s, t, cap, flow);
 
       
    79     max_flow_test.run();
 
       
    80 //    int i=0;
 
       
    81 //    while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 
       
    82 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
       
    83 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
       
    84 //     }
 
       
    85 //     std::cout<<std::endl;
 
       
    86 //      ++i; 
       
    87 //    }
 
       
    88 
       
    89 //   std::cout << "maximum flow: "<< std::endl;
 
       
    90 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
       
    91 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
       
    92 //   }
 
       
    93 //   std::cout<<std::endl;
 
       
    94     std::cout << "elapsed time: " << ts << std::endl;
 
    81     std::cout << "elapsed time: " << ts << std::endl;
 
    95 //    std::cout << "number of augmentation phases: " << i << std::endl; 
    82     std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl;
 
    96     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
       
    97   }
 
    83   }
 
    98 
    84 
    99   {
 
    85   {
 
   100     std::cout << "physical blocking flow augmentation ..." << std::endl;
 
    86     std::cout << "physical blocking flow augmentation ..." << std::endl;
 
   101     Graph::EdgeMap<int> flow(G); //0 flow
 
    87     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   102 
       
   103     Timer ts;
 
       
   104     ts.reset();
 
    88     ts.reset();
 
   105 
       
   106     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
       
   107       max_flow_test(G, s, t, cap, flow);
 
       
   108     int i=0;
 
    89     int i=0;
 
   109     while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 
    90     while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
 
   110 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
       
   111 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
       
   112 //     }
 
       
   113 //     std::cout<<std::endl;
 
       
   114       ++i; 
       
   115     }
 
       
   116 
       
   117 //   std::cout << "maximum flow: "<< std::endl;
 
       
   118 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
       
   119 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
       
   120 //   }
 
       
   121 //   std::cout<<std::endl;
 
       
   122     std::cout << "elapsed time: " << ts << std::endl;
 
    91     std::cout << "elapsed time: " << ts << std::endl;
 
   123     std::cout << "number of augmentation phases: " << i << std::endl; 
    92     std::cout << "number of augmentation phases: " << i << std::endl; 
   124     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
    93     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   125   }
 
    94   }
 
   126 
    95 
   127   {
 
    96   {
 
   128     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
 
    97     std::cout << "faster physical blocking flow augmentation ..." << std::endl;
 
   129     Graph::EdgeMap<int> flow(G); //0 flow
 
    98     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   130 
       
   131     Timer ts;
 
       
   132     ts.reset();
 
    99     ts.reset();
 
   133 
       
   134     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
       
   135       max_flow_test(G, s, t, cap, flow);
 
       
   136     int i=0;
 
   100     int i=0;
 
   137     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { 
   101     while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
 
   138 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
       
   139 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
       
   140 //     }
 
       
   141 //     std::cout<<std::endl;
 
       
   142       ++i; 
       
   143     }
 
       
   144 
       
   145 //   std::cout << "maximum flow: "<< std::endl;
 
       
   146 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
       
   147 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
       
   148 //   }
 
       
   149 //   std::cout<<std::endl;
 
       
   150     std::cout << "elapsed time: " << ts << std::endl;
 
   102     std::cout << "elapsed time: " << ts << std::endl;
 
   151     std::cout << "number of augmentation phases: " << i << std::endl; 
   103     std::cout << "number of augmentation phases: " << i << std::endl; 
   152     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   104     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   153   }
 
   105   }
 
   154 
   106 
   155   {
 
   107   {
 
   156     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
 
   108     std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
 
   157     Graph::EdgeMap<int> flow(G); //0 flow
 
   109     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   158 
       
   159     Timer ts;
 
       
   160     ts.reset();
 
   110     ts.reset();
 
   161 
       
   162     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
       
   163       max_flow_test(G, s, t, cap, flow);
 
       
   164     int i=0;
 
   111     int i=0;
 
   165     while (max_flow_test.augmentOnBlockingFlow2()) { 
   112     while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
 
   166 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
       
   167 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
       
   168 //     }
 
       
   169 //     std::cout<<std::endl;
 
       
   170       ++i; 
       
   171     }
 
       
   172 
       
   173 //   std::cout << "maximum flow: "<< std::endl;
 
       
   174 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
       
   175 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
       
   176 //   }
 
       
   177 //   std::cout<<std::endl;
 
       
   178     std::cout << "elapsed time: " << ts << std::endl;
 
   113     std::cout << "elapsed time: " << ts << std::endl;
 
   179     std::cout << "number of augmentation phases: " << i << std::endl; 
   114     std::cout << "number of augmentation phases: " << i << std::endl; 
   180     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   115     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   181   }
 
   116   }
 
   182 
   117 
   183   {
 
   118   {
 
   184     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
 
   119     std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
 
   185     Graph::EdgeMap<int> flow(G); //0 flow
 
   120     FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
 
   186 
       
   187     Timer ts;
 
       
   188     ts.reset();
 
   121     ts.reset();
 
   189 
       
   190     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > 
       
   191       max_flow_test(G, s, t, cap, flow);
 
       
   192     int i=0;
 
   122     int i=0;
 
   193     while (max_flow_test.augmentOnShortestPath()) { 
   123     while (max_flow_test.augmentOnShortestPath()) { ++i; }
 
   194 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
       
   195 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
       
   196 //     }
 
       
   197 //     std::cout<<std::endl;
 
       
   198       ++i; 
       
   199     }
 
       
   200 
       
   201 //   std::cout << "maximum flow: "<< std::endl;
 
       
   202 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
       
   203 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
       
   204 //   }
 
       
   205 //   std::cout<<std::endl;
 
       
   206     std::cout << "elapsed time: " << ts << std::endl;
 
   124     std::cout << "elapsed time: " << ts << std::endl;
 
   207     std::cout << "number of augmentation phases: " << i << std::endl; 
   125     std::cout << "number of augmentation phases: " << i << std::endl; 
   208     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   126     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   209   }
 
   127   }
 
   210 
   128
lemon-0.x