marci@174: // -*- c++ -*- marci@174: #include marci@174: #include marci@174: #include marci@174: marci@174: #include marci@174: #include marci@174: #include marci@480: #include marci@174: #include marci@334: #include marci@174: marci@174: using namespace hugo; marci@174: marci@174: // Use a DIMACS max flow file as stdin. marci@174: // read_dimacs_demo dimacs_max_flow_file marci@174: marci@174: int main(int, char** argv) { marci@174: marci@174: std::string in=argv[1]; marci@174: typedef ListGraph MutableGraph; marci@174: marci@174: { marci@174: typedef ListGraph Graph; marci@174: typedef Graph::Node Node; marci@174: typedef Graph::EdgeIt EdgeIt; marci@174: marci@174: Graph G; marci@174: Node s, t; marci@174: Graph::EdgeMap cap(G); marci@174: std::ifstream ins(in.c_str()); marci@174: readDimacsMaxFlow(ins, G, s, t, cap); marci@174: marci@334: Timer ts; marci@334: Graph::EdgeMap flow(G); //0 flow marci@334: MaxFlow, Graph::EdgeMap > marci@476: max_flow_test(G, s, t, cap, flow/*, true*/); marci@334: marci@334: std::cout << "ListGraph ..." << std::endl; marci@334: marci@174: { marci@334: std::cout << "preflow ..." << std::endl; marci@334: ts.reset(); marci@476: max_flow_test.run(); marci@334: std::cout << "elapsed time: " << ts << std::endl; marci@476: std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@334: } marci@174: marci@334: { marci@334: std::cout << "physical blocking flow augmentation ..." << std::endl; marci@334: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@174: ts.reset(); marci@174: int i=0; marci@174: 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@174: } marci@174: marci@476: // { marci@476: // std::cout << "faster physical blocking flow augmentation ..." << std::endl; marci@476: // FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@476: // ts.reset(); marci@476: // int i=0; marci@476: // while (max_flow_test.augmentOnBlockingFlow1()) { ++i; } marci@476: // std::cout << "elapsed time: " << ts << std::endl; marci@476: // std::cout << "number of augmentation phases: " << i << std::endl; marci@476: // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@476: // } marci@174: marci@174: { marci@334: std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; marci@334: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@334: ts.reset(); marci@334: int i=0; marci@334: while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } marci@334: std::cout << "elapsed time: " << ts << std::endl; marci@334: std::cout << "number of augmentation phases: " << i << std::endl; marci@334: std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@334: } marci@174: marci@334: { marci@334: std::cout << "on-the-fly shortest path augmentation ..." << std::endl; marci@334: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@174: ts.reset(); marci@174: int i=0; marci@174: 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@174: } marci@174: } marci@174: marci@174: marci@174: { marci@174: typedef SmartGraph Graph; marci@174: typedef Graph::Node Node; marci@174: typedef Graph::EdgeIt EdgeIt; marci@174: marci@174: Graph G; marci@174: Node s, t; marci@174: Graph::EdgeMap cap(G); marci@174: std::ifstream ins(in.c_str()); marci@174: readDimacsMaxFlow(ins, G, s, t, cap); marci@174: marci@334: Timer ts; marci@334: Graph::EdgeMap flow(G); //0 flow marci@334: MaxFlow, Graph::EdgeMap > marci@476: max_flow_test(G, s, t, cap, flow/*, true*/); marci@476: // MaxFlow, Graph::EdgeMap > marci@476: // max_flow_test(G, s, t, cap, flow); marci@334: marci@334: std::cout << "SmatrGraph ..." << std::endl; marci@334: marci@174: { marci@334: std::cout << "preflow ..." << std::endl; marci@334: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@334: ts.reset(); marci@476: max_flow_test.run(); marci@334: std::cout << "elapsed time: " << ts << std::endl; marci@476: std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@334: } marci@174: marci@334: { marci@334: std::cout << "physical blocking flow augmentation ..." << std::endl; marci@334: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@174: ts.reset(); marci@174: int i=0; marci@174: 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@174: } marci@174: marci@476: // { marci@476: // std::cout << "faster physical blocking flow augmentation ..." << std::endl; marci@476: // FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@476: // ts.reset(); marci@476: // int i=0; marci@476: // while (max_flow_test.augmentOnBlockingFlow1()) { ++i; } marci@476: // std::cout << "elapsed time: " << ts << std::endl; marci@476: // std::cout << "number of augmentation phases: " << i << std::endl; marci@476: // std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@476: // } marci@174: marci@174: { marci@334: std::cout << "on-the-fly blocking flow augmentation ..." << std::endl; marci@334: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@334: ts.reset(); marci@334: int i=0; marci@334: while (max_flow_test.augmentOnBlockingFlow2()) { ++i; } marci@334: std::cout << "elapsed time: " << ts << std::endl; marci@334: std::cout << "number of augmentation phases: " << i << std::endl; marci@334: std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; marci@334: } marci@174: marci@334: { marci@334: std::cout << "on-the-fly shortest path augmentation ..." << std::endl; marci@334: FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); marci@174: ts.reset(); marci@174: int i=0; marci@174: 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@174: } marci@174: } marci@174: marci@334: marci@334: marci@334: marci@174: return 0; marci@174: }