7 #include <dimacs.h> |
7 #include <dimacs.h> |
8 #include <edmonds_karp.h> |
8 #include <edmonds_karp.h> |
9 #include <time_measure.h> |
9 #include <time_measure.h> |
10 //#include <graph_wrapper.h> |
10 //#include <graph_wrapper.h> |
11 #include <preflow.h> |
11 #include <preflow.h> |
|
12 #include <preflowproba.h> |
12 #include <for_each_macros.h> |
13 #include <for_each_macros.h> |
13 |
14 |
14 using namespace hugo; |
15 using namespace hugo; |
15 |
16 |
16 // Use a DIMACS max flow file as stdin. |
17 // Use a DIMACS max flow file as stdin. |
68 Graph::EdgeMap<int> cap(G); |
69 Graph::EdgeMap<int> cap(G); |
69 readDimacsMaxFlow(std::cin, G, s, t, cap); |
70 readDimacsMaxFlow(std::cin, G, s, t, cap); |
70 Timer ts; |
71 Timer ts; |
71 Graph::EdgeMap<int> flow(G); //0 flow |
72 Graph::EdgeMap<int> flow(G); //0 flow |
72 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
73 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
73 pre_flow_test(G, s, t, cap, flow); |
74 pre_flow_test(G, s, t, cap, flow, true); |
|
75 PreflowProba<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
|
76 pre_flow_proba(G, s, t, cap, flow, true, true); |
74 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
77 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
75 max_flow_test(G, s, t, cap, flow); |
78 max_flow_test(G, s, t, cap, flow); |
76 |
79 |
77 { |
80 { |
78 std::cout << "preflow ..." << std::endl; |
81 std::cout << "preflow ..." << std::endl; |
79 ts.reset(); |
82 ts.reset(); |
80 pre_flow_test.run(); |
83 pre_flow_test.run(); |
|
84 std::cout << "elapsed time: " << ts << std::endl; |
|
85 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; |
|
86 } |
|
87 |
|
88 { |
|
89 std::cout << "wrapped preflow ..." << std::endl; |
|
90 FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0); |
|
91 ts.reset(); |
|
92 pre_flow_proba.run(); |
81 std::cout << "elapsed time: " << ts << std::endl; |
93 std::cout << "elapsed time: " << ts << std::endl; |
82 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; |
94 std::cout << "flow value: "<< pre_flow_test.flowValue() << std::endl; |
83 } |
95 } |
84 |
96 |
85 { |
97 { |