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