marci@174: // -*- c++ -*- marci@73: #include marci@73: #include marci@73: marci@174: #include marci@415: #include marci@174: #include marci@174: #include marci@73: #include marci@303: //#include marci@311: #include marci@390: #include marci@333: #include marci@266: 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@174: marci@174: // struct Ize { marci@174: // }; marci@139: marci@174: // struct Mize { marci@174: // Ize bumm; marci@174: // }; marci@139: marci@174: // template marci@174: // class Huha { marci@174: // public: marci@174: // int u; marci@174: // B brr; marci@174: // }; marci@174: marci@139: marci@73: int main(int, char **) { marci@73: marci@174: typedef ListGraph MutableGraph; marci@139: marci@415: typedef SmartGraph Graph; marci@415: // typedef ListGraph Graph; marci@174: typedef Graph::Node Node; marci@174: typedef Graph::EdgeIt EdgeIt; marci@139: marci@139: marci@174: // Mize mize[10]; marci@174: // Mize bize[0]; marci@174: // Mize zize; marci@174: // typedef Mize Tize[0]; marci@146: marci@174: // std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl; marci@174: // std::cout << sizeof(bize) << std::endl; marci@146: marci@146: marci@174: // Huha k; marci@174: // std::cout << sizeof(k) << std::endl; marci@139: marci@174: marci@174: // struct Bumm { marci@174: // //int a; marci@174: // bool b; marci@174: // }; marci@174: marci@174: // std::cout << sizeof(Bumm) << std::endl; marci@174: marci@174: marci@174: Graph G; marci@174: Node s, t; marci@174: Graph::EdgeMap cap(G); marci@73: readDimacsMaxFlow(std::cin, G, s, t, cap); marci@333: Timer ts; marci@333: Graph::EdgeMap flow(G); //0 flow marci@333: Preflow, Graph::EdgeMap > marci@376: pre_flow_test(G, s, t, cap, flow, true); marci@418: Preflow, Graph::EdgeMap > marci@418: pre_flow_ize(G, s, t, cap, flow, false); marci@390: PreflowRes, Graph::EdgeMap > marci@390: pre_flow_res(G, s, t, cap, flow, true); marci@333: MaxFlow, Graph::EdgeMap > marci@333: max_flow_test(G, s, t, cap, flow); marci@155: marci@311: { marci@311: std::cout << "preflow ..." << std::endl; marci@311: ts.reset(); marci@333: pre_flow_test.run(); marci@311: std::cout << "elapsed time: " << ts << std::endl; marci@333: std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; marci@311: } marci@73: marci@133: { marci@418: std::cout << "preflow ..." << std::endl; marci@418: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@418: ts.reset(); marci@418: pre_flow_ize.run(); marci@418: std::cout << "elapsed time: " << ts << std::endl; marci@418: std::cout << "flow value: "<< pre_flow_ize.flowValue() << std::endl; marci@418: } marci@418: marci@418: { marci@376: std::cout << "wrapped preflow ..." << std::endl; marci@376: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@376: ts.reset(); marci@390: pre_flow_res.run(); marci@376: std::cout << "elapsed time: " << ts << std::endl; marci@376: std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; marci@376: } marci@376: marci@376: { marci@311: std::cout << "physical blocking flow augmentation ..." << std::endl; marci@333: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@174: ts.reset(); marci@174: int i=0; marci@333: while (max_flow_test.augmentOnBlockingFlow()) { ++i; } marci@174: std::cout << "elapsed time: " << ts << std::endl; marci@174: std::cout << "number of augmentation phases: " << i << std::endl; marci@174: std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@168: } marci@168: marci@268: { marci@311: std::cout << "faster physical blocking flow augmentation ..." << std::endl; marci@333: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@268: ts.reset(); marci@268: int i=0; marci@333: while (max_flow_test.augmentOnBlockingFlow1()) { ++i; } marci@268: std::cout << "elapsed time: " << ts << std::endl; marci@268: std::cout << "number of augmentation phases: " << i << std::endl; marci@268: std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@268: } marci@266: marci@269: { marci@311: std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; marci@333: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@269: ts.reset(); marci@269: int i=0; marci@333: while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } marci@269: std::cout << "elapsed time: " << ts << std::endl; marci@269: std::cout << "number of augmentation phases: " << i << std::endl; marci@269: std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@269: } marci@266: marci@168: { marci@311: std::cout << "on-the-fly shortest path augmentation ..." << std::endl; marci@333: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@206: ts.reset(); marci@174: int i=0; marci@333: while (max_flow_test.augmentOnShortestPath()) { ++i; } marci@174: std::cout << "elapsed time: " << ts << std::endl; marci@174: std::cout << "number of augmentation phases: " << i << std::endl; marci@174: std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@168: } marci@133: marci@73: marci@73: return 0; marci@73: }