82 GEQ, |
82 GEQ, |
83 LEQ |
83 LEQ |
84 }; |
84 }; |
85 |
85 |
86 // Check the interface of an MCF algorithm |
86 // Check the interface of an MCF algorithm |
87 template <typename GR, typename Flow, typename Cost> |
87 template <typename GR, typename Value, typename Cost> |
88 class McfClassConcept |
88 class McfClassConcept |
89 { |
89 { |
90 public: |
90 public: |
91 |
91 |
92 template <typename MCF> |
92 template <typename MCF> |
93 struct Constraints { |
93 struct Constraints { |
94 void constraints() { |
94 void constraints() { |
95 checkConcept<concepts::Digraph, GR>(); |
95 checkConcept<concepts::Digraph, GR>(); |
96 |
96 |
97 MCF mcf(g); |
97 MCF mcf(g); |
|
98 const MCF& const_mcf = mcf; |
98 |
99 |
99 b = mcf.reset() |
100 b = mcf.reset() |
100 .lowerMap(lower) |
101 .lowerMap(lower) |
101 .upperMap(upper) |
102 .upperMap(upper) |
102 .costMap(cost) |
103 .costMap(cost) |
103 .supplyMap(sup) |
104 .supplyMap(sup) |
104 .stSupply(n, n, k) |
105 .stSupply(n, n, k) |
105 .flowMap(flow) |
|
106 .potentialMap(pot) |
|
107 .run(); |
106 .run(); |
108 |
|
109 const MCF& const_mcf = mcf; |
|
110 |
|
111 const typename MCF::FlowMap &fm = const_mcf.flowMap(); |
|
112 const typename MCF::PotentialMap &pm = const_mcf.potentialMap(); |
|
113 |
107 |
114 c = const_mcf.totalCost(); |
108 c = const_mcf.totalCost(); |
115 double x = const_mcf.template totalCost<double>(); |
109 x = const_mcf.template totalCost<double>(); |
116 v = const_mcf.flow(a); |
110 v = const_mcf.flow(a); |
117 c = const_mcf.potential(n); |
111 c = const_mcf.potential(n); |
118 |
112 const_mcf.flowMap(fm); |
119 v = const_mcf.INF; |
113 const_mcf.potentialMap(pm); |
120 |
|
121 ignore_unused_variable_warning(fm); |
|
122 ignore_unused_variable_warning(pm); |
|
123 ignore_unused_variable_warning(x); |
|
124 } |
114 } |
125 |
115 |
126 typedef typename GR::Node Node; |
116 typedef typename GR::Node Node; |
127 typedef typename GR::Arc Arc; |
117 typedef typename GR::Arc Arc; |
128 typedef concepts::ReadMap<Node, Flow> NM; |
118 typedef concepts::ReadMap<Node, Value> NM; |
129 typedef concepts::ReadMap<Arc, Flow> FAM; |
119 typedef concepts::ReadMap<Arc, Value> VAM; |
130 typedef concepts::ReadMap<Arc, Cost> CAM; |
120 typedef concepts::ReadMap<Arc, Cost> CAM; |
|
121 typedef concepts::WriteMap<Arc, Value> FlowMap; |
|
122 typedef concepts::WriteMap<Node, Cost> PotMap; |
131 |
123 |
132 const GR &g; |
124 const GR &g; |
133 const FAM &lower; |
125 const VAM &lower; |
134 const FAM &upper; |
126 const VAM &upper; |
135 const CAM &cost; |
127 const CAM &cost; |
136 const NM ⊃ |
128 const NM ⊃ |
137 const Node &n; |
129 const Node &n; |
138 const Arc &a; |
130 const Arc &a; |
139 const Flow &k; |
131 const Value &k; |
140 Flow v; |
132 FlowMap fm; |
141 Cost c; |
133 PotMap pm; |
142 bool b; |
134 bool b; |
143 |
135 double x; |
144 typename MCF::FlowMap &flow; |
136 typename MCF::Value v; |
145 typename MCF::PotentialMap &pot; |
137 typename MCF::Cost c; |
146 }; |
138 }; |
147 |
139 |
148 }; |
140 }; |
149 |
141 |
150 |
142 |
219 const std::string &test_id = "", |
211 const std::string &test_id = "", |
220 SupplyType type = EQ ) |
212 SupplyType type = EQ ) |
221 { |
213 { |
222 check(mcf_result == result, "Wrong result " + test_id); |
214 check(mcf_result == result, "Wrong result " + test_id); |
223 if (optimal) { |
215 if (optimal) { |
224 check(checkFlow(gr, lower, upper, supply, mcf.flowMap(), type), |
216 typename GR::template ArcMap<typename SM::Value> flow(gr); |
|
217 typename GR::template NodeMap<typename CM::Value> pi(gr); |
|
218 mcf.flowMap(flow); |
|
219 mcf.potentialMap(pi); |
|
220 check(checkFlow(gr, lower, upper, supply, flow, type), |
225 "The flow is not feasible " + test_id); |
221 "The flow is not feasible " + test_id); |
226 check(mcf.totalCost() == total, "The flow is not optimal " + test_id); |
222 check(mcf.totalCost() == total, "The flow is not optimal " + test_id); |
227 check(checkPotential(gr, lower, upper, cost, supply, mcf.flowMap(), |
223 check(checkPotential(gr, lower, upper, cost, supply, flow, pi), |
228 mcf.potentialMap()), |
|
229 "Wrong potentials " + test_id); |
224 "Wrong potentials " + test_id); |
230 } |
225 } |
231 } |
226 } |
232 |
227 |
233 int main() |
228 int main() |
234 { |
229 { |
235 // Check the interfaces |
230 // Check the interfaces |
236 { |
231 { |
237 typedef int Flow; |
|
238 typedef int Cost; |
|
239 typedef concepts::Digraph GR; |
232 typedef concepts::Digraph GR; |
240 checkConcept< McfClassConcept<GR, Flow, Cost>, |
233 checkConcept< McfClassConcept<GR, int, int>, |
241 NetworkSimplex<GR, Flow, Cost> >(); |
234 NetworkSimplex<GR> >(); |
|
235 checkConcept< McfClassConcept<GR, double, double>, |
|
236 NetworkSimplex<GR, double> >(); |
|
237 checkConcept< McfClassConcept<GR, int, double>, |
|
238 NetworkSimplex<GR, int, double> >(); |
242 } |
239 } |
243 |
240 |
244 // Run various MCF tests |
241 // Run various MCF tests |
245 typedef ListDigraph Digraph; |
242 typedef ListDigraph Digraph; |
246 DIGRAPH_TYPEDEFS(ListDigraph); |
243 DIGRAPH_TYPEDEFS(ListDigraph); |