69 |
69 |
70 typedef Preflow<Graph, int> PType; |
70 typedef Preflow<Graph, int> PType; |
71 |
71 |
72 std::string f_name; |
72 std::string f_name; |
73 if( getenv("srcdir") ) { |
73 if( getenv("srcdir") ) { |
74 f_name = std::string(getenv("srcdir")) + "/preflow_graph.inp"; |
74 f_name = std::string(getenv("srcdir")) + "/preflow_graph.dim"; |
75 } |
75 } |
76 else { |
76 else { |
77 f_name = "preflow_graph.inp"; |
77 f_name = "preflow_graph.dim"; |
78 } |
78 } |
79 |
79 |
80 std::ifstream file(f_name.c_str()); |
80 std::ifstream file(f_name.c_str()); |
81 |
81 |
82 check(file, "Input file '" << f_name << "' not found."); |
82 check(file, "Input file '" << f_name << "' not found."); |
85 Node s, t; |
85 Node s, t; |
86 CapMap cap(G); |
86 CapMap cap(G); |
87 readDimacs(file, G, cap, s, t); |
87 readDimacs(file, G, cap, s, t); |
88 |
88 |
89 FlowMap flow(G,0); |
89 FlowMap flow(G,0); |
|
90 |
90 |
91 |
|
92 |
91 PType preflow_test(G, s, t, cap, flow); |
93 PType preflow_test(G, s, t, cap, flow); |
92 preflow_test.run(PType::ZERO_FLOW); |
94 preflow_test.run(PType::ZERO_FLOW); |
93 |
95 |
94 |
|
95 CutMap mincut(G,false); |
96 CutMap mincut(G,false); |
96 preflow_test.minCut(mincut); |
97 preflow_test.minCut(mincut); |
97 int min_cut_value=cut_value(G,mincut,cap); |
98 int min_cut_value=cut_value(G,mincut,cap); |
98 |
99 |
99 CutMap minmincut(G,false); |
100 CutMap minmincut(G,false); |
110 "The max flow value is not equal to the three min cut values."); |
111 "The max flow value is not equal to the three min cut values."); |
111 |
112 |
112 int flow_value=preflow_test.flowValue(); |
113 int flow_value=preflow_test.flowValue(); |
113 |
114 |
114 |
115 |
|
116 |
115 for(EdgeIt e(G); e!=INVALID; ++e) cap[e]=2*cap[e]; |
117 for(EdgeIt e(G); e!=INVALID; ++e) cap[e]=2*cap[e]; |
116 preflow_test.setCap(cap); |
118 preflow_test.setCap(cap); |
117 |
|
118 NodeIt tmp_node(G,t); |
|
119 ++tmp_node; |
|
120 t=tmp_node; |
|
121 |
|
122 preflow_test.setTarget(t); //the max flow value remains 2*flow_value |
|
123 //warning: ++t must be a valid node. In preflow_graph, it is. |
|
124 |
119 |
125 preflow_test.phase1(PType::PRE_FLOW); |
120 preflow_test.phase1(PType::PRE_FLOW); |
126 |
121 |
127 CutMap mincut1(G,false); |
122 CutMap mincut1(G,false); |
128 preflow_test.minCut(mincut1); |
123 preflow_test.minCut(mincut1); |
139 min_cut_value=cut_value(G,mincut2,cap); |
134 min_cut_value=cut_value(G,mincut2,cap); |
140 |
135 |
141 CutMap minmincut2(G,false); |
136 CutMap minmincut2(G,false); |
142 preflow_test.minMinCut(minmincut2); |
137 preflow_test.minMinCut(minmincut2); |
143 min_min_cut_value=cut_value(G,minmincut2,cap); |
138 min_min_cut_value=cut_value(G,minmincut2,cap); |
144 |
|
145 |
139 |
146 preflow_test.maxMinCut(maxmincut); |
140 preflow_test.maxMinCut(maxmincut); |
147 |
|
148 max_min_cut_value=cut_value(G,maxmincut,cap); |
141 max_min_cut_value=cut_value(G,maxmincut,cap); |
149 |
142 |
150 check(preflow_test.flowValue() == min_cut_value && |
143 check(preflow_test.flowValue() == min_cut_value && |
151 min_cut_value == min_min_cut_value && |
144 min_cut_value == min_min_cut_value && |
152 min_min_cut_value == max_min_cut_value && |
145 min_min_cut_value == max_min_cut_value && |
153 min_cut_value == 2*flow_value, |
146 min_cut_value == 2*flow_value, |
154 "The max flow value or the three min cut values were not doubled"); |
147 "The max flow value or the three min cut values were not doubled"); |
155 |
148 |
|
149 |
|
150 |
156 EdgeIt e(G); |
151 EdgeIt e(G); |
157 for( int i=1; i==1000; ++i ) { |
152 for( int i=1; i==10; ++i ) { |
158 flow[e]=0; |
153 flow.set(e,0); |
159 ++e; |
154 ++e; |
160 } |
155 } |
161 |
156 |
162 preflow_test.setFlow(flow); |
157 preflow_test.setFlow(flow); |
|
158 |
|
159 NodeIt tmp1(G,s); |
|
160 ++tmp1; |
|
161 if ( tmp1 != INVALID ) s=tmp1; |
|
162 |
|
163 NodeIt tmp2(G,t); |
|
164 ++tmp2; |
|
165 if ( tmp2 != INVALID ) t=tmp2; |
|
166 |
163 preflow_test.setSource(s); |
167 preflow_test.setSource(s); |
164 |
168 preflow_test.setTarget(t); |
|
169 |
165 preflow_test.run(); |
170 preflow_test.run(); |
166 |
171 |
167 CutMap mincut3(G,false); |
172 CutMap mincut3(G,false); |
168 preflow_test.minCut(mincut3); |
173 preflow_test.minCut(mincut3); |
169 min_cut_value=cut_value(G,mincut3,cap); |
174 min_cut_value=cut_value(G,mincut3,cap); |