marci@748: #include <iostream> marci@748: alpar@921: //#include <lemon/list_graph.h> marci@748: #include <sage_graph.h> alpar@921: #include <lemon/dimacs.h> alpar@921: #include <lemon/max_flow.h> marci@748: //#include <max_flow_no_stack.h> alpar@921: #include <lemon/time_measure.h> marci@748: alpar@921: using namespace lemon; marci@748: marci@748: int main(int, char **) { marci@748: marci@748: // typedef ListGraph Graph; marci@748: typedef SageGraph Graph; marci@748: marci@748: typedef Graph::Node Node; marci@748: typedef Graph::EdgeIt EdgeIt; marci@748: marci@748: Graph G; marci@748: Node s, t; marci@748: Graph::EdgeMap<int> cap(G); marci@748: Graph::EdgeMap<int> flow(G,0); marci@748: marci@748: readDimacs(std::cin, G, cap, s, t, flow); marci@748: Timer ts; marci@748: marci@748: std::cout << marci@748: "\n Running max_flow.h on a graph with " << marci@748: G.nodeNum() << " nodes and " << G.edgeNum() << " edges..." marci@748: << std::endl<<std::endl; marci@748: marci@748: marci@748: MaxFlow<Graph, int> max_flow_test_no_stack(G, s, t, cap, flow); marci@748: ts.reset(); marci@748: max_flow_test_no_stack.preflowPhase1(MaxFlow<Graph, int>::PRE_FLOW); marci@748: std::cout << "Elapsed time of run() without stack: " << std::endl marci@748: <<ts << std::endl; marci@748: marci@748: Graph::NodeMap<bool> mincut(G); marci@748: max_flow_test_no_stack.minMinCut(mincut); marci@748: int min_min_cut_value=0; marci@748: EdgeIt e; marci@748: for(G.first(e); G.valid(e); G.next(e)) { alpar@986: if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e]; marci@748: } marci@748: marci@748: Graph::NodeMap<bool> cut(G); marci@748: max_flow_test_no_stack.minCut(cut); marci@748: int min_cut_value=0; marci@748: for(G.first(e); G.valid(e); G.next(e)) { alpar@986: if (cut[G.source(e)] && !cut[G.target(e)]) marci@748: min_cut_value+=cap[e]; marci@748: } marci@748: marci@748: Graph::NodeMap<bool> maxcut(G); marci@748: max_flow_test_no_stack.maxMinCut(maxcut); marci@748: int max_min_cut_value=0; marci@748: for(G.first(e); G.valid(e); G.next(e)) { alpar@986: if (maxcut[G.source(e)] && !maxcut[G.target(e)]) marci@748: max_min_cut_value+=cap[e]; marci@748: } marci@748: marci@748: std::cout << "\n Checking the result without stack: " <<std::endl; marci@748: std::cout << "Flow value: "<< max_flow_test_no_stack.flowValue() << std::endl; marci@748: std::cout << "Min cut value: "<< min_cut_value << std::endl; marci@748: std::cout << "Min min cut value: "<< min_min_cut_value << std::endl; marci@748: std::cout << "Max min cut value: "<< max_min_cut_value << marci@748: std::endl; marci@748: marci@748: if ( max_flow_test_no_stack.flowValue() == min_cut_value && marci@748: min_cut_value == min_min_cut_value && marci@748: min_min_cut_value == max_min_cut_value ) marci@748: std::cout << "They are equal! " <<std::endl<< std::endl<<"\n"; marci@748: marci@748: /* marci@748: marci@748: Graph::EdgeMap<int> flow2(G,0); alpar@757: std::cout << "Calling setFlow() " << std::endl marci@748: << ts << std::endl; alpar@757: max_flow_test.setFlow(flow2); marci@748: ts.reset(); marci@748: max_flow_test.preflow(max_flow_test.PRE_FLOW); marci@748: std::cout << "Elapsed time of preflow(PRE_FLOW) starting from the zero flow: " << std::endl marci@748: << ts << std::endl; marci@748: marci@748: Graph::NodeMap<bool> mincut2(G); marci@748: max_flow_test.minMinCut(mincut2); marci@748: int min_min_cut_value2=0; marci@748: for(G.first(e); G.valid(e); G.next(e)) { alpar@986: if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e]; marci@748: } marci@748: marci@748: Graph::NodeMap<bool> cut2(G); marci@748: max_flow_test.minCut(cut2); marci@748: int min_cut_value2=0; marci@748: for(G.first(e); G.valid(e); G.next(e)) { alpar@986: if (cut2[G.source(e)] && !cut2[G.target(e)]) marci@748: min_cut_value2+=cap[e]; marci@748: } marci@748: marci@748: Graph::NodeMap<bool> maxcut2(G); marci@748: max_flow_test.maxMinCut(maxcut2); marci@748: int max_min_cut_value2=0; marci@748: for(G.first(e); G.valid(e); G.next(e)) { alpar@986: if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) marci@748: max_min_cut_value2+=cap[e]; marci@748: } marci@748: marci@748: std::cout << "\n Checking the result: " <<std::endl; marci@748: std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl; marci@748: std::cout << "Min cut value: "<< min_cut_value2 << std::endl; marci@748: std::cout << "Min min cut value: "<< min_min_cut_value2 << std::endl; marci@748: std::cout << "Max min cut value: "<< max_min_cut_value2 << marci@748: std::endl; marci@748: if ( max_flow_test.flowValue() == min_cut_value && marci@748: min_cut_value == min_min_cut_value && marci@748: min_min_cut_value == max_min_cut_value ) marci@748: std::cout << "They are equal! " <<std::endl; marci@748: marci@748: marci@748: MaxFlow<Graph, int> max_flow_test3(G, s, t, cap, flow2); marci@748: max_flow_test3.run(max_flow_test3.GEN_FLOW); marci@748: std::cout << "Calling run(GEN_FLOW) from the max flow found before. " <<std::endl; marci@748: marci@748: Graph::NodeMap<bool> mincut3(G); marci@748: max_flow_test3.minMinCut(mincut3); marci@748: int min_min_cut_value3=0; marci@748: for(G.first(e); G.valid(e); G.next(e)) { alpar@986: if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e]; marci@748: } marci@748: marci@748: Graph::NodeMap<bool> cut3(G); marci@748: max_flow_test3.minCut(cut3); marci@748: int min_cut_value3=0; marci@748: for(G.first(e); G.valid(e); G.next(e)) { alpar@986: if (cut3[G.source(e)] && !cut3[G.target(e)]) marci@748: min_cut_value3+=cap[e]; marci@748: } marci@748: marci@748: Graph::NodeMap<bool> maxcut3(G); marci@748: max_flow_test3.maxMinCut(maxcut3); marci@748: int max_min_cut_value3=0; marci@748: for(G.first(e); G.valid(e); G.next(e)) { alpar@986: if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) marci@748: max_min_cut_value3+=cap[e]; marci@748: } marci@748: marci@748: std::cout << "\n Checking the result: " <<std::endl; marci@748: std::cout << "Flow value: "<< max_flow_test3.flowValue() << std::endl; marci@748: std::cout << "Min cut value: "<< min_cut_value3 << std::endl; marci@748: std::cout << "Min min cut value: "<< min_min_cut_value3 << std::endl; marci@748: std::cout << "Max min cut value: "<< max_min_cut_value3 << marci@748: std::endl; marci@748: marci@748: if ( max_flow_test3.flowValue() == min_cut_value3 && marci@748: min_cut_value3 == min_min_cut_value3 && marci@748: min_min_cut_value3 == max_min_cut_value3 ) marci@748: std::cout << "They are equal! " <<std::endl<< std::endl<<"\n"; marci@748: */ marci@748: marci@748: return 0; marci@748: }