marci@475: // -*- c++ -*- marci@475: #include marci@475: #include marci@475: marci@475: #include marci@475: #include marci@475: #include marci@475: #include marci@475: //#include marci@480: #include marci@475: //#include marci@475: #include marci@475: marci@475: using namespace hugo; marci@475: marci@475: // Use a DIMACS max flow file as stdin. marci@475: // read_dimacs_demo < dimacs_max_flow_file marci@475: marci@475: marci@475: // struct Ize { marci@475: // }; marci@475: marci@475: // struct Mize { marci@475: // Ize bumm; marci@475: // }; marci@475: marci@475: // template marci@475: // class Huha { marci@475: // public: marci@475: // int u; marci@475: // B brr; marci@475: // }; marci@475: marci@475: marci@475: int main(int, char **) { marci@475: marci@475: typedef ListGraph MutableGraph; marci@475: marci@475: typedef SmartGraph Graph; marci@475: // typedef ListGraph Graph; marci@475: typedef Graph::Node Node; marci@475: typedef Graph::EdgeIt EdgeIt; marci@475: marci@475: marci@475: // Mize mize[10]; marci@475: // Mize bize[0]; marci@475: // Mize zize; marci@475: // typedef Mize Tize[0]; marci@475: marci@475: // std::cout << &zize << " " << sizeof(mize) << sizeof(Tize) << std::endl; marci@475: // std::cout << sizeof(bize) << std::endl; marci@475: marci@475: marci@475: // Huha k; marci@475: // std::cout << sizeof(k) << std::endl; marci@475: marci@475: marci@475: // struct Bumm { marci@475: // //int a; marci@475: // bool b; marci@475: // }; marci@475: marci@475: // std::cout << sizeof(Bumm) << std::endl; marci@475: marci@475: marci@475: Graph G; marci@475: Node s, t; marci@475: Graph::EdgeMap cap(G); marci@475: readDimacsMaxFlow(std::cin, G, s, t, cap); marci@475: Timer ts; marci@475: Graph::EdgeMap flow(G); //0 flow marci@476: MaxFlow, Graph::EdgeMap > marci@476: max_flow_test(G, s, t, cap, flow); marci@475: marci@475: { marci@475: std::cout << "preflow ..." << std::endl; marci@475: ts.reset(); marci@476: max_flow_test.run(); marci@475: std::cout << "elapsed time: " << ts << std::endl; marci@476: std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@475: } marci@475: marci@475: { marci@475: std::cout << "preflow ..." << std::endl; marci@475: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@475: ts.reset(); marci@476: max_flow_test.preflow(MaxFlow, Graph::EdgeMap >::GEN_FLOW); marci@475: std::cout << "elapsed time: " << ts << std::endl; marci@476: std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@475: } marci@475: marci@475: // { marci@475: // std::cout << "wrapped preflow ..." << std::endl; marci@475: // FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@475: // ts.reset(); marci@475: // pre_flow_res.run(); marci@475: // std::cout << "elapsed time: " << ts << std::endl; marci@475: // std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; marci@475: // } marci@475: marci@475: { marci@475: std::cout << "physical blocking flow augmentation ..." << std::endl; marci@475: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@475: ts.reset(); marci@475: int i=0; marci@476: while (max_flow_test.augmentOnBlockingFlow()) { ++i; } marci@475: std::cout << "elapsed time: " << ts << std::endl; marci@475: std::cout << "number of augmentation phases: " << i << std::endl; marci@476: std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@475: } marci@475: marci@475: // { marci@475: // std::cout << "faster physical blocking flow augmentation ..." << std::endl; marci@475: // FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@475: // ts.reset(); marci@475: // int i=0; marci@475: // while (max_flow_test.augmentOnBlockingFlow1()) { ++i; } marci@475: // std::cout << "elapsed time: " << ts << std::endl; marci@475: // std::cout << "number of augmentation phases: " << i << std::endl; marci@475: // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@475: // } marci@475: marci@475: { marci@475: std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; marci@475: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@475: ts.reset(); marci@475: int i=0; marci@476: while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } marci@475: std::cout << "elapsed time: " << ts << std::endl; marci@475: std::cout << "number of augmentation phases: " << i << std::endl; marci@476: std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@475: } marci@475: marci@475: { marci@475: std::cout << "on-the-fly shortest path augmentation ..." << std::endl; marci@475: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@475: ts.reset(); marci@475: int i=0; marci@476: while (max_flow_test.augmentOnShortestPath()) { ++i; } marci@475: std::cout << "elapsed time: " << ts << std::endl; marci@475: std::cout << "number of augmentation phases: " << i << std::endl; marci@476: std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@475: } marci@475: marci@475: marci@475: return 0; marci@475: }