marci@73: #include <iostream>
marci@73: #include <fstream>
marci@73: 
marci@73: #include <list_graph.hh>
marci@73: #include <dimacs.hh>
marci@73: #include <edmonds_karp.hh>
marci@73: #include <time_measure.h>
marci@155: #include <graph_wrapper.h>
marci@73: 
alpar@105: using namespace hugo;
marci@73: 
marci@73: // Use a DIMACS max flow file as stdin.
marci@73: // read_dimacs_demo < dimacs_max_flow_file
marci@139: 
marci@139: /*
marci@139:   struct Ize {
marci@139:   };
marci@139:   
marci@139:   struct Mize {
marci@139:     Ize bumm;
marci@139:   };
marci@139: 
marci@139:   template <typename B>
marci@139:     class Huha {
marci@139:     public:
marci@139:       int u;
marci@139:       B brr;
marci@139:     };
marci@139: */
marci@139: 
marci@73: int main(int, char **) {
marci@73:   typedef ListGraph::NodeIt NodeIt;
marci@73:   typedef ListGraph::EachEdgeIt EachEdgeIt;
marci@73: 
marci@139: /*
marci@139:   Mize mize[10];
marci@139:   Mize bize[0];
marci@139:   Mize zize;
marci@139:   typedef Mize Tize[0];
marci@139: 
marci@139:   std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl;
marci@139:   std::cout << sizeof(bize) << std::endl;
marci@139: 
marci@139: 
marci@139:   Huha<Tize> k;
marci@139:   std::cout << sizeof(k) << std::endl;
marci@146: 
marci@146: 
marci@146:   struct Bumm {
marci@146:     //int a;
marci@146:     bool b;
marci@146:   };
marci@146: 
marci@146:   std::cout << sizeof(Bumm) << std::endl;
marci@139: */
marci@139: 
marci@73:   ListGraph G;
marci@73:   NodeIt s, t;
marci@73:   ListGraph::EdgeMap<int> cap(G);
marci@73:   readDimacsMaxFlow(std::cin, G, s, t, cap);
marci@155: /*
marci@155:   typedef TrivGraphWrapper<ListGraph> TGW;
marci@155:   TGW gw(G);
marci@155:   TGW::EachNodeIt sw;
marci@155:   gw.getFirst(sw);
marci@155:   std::cout << "p1:" << gw.nodeNum() << std::endl;
marci@155:   gw.erase(sw);
marci@155:   std::cout << "p2:" << gw.nodeNum() << std::endl;
marci@155: 
marci@155:   typedef const ListGraph cLG;
marci@155:   typedef TrivGraphWrapper<const cLG> CTGW;
marci@155:   CTGW cgw(G);
marci@155:   CTGW::EachNodeIt csw;
marci@155:   cgw.getFirst(csw);
marci@155:   std::cout << "p1:" << cgw.nodeNum() << std::endl;
marci@155:   //cgw.erase(csw);
marci@155:   std::cout << "p2:" << cgw.nodeNum() << std::endl;
marci@155: */
marci@73: 
marci@133:   {
marci@133:   std::cout << "edmonds karp demo (blocking flow augmentation)..." << std::endl;
marci@73:   ListGraph::EdgeMap<int> flow(G); //0 flow
marci@73: 
marci@144:   Timer ts;
marci@144:   ts.reset();
marci@144:   //double pre_time=currTime();
marci@73:   MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
marci@133:   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
marci@138:   int i=0;
marci@138:   while (max_flow_test.augmentOnBlockingFlow<ListGraph>()) { ++i; }
marci@144:   //double post_time=currTime();
marci@133: 
marci@73:   //std::cout << "maximum flow: "<< std::endl;
marci@73:   //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 
marci@73:   //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
marci@73:   //}
marci@73:   //std::cout<<std::endl;
marci@144:   std::cout << "elapsed time: " << ts << std::endl;
marci@138:   std::cout << "number of augmentation phases: " << i << std::endl; 
marci@73:   std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@133:   }
marci@133: 
marci@133:   {
marci@133:   std::cout << "edmonds karp demo (shortest path augmentation)..." << std::endl;
marci@133:   ListGraph::EdgeMap<int> flow(G); //0 flow
marci@133: 
marci@144:   Timer ts;
marci@144:   ts.reset();
marci@144:   //double pre_time=currTime();
marci@133:   MaxFlow<ListGraph, int, ListGraph::EdgeMap<int>, ListGraph::EdgeMap<int> > max_flow_test(G, s, t, flow, cap);
marci@133:   //max_flow_test.augmentWithBlockingFlow<ListGraph>();
marci@138:   int i=0;
marci@138:   while (max_flow_test.augmentOnShortestPath()) { ++i; }
marci@144:   //double post_time=currTime();
marci@133: 
marci@133:   //std::cout << "maximum flow: "<< std::endl;
marci@133:   //for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) { 
marci@133:   //  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
marci@133:   //}
marci@133:   //std::cout<<std::endl;
marci@144:   std::cout << "elapsed time: " << ts << std::endl;
marci@138:   std::cout << "number of augmentation phases: " << i << std::endl; 
marci@133:   std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
marci@133:   }
marci@73: 
marci@73:   return 0;
marci@73: }