10 #include <sage_graph.h> |
10 #include <sage_graph.h> |
11 #include <hugo/smart_graph.h> |
11 #include <hugo/smart_graph.h> |
12 #include <hugo/dimacs.h> |
12 #include <hugo/dimacs.h> |
13 #include <hugo/time_measure.h> |
13 #include <hugo/time_measure.h> |
14 //#include <graph_wrapper.h> |
14 //#include <graph_wrapper.h> |
15 #include <hugo/max_flow.h> |
15 #include <hugo/preflow.h> |
16 #include <augmenting_flow.h> |
16 #include <augmenting_flow.h> |
17 //#include <preflow_res.h> |
17 //#include <preflow_res.h> |
18 #include <for_each_macros.h> |
18 #include <for_each_macros.h> |
19 #include <graph_concept.h> |
19 #include <graph_concept.h> |
20 |
20 |
36 Graph::EdgeMap<int> cap(g); |
36 Graph::EdgeMap<int> cap(g); |
37 //readDimacsMaxFlow(std::cin, g, s, t, cap); |
37 //readDimacsMaxFlow(std::cin, g, s, t, cap); |
38 readDimacs(std::cin, g, cap, s, t); |
38 readDimacs(std::cin, g, cap, s, t); |
39 Timer ts; |
39 Timer ts; |
40 Graph::EdgeMap<int> flow(g); //0 flow |
40 Graph::EdgeMap<int> flow(g); //0 flow |
41 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
41 Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
42 max_flow_test(g, s, t, cap, flow); |
42 max_flow_test(g, s, t, cap, flow); |
43 AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
43 AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> > |
44 augmenting_flow_test(g, s, t, cap, flow); |
44 augmenting_flow_test(g, s, t, cap, flow); |
45 |
45 |
46 Graph::NodeMap<bool> cut(g); |
46 Graph::NodeMap<bool> cut(g); |
49 std::cout << "preflow ..." << std::endl; |
49 std::cout << "preflow ..." << std::endl; |
50 ts.reset(); |
50 ts.reset(); |
51 max_flow_test.run(); |
51 max_flow_test.run(); |
52 std::cout << "elapsed time: " << ts << std::endl; |
52 std::cout << "elapsed time: " << ts << std::endl; |
53 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
53 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
54 max_flow_test.actMinCut(cut); |
54 max_flow_test.minCut(cut); |
55 |
55 |
56 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
56 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
57 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
57 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
58 std::cout << "Slackness does not hold!" << std::endl; |
58 std::cout << "Slackness does not hold!" << std::endl; |
59 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
59 if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0) |
63 |
63 |
64 { |
64 { |
65 std::cout << "preflow ..." << std::endl; |
65 std::cout << "preflow ..." << std::endl; |
66 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
66 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0); |
67 ts.reset(); |
67 ts.reset(); |
68 max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); |
68 max_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW); |
69 std::cout << "elapsed time: " << ts << std::endl; |
69 std::cout << "elapsed time: " << ts << std::endl; |
70 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
70 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl; |
71 |
71 |
72 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
72 FOR_EACH_LOC(Graph::EdgeIt, e, g) { |
73 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |
73 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e]) |