marci@475: // -*- c++ -*- marci@475: #include marci@475: #include marci@475: marci@642: #include marci@555: #include marci@555: #include marci@555: #include marci@475: //#include marci@762: #include marci@762: #include marci@475: //#include marci@762: #include marci@651: #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@642: typedef SageGraph MutableGraph; marci@475: marci@651: //typedef FullFeatureGraphConcept Graph; marci@762: //typedef SmartGraph Graph; marci@762: typedef SageGraph 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@577: Graph g; marci@652: marci@475: Node s, t; marci@577: Graph::EdgeMap cap(g); marci@577: //readDimacsMaxFlow(std::cin, g, s, t, cap); marci@577: readDimacs(std::cin, g, cap, s, t); marci@475: Timer ts; marci@577: Graph::EdgeMap flow(g); //0 flow marci@476: MaxFlow, Graph::EdgeMap > marci@577: max_flow_test(g, s, t, cap, flow); marci@762: AugmentingFlow, Graph::EdgeMap > marci@762: augmenting_flow_test(g, s, t, cap, flow); marci@762: marci@646: Graph::NodeMap cut(g); 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@646: max_flow_test.actMinCut(cut); marci@646: marci@646: FOR_EACH_LOC(Graph::EdgeIt, e, g) { marci@646: if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) marci@646: std::cout << "Slackness does not hold!" << std::endl; marci@646: if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) marci@646: std::cout << "Slackness does not hold!" << std::endl; marci@646: } marci@475: } marci@475: marci@475: { marci@475: std::cout << "preflow ..." << std::endl; marci@577: 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@646: marci@646: FOR_EACH_LOC(Graph::EdgeIt, e, g) { marci@646: if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) marci@646: std::cout << "Slackness does not hold!" << std::endl; marci@646: if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) marci@646: std::cout << "Slackness does not hold!" << std::endl; marci@646: } marci@475: } marci@475: marci@475: // { marci@475: // std::cout << "wrapped preflow ..." << std::endl; marci@577: // 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@577: FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); marci@475: ts.reset(); marci@475: int i=0; marci@762: while (augmenting_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@762: std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; marci@646: marci@646: FOR_EACH_LOC(Graph::EdgeIt, e, g) { marci@646: if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) marci@646: std::cout << "Slackness does not hold!" << std::endl; marci@646: if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) marci@646: std::cout << "Slackness does not hold!" << std::endl; marci@646: } marci@475: } marci@475: marci@475: // { marci@475: // std::cout << "faster physical blocking flow augmentation ..." << std::endl; marci@577: // 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@577: FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); marci@475: ts.reset(); marci@475: int i=0; marci@762: while (augmenting_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@762: std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; marci@646: marci@646: FOR_EACH_LOC(Graph::EdgeIt, e, g) { marci@646: if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) marci@646: std::cout << "Slackness does not hold!" << std::endl; marci@646: if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) marci@646: std::cout << "Slackness does not hold!" << std::endl; marci@646: } marci@475: } marci@475: marci@475: { marci@475: std::cout << "on-the-fly shortest path augmentation ..." << std::endl; marci@577: FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); marci@475: ts.reset(); marci@475: int i=0; marci@762: while (augmenting_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@762: std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; marci@646: marci@646: FOR_EACH_LOC(Graph::EdgeIt, e, g) { marci@646: if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) marci@646: std::cout << "Slackness does not hold!" << std::endl; marci@646: if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) marci@646: std::cout << "Slackness does not hold!" << std::endl; marci@646: } marci@475: } marci@475: marci@646: { marci@646: std::cout << "on-the-fly shortest path augmentation ..." << std::endl; marci@646: FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); marci@646: ts.reset(); marci@646: int i=0; marci@762: while (augmenting_flow_test.augmentOnShortestPath2()) { ++i; } marci@646: std::cout << "elapsed time: " << ts << std::endl; marci@646: std::cout << "number of augmentation phases: " << i << std::endl; marci@762: std::cout << "flow value: "<< augmenting_flow_test.flowValue() << std::endl; marci@646: marci@646: FOR_EACH_LOC(Graph::EdgeIt, e, g) { marci@646: if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) marci@646: std::cout << "Slackness does not hold!" << std::endl; marci@646: if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) marci@646: std::cout << "Slackness does not hold!" << std::endl; marci@646: } marci@646: } marci@475: marci@475: return 0; marci@475: }