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 184 08735c8704cd
parent 168 27fbd1559fb7
child 188 ad1417e74042
equal deleted inserted replaced
9:a9d9b2b4fa01 10:b50839e47a59 
       
     1 // -*- c++ -*-
 
     1 #include <iostream>
 
     2 #include <iostream>
 
     2 #include <fstream>
 
     3 #include <fstream>
 
     3 
     4 
     4 #include <list_graph.hh>
 
     5 #include <list_graph.h>
 
     5 #include <dimacs.hh>
 
     6 #include <smart_graph.h>
 
     6 #include <edmonds_karp.hh>
 
     7 #include <dimacs.h>
 
       
     8 #include <edmonds_karp.h>
 
     7 #include <time_measure.h>
 
     9 #include <time_measure.h>
 
     8 #include <graph_wrapper.h>
 
    10 #include <graph_wrapper.h>
 
     9 
    11 
    10 using namespace hugo;
 
    12 using namespace hugo;
 
    11 
    13 
    12 // Use a DIMACS max flow file as stdin.
 
    14 // Use a DIMACS max flow file as stdin.
 
    13 // read_dimacs_demo < dimacs_max_flow_file
 
    15 // read_dimacs_demo < dimacs_max_flow_file
 
    14 
    16 
    15 /*
 
    17 
    16   struct Ize {
 
    18 //   struct Ize {
 
    17   };
 
    19 //   };
 
    18   
    20   
    19   struct Mize {
 
    21 //   struct Mize {
 
    20     Ize bumm;
 
    22 //     Ize bumm;
 
    21   };
 
    23 //   };
 
    22 
    24 
    23   template <typename B>
 
    25 //   template <typename B>
 
    24     class Huha {
 
    26 //     class Huha {
 
    25     public:
 
    27 //     public:
 
    26       int u;
 
    28 //       int u;
 
    27       B brr;
 
    29 //       B brr;
 
    28     };
 
    30 //     };
 
    29 */
 
    31 
    30 
    32 
    31 int main(int, char **) {
 
    33 int main(int, char **) {
 
    32   typedef ListGraph::NodeIt NodeIt;
 
       
    33   typedef ListGraph::EachEdgeIt EachEdgeIt;
 
       
    34 
    34 
    35 /*
 
    35   typedef ListGraph MutableGraph;
 
    36   Mize mize[10];
 
       
    37   Mize bize[0];
 
       
    38   Mize zize;
 
       
    39   typedef Mize Tize[0];
 
       
    40 
    36 
    41   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
 
    37   typedef SmartGraph Graph;
 
    42   std::cout << sizeof(bize) << std::endl;
 
    38   typedef Graph::Node Node;
 
       
    39   typedef Graph::EdgeIt EdgeIt;
 
    43 
    40 
    44 
    41 
    45   Huha<Tize> k;
 
    42 //   Mize mize[10];
 
    46   std::cout << sizeof(k) << std::endl;
 
    43 //   Mize bize[0];
 
       
    44 //   Mize zize;
 
       
    45 //   typedef Mize Tize[0];
 
       
    46 
       
    47 //   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
 
       
    48 //   std::cout << sizeof(bize) << std::endl;
 
    47 
    49 
    48 
    50 
    49   struct Bumm {
 
    51 //   Huha<Tize> k;
 
    50     //int a;
 
    52 //   std::cout << sizeof(k) << std::endl;
 
    51     bool b;
 
       
    52   };
 
       
    53 
    53 
    54   std::cout << sizeof(Bumm) << std::endl;
 
       
    55 */
 
       
    56 
    54 
    57   ListGraph G;
 
    55 //   struct Bumm {
 
    58   NodeIt s, t;
 
    56 //     //int a;
 
    59   ListGraph::EdgeMap<int> cap(G);
 
    57 //     bool b;
 
       
    58 //   };
 
       
    59 
       
    60 //   std::cout << sizeof(Bumm) << std::endl;
 
       
    61 
       
    62 
       
    63   Graph G;
 
       
    64   Node s, t;
 
       
    65   Graph::EdgeMap<int> cap(G);
 
    60   readDimacsMaxFlow(std::cin, G, s, t, cap);
 
    66   readDimacsMaxFlow(std::cin, G, s, t, cap);
 
    61 /*
 
       
    62   typedef TrivGraphWrapper<ListGraph> TGW;
 
       
    63   TGW gw(G);
 
       
    64   TGW::EachNodeIt sw;
 
       
    65   gw.getFirst(sw);
 
       
    66   std::cout << "p1:" << gw.nodeNum() << std::endl;
 
       
    67   gw.erase(sw);
 
       
    68   std::cout << "p2:" << gw.nodeNum() << std::endl;
 
       
    69 
    67 
    70   typedef const ListGraph cLG;
 
    68 //   typedef TrivGraphWrapper<Graph> TGW;
 
    71   typedef TrivGraphWrapper<const cLG> CTGW;
 
    69 //   TGW gw(G);
 
    72   CTGW cgw(G);
 
    70 //   TGW::NodeIt sw;
 
    73   CTGW::EachNodeIt csw;
 
    71 //   gw./*getF*/first(sw);
 
    74   cgw.getFirst(csw);
 
    72 //   std::cout << "p1:" << gw.nodeNum() << std::endl;
 
    75   std::cout << "p1:" << cgw.nodeNum() << std::endl;
 
    73 //   gw.erase(sw);
 
    76   //cgw.erase(csw);
 
    74 //   std::cout << "p2:" << gw.nodeNum() << std::endl;
 
    77   std::cout << "p2:" << cgw.nodeNum() << std::endl;
 
    75 
    78 */
 
    76 //   typedef const Graph cLG;
 
       
    77 //   typedef TrivGraphWrapper<const cLG> CTGW;
 
       
    78 //   CTGW cgw(G);
 
       
    79 //   CTGW::NodeIt csw;
 
       
    80 //   cgw./*getF*/first(csw);
 
       
    81 //   std::cout << "p1:" << cgw.nodeNum() << std::endl;
 
       
    82 //   //cgw.erase(csw);
 
       
    83 //   std::cout << "p2:" << cgw.nodeNum() << std::endl;
 
       
    84 
    79 
    85 
    80   {
 
    86   {
 
    81   std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
 
    87     std::cout << "SmartGraph..." << std::endl;
 
    82   ListGraph::EdgeMap<int> flow(G); //0 flow
 
    88     std::cout << "edmonds karp demo (physical blocking flow augmentation)..." << std::endl;
 
       
    89     Graph::EdgeMap<int> flow(G); //0 flow
 
    83 
    90 
    84   Timer ts;
 
    91     Timer ts;
 
    85   ts.reset();
 
    92     ts.reset();
 
    86   //double pre_time=currTime();
 
    93 
    87   MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
 
    94     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
 
    88   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
 
    95     //max_flow_test.augmentWithBlockingFlow<Graph>();
 
    89   int i=0;
 
    96     int i=0;
 
    90   while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { 
    97     while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { 
    91 //     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
    98 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
    92 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
    99 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
    93 //     }
 
   100 //     }
 
    94 //     std::cout<<std::endl;
 
   101 //     std::cout<<std::endl;
 
    95     ++i; 
   102       ++i; 
    96   }
 
   103     }
 
    97   //double post_time=currTime();
 
       
    98 
   104 
    99   //std::cout << "maximum flow: "<< std::endl;
 
   105 //   std::cout << "maximum flow: "<< std::endl;
 
   100   //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 
   106 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
   101   //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
   107 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
   102   //}
 
   108 //   }
 
   103   //std::cout<<std::endl;
 
   109 //   std::cout<<std::endl;
 
   104   std::cout << "elapsed time: " << ts << std::endl;
 
   110     std::cout << "elapsed time: " << ts << std::endl;
 
   105   std::cout << "number of augmentation phases: " << i << std::endl; 
   111     std::cout << "number of augmentation phases: " << i << std::endl; 
   106   std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   112     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   107   }
 
   113   }
 
   108 
   114 
   109   {
 
   115   {
 
   110   std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
 
   116     std::cout << "edmonds karp demo (on-the-fly blocking flow augmentation)..." << std::endl;
 
   111   ListGraph::EdgeMap<int> flow(G); //0 flow
 
   117     Graph::EdgeMap<int> flow(G); //0 flow
 
   112 
   118 
   113   Timer ts;
 
   119     Timer ts;
 
   114   ts.reset();
 
   120     ts.reset();
 
   115   //double pre_time=currTime();
 
   121 
   116   MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
 
   122     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
 
   117   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
 
   123     //max_flow_test.augmentWithBlockingFlow<Graph>();
 
   118   int i=0;
 
   124     int i=0;
 
   119   while (max_flow_test.augmentOnBlockingFlow2()) { 
   125     while (max_flow_test.augmentOnBlockingFlow2()) { 
   120 //     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
   126 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
   121 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
   127 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
   122 //     }
 
   128 //     }
 
   123 //     std::cout<<std::endl;
 
   129 //     std::cout<<std::endl;
 
   124     ++i; 
   130       ++i; 
   125   }
 
   131     }
 
   126   //double post_time=currTime();
 
       
   127 
   132 
   128   //std::cout << "maximum flow: "<< std::endl;
 
   133 //   std::cout << "maximum flow: "<< std::endl;
 
   129   //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 
   134 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
   130   //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
   135 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
   131   //}
 
   136 //   }
 
   132   //std::cout<<std::endl;
 
   137 //   std::cout<<std::endl;
 
   133   std::cout << "elapsed time: " << ts << std::endl;
 
   138     std::cout << "elapsed time: " << ts << std::endl;
 
   134   std::cout << "number of augmentation phases: " << i << std::endl; 
   139     std::cout << "number of augmentation phases: " << i << std::endl; 
   135   std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   140     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   136   }
 
   141   }
 
   137 
   142 
   138   {
 
   143   {
 
   139   std::cout << "edmonds karp demo (shortest path augmentation)..." << std::endl;
 
   144     std::cout << "edmonds karp demo (on-the-fly shortest path augmentation)..." << std::endl;
 
   140   ListGraph::EdgeMap<int> flow(G); //0 flow
 
   145     Graph::EdgeMap<int> flow(G); //0 flow
 
   141 
   146 
   142   Timer ts;
 
   147     Timer ts;
 
   143   ts.reset();
 
   148     ts.reset();
 
   144   //double pre_time=currTime();
 
   149 
   145   MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
 
   150     MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
 
   146   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
 
   151     //max_flow_test.augmentWithBlockingFlow<Graph>();
 
   147   int i=0;
 
   152     int i=0;
 
   148   while (max_flow_test.augmentOnShortestPath()) { 
   153     while (max_flow_test.augmentOnShortestPath()) { 
   149 //     for(EachEdgeIt e=G.template first<EachEdgeIt>(); e.valid(); ++e) { 
   154 //     for(EdgeIt e=G.template first<EdgeIt>(); e.valid(); ++e) { 
   150 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
   155 //       std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
   151 //     }
 
   156 //     }
 
   152 //     std::cout<<std::endl;
 
   157 //     std::cout<<std::endl;
 
   153     ++i; 
   158       ++i; 
       
   159     }
 
       
   160 
       
   161 //   std::cout << "maximum flow: "<< std::endl;
 
       
   162 //   for(EdgeIt e=G.first<EdgeIt>(); e.valid(); ++e) { 
       
   163 //     std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
       
   164 //   }
 
       
   165 //   std::cout<<std::endl;
 
       
   166     std::cout << "elapsed time: " << ts << std::endl;
 
       
   167     std::cout << "number of augmentation phases: " << i << std::endl; 
       
   168     std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
   154   }
 
   169   }
 
   155   //double post_time=currTime();
 
       
   156 
   170 
   157   //std::cout << "maximum flow: "<< std::endl;
 
       
   158   //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 
       
   159   //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
 
       
   160   //}
 
       
   161   //std::cout<<std::endl;
 
       
   162   std::cout << "elapsed time: " << ts << std::endl;
 
       
   163   std::cout << "number of augmentation phases: " << i << std::endl; 
       
   164   std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
 
       
   165   }
 
       
   166 
   171 
   167   return 0;
 
   172   return 0;
 
   168 }
 
   173 }
lemon-0.x