1 #include <iostream> |
|
2 |
|
3 #include <lemon/list_graph.h> |
|
4 #include <lemon/dimacs.h> |
|
5 #include <max_flow.h> |
|
6 #include <max_flow_no_stack.h> |
|
7 #include <lemon/time_measure.h> |
|
8 |
|
9 using namespace lemon; |
|
10 |
|
11 int main(int, char **) { |
|
12 |
|
13 typedef ListGraph Graph; |
|
14 |
|
15 typedef Graph::Node Node; |
|
16 typedef Graph::EdgeIt EdgeIt; |
|
17 |
|
18 Graph G; |
|
19 Node s, t; |
|
20 Graph::EdgeMap<int> cap(G); |
|
21 readDimacs(std::cin, G, cap, s, t); |
|
22 Timer ts; |
|
23 |
|
24 std::cout << |
|
25 "\n Running max_flow.h on a graph with " << |
|
26 G.nodeNum() << " nodes and " << G.edgeNum() << " edges..." |
|
27 << std::endl<<std::endl; |
|
28 |
|
29 Graph::EdgeMap<int> flowstack(G,0); |
|
30 MaxFlow<Graph, int> max_flow_test(G, s, t, cap, flowstack); |
|
31 ts.reset(); |
|
32 max_flow_test.run(); |
|
33 std::cout << "Elapsed time of run() with stl stack: " << std::endl |
|
34 <<ts << std::endl; |
|
35 |
|
36 Graph::EdgeMap<int> flow(G,0); |
|
37 MaxFlowNoStack<Graph, int> max_flow_test_no_stack(G, s, t, cap, flow); |
|
38 ts.reset(); |
|
39 max_flow_test_no_stack.run(); |
|
40 std::cout << "Elapsed time of run() without stack: " << std::endl |
|
41 <<ts << std::endl; |
|
42 |
|
43 Graph::NodeMap<bool> mincut(G); |
|
44 max_flow_test_no_stack.minMinCut(mincut); |
|
45 int min_min_cut_value=0; |
|
46 EdgeIt e; |
|
47 for(G.first(e); G.valid(e); G.next(e)) { |
|
48 if (mincut[G.source(e)] && !mincut[G.target(e)]) min_min_cut_value+=cap[e]; |
|
49 } |
|
50 |
|
51 Graph::NodeMap<bool> cut(G); |
|
52 max_flow_test_no_stack.minCut(cut); |
|
53 int min_cut_value=0; |
|
54 for(G.first(e); G.valid(e); G.next(e)) { |
|
55 if (cut[G.source(e)] && !cut[G.target(e)]) |
|
56 min_cut_value+=cap[e]; |
|
57 } |
|
58 |
|
59 Graph::NodeMap<bool> maxcut(G); |
|
60 max_flow_test_no_stack.maxMinCut(maxcut); |
|
61 int max_min_cut_value=0; |
|
62 for(G.first(e); G.valid(e); G.next(e)) { |
|
63 if (maxcut[G.source(e)] && !maxcut[G.target(e)]) |
|
64 max_min_cut_value+=cap[e]; |
|
65 } |
|
66 |
|
67 std::cout << "\n Checking the result without stack: " <<std::endl; |
|
68 std::cout << "Flow value: "<< max_flow_test_no_stack.flowValue() << std::endl; |
|
69 std::cout << "Min cut value: "<< min_cut_value << std::endl; |
|
70 std::cout << "Min min cut value: "<< min_min_cut_value << std::endl; |
|
71 std::cout << "Max min cut value: "<< max_min_cut_value << |
|
72 std::endl; |
|
73 |
|
74 if ( max_flow_test_no_stack.flowValue() == min_cut_value && |
|
75 min_cut_value == min_min_cut_value && |
|
76 min_min_cut_value == max_min_cut_value ) |
|
77 std::cout << "They are equal! " <<std::endl<< std::endl<<"\n"; |
|
78 |
|
79 /* |
|
80 |
|
81 Graph::EdgeMap<int> flow2(G,0); |
|
82 std::cout << "Calling resetFlow() " << std::endl |
|
83 << ts << std::endl; |
|
84 max_flow_test.setFlow(flow2); |
|
85 ts.reset(); |
|
86 max_flow_test.preflow(max_flow_test.PRE_FLOW); |
|
87 std::cout << "Elapsed time of preflow(PRE_FLOW) starting from the zero flow: " << std::endl |
|
88 << ts << std::endl; |
|
89 |
|
90 Graph::NodeMap<bool> mincut2(G); |
|
91 max_flow_test.minMinCut(mincut2); |
|
92 int min_min_cut_value2=0; |
|
93 for(G.first(e); G.valid(e); G.next(e)) { |
|
94 if (mincut2[G.source(e)] && !mincut2[G.target(e)]) min_min_cut_value2+=cap[e]; |
|
95 } |
|
96 |
|
97 Graph::NodeMap<bool> cut2(G); |
|
98 max_flow_test.minCut(cut2); |
|
99 int min_cut_value2=0; |
|
100 for(G.first(e); G.valid(e); G.next(e)) { |
|
101 if (cut2[G.source(e)] && !cut2[G.target(e)]) |
|
102 min_cut_value2+=cap[e]; |
|
103 } |
|
104 |
|
105 Graph::NodeMap<bool> maxcut2(G); |
|
106 max_flow_test.maxMinCut(maxcut2); |
|
107 int max_min_cut_value2=0; |
|
108 for(G.first(e); G.valid(e); G.next(e)) { |
|
109 if (maxcut2[G.source(e)] && !maxcut2[G.target(e)]) |
|
110 max_min_cut_value2+=cap[e]; |
|
111 } |
|
112 |
|
113 std::cout << "\n Checking the result: " <<std::endl; |
|
114 std::cout << "Flow value: "<< max_flow_test.flowValue() << std::endl; |
|
115 std::cout << "Min cut value: "<< min_cut_value2 << std::endl; |
|
116 std::cout << "Min min cut value: "<< min_min_cut_value2 << std::endl; |
|
117 std::cout << "Max min cut value: "<< max_min_cut_value2 << |
|
118 std::endl; |
|
119 if ( max_flow_test.flowValue() == min_cut_value && |
|
120 min_cut_value == min_min_cut_value && |
|
121 min_min_cut_value == max_min_cut_value ) |
|
122 std::cout << "They are equal! " <<std::endl; |
|
123 |
|
124 |
|
125 MaxFlow<Graph, int> max_flow_test3(G, s, t, cap, flow2); |
|
126 max_flow_test3.run(max_flow_test3.GEN_FLOW); |
|
127 std::cout << "Calling run(GEN_FLOW) from the max flow found before. " <<std::endl; |
|
128 |
|
129 Graph::NodeMap<bool> mincut3(G); |
|
130 max_flow_test3.minMinCut(mincut3); |
|
131 int min_min_cut_value3=0; |
|
132 for(G.first(e); G.valid(e); G.next(e)) { |
|
133 if (mincut3[G.source(e)] && !mincut3[G.target(e)]) min_min_cut_value3+=cap[e]; |
|
134 } |
|
135 |
|
136 Graph::NodeMap<bool> cut3(G); |
|
137 max_flow_test3.minCut(cut3); |
|
138 int min_cut_value3=0; |
|
139 for(G.first(e); G.valid(e); G.next(e)) { |
|
140 if (cut3[G.source(e)] && !cut3[G.target(e)]) |
|
141 min_cut_value3+=cap[e]; |
|
142 } |
|
143 |
|
144 Graph::NodeMap<bool> maxcut3(G); |
|
145 max_flow_test3.maxMinCut(maxcut3); |
|
146 int max_min_cut_value3=0; |
|
147 for(G.first(e); G.valid(e); G.next(e)) { |
|
148 if (maxcut3[G.source(e)] && !maxcut3[G.target(e)]) |
|
149 max_min_cut_value3+=cap[e]; |
|
150 } |
|
151 |
|
152 std::cout << "\n Checking the result: " <<std::endl; |
|
153 std::cout << "Flow value: "<< max_flow_test3.flowValue() << std::endl; |
|
154 std::cout << "Min cut value: "<< min_cut_value3 << std::endl; |
|
155 std::cout << "Min min cut value: "<< min_min_cut_value3 << std::endl; |
|
156 std::cout << "Max min cut value: "<< max_min_cut_value3 << |
|
157 std::endl; |
|
158 |
|
159 if ( max_flow_test3.flowValue() == min_cut_value3 && |
|
160 min_cut_value3 == min_min_cut_value3 && |
|
161 min_min_cut_value3 == max_min_cut_value3 ) |
|
162 std::cout << "They are equal! " <<std::endl<< std::endl<<"\n"; |
|
163 */ |
|
164 |
|
165 return 0; |
|
166 } |
|