1 /* -*- C++ -*- |
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
2 * |
2 * |
3 * This file is a part of LEMON, a generic C++ optimization library |
3 * This file is a part of LEMON, a generic C++ optimization library. |
4 * |
4 * |
5 * Copyright (C) 2003-2008 |
5 * Copyright (C) 2003-2009 |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
8 * |
8 * |
9 * Permission to use, modify and distribute this software is granted |
9 * Permission to use, modify and distribute this software is granted |
10 * provided that this copyright notice appears in all copies. For |
10 * provided that this copyright notice appears in all copies. For |
70 "target 12\n" |
70 "target 12\n" |
71 "@end\n"; |
71 "@end\n"; |
72 |
72 |
73 // Check the feasibility of the flow |
73 // Check the feasibility of the flow |
74 template <typename Digraph, typename FlowMap> |
74 template <typename Digraph, typename FlowMap> |
75 bool checkFlow( const Digraph& gr, const FlowMap& flow, |
75 bool checkFlow( const Digraph& gr, const FlowMap& flow, |
76 typename Digraph::Node s, typename Digraph::Node t, |
76 typename Digraph::Node s, typename Digraph::Node t, |
77 int value ) |
77 int value ) |
78 { |
78 { |
79 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
79 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
80 for (ArcIt e(gr); e != INVALID; ++e) |
80 for (ArcIt e(gr); e != INVALID; ++e) |
93 |
93 |
94 return true; |
94 return true; |
95 } |
95 } |
96 |
96 |
97 // Check the optimalitiy of the flow |
97 // Check the optimalitiy of the flow |
98 template < typename Digraph, typename CostMap, |
98 template < typename Digraph, typename CostMap, |
99 typename FlowMap, typename PotentialMap > |
99 typename FlowMap, typename PotentialMap > |
100 bool checkOptimality( const Digraph& gr, const CostMap& cost, |
100 bool checkOptimality( const Digraph& gr, const CostMap& cost, |
101 const FlowMap& flow, const PotentialMap& pi ) |
101 const FlowMap& flow, const PotentialMap& pi ) |
102 { |
102 { |
103 // Check the "Complementary Slackness" optimality condition |
103 // Check the "Complementary Slackness" optimality condition |
142 DigraphReader<ListDigraph>(digraph, input). |
142 DigraphReader<ListDigraph>(digraph, input). |
143 arcMap("cost", length). |
143 arcMap("cost", length). |
144 node("source", source). |
144 node("source", source). |
145 node("target", target). |
145 node("target", target). |
146 run(); |
146 run(); |
147 |
147 |
148 // Find 2 paths |
148 // Find 2 paths |
149 { |
149 { |
150 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
150 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
151 check(suurballe.run(2) == 2, "Wrong number of paths"); |
151 check(suurballe.run(2) == 2, "Wrong number of paths"); |
152 check(checkFlow(digraph, suurballe.flowMap(), source, target, 2), |
152 check(checkFlow(digraph, suurballe.flowMap(), source, target, 2), |
153 "The flow is not feasible"); |
153 "The flow is not feasible"); |
154 check(suurballe.totalLength() == 510, "The flow is not optimal"); |
154 check(suurballe.totalLength() == 510, "The flow is not optimal"); |
155 check(checkOptimality(digraph, length, suurballe.flowMap(), |
155 check(checkOptimality(digraph, length, suurballe.flowMap(), |
156 suurballe.potentialMap()), |
156 suurballe.potentialMap()), |
157 "Wrong potentials"); |
157 "Wrong potentials"); |
158 for (int i = 0; i < suurballe.pathNum(); ++i) |
158 for (int i = 0; i < suurballe.pathNum(); ++i) |
159 check(checkPath(digraph, suurballe.path(i), source, target), |
159 check(checkPath(digraph, suurballe.path(i), source, target), |
160 "Wrong path"); |
160 "Wrong path"); |
165 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
165 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
166 check(suurballe.run(3) == 3, "Wrong number of paths"); |
166 check(suurballe.run(3) == 3, "Wrong number of paths"); |
167 check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), |
167 check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), |
168 "The flow is not feasible"); |
168 "The flow is not feasible"); |
169 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
169 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
170 check(checkOptimality(digraph, length, suurballe.flowMap(), |
170 check(checkOptimality(digraph, length, suurballe.flowMap(), |
171 suurballe.potentialMap()), |
171 suurballe.potentialMap()), |
172 "Wrong potentials"); |
172 "Wrong potentials"); |
173 for (int i = 0; i < suurballe.pathNum(); ++i) |
173 for (int i = 0; i < suurballe.pathNum(); ++i) |
174 check(checkPath(digraph, suurballe.path(i), source, target), |
174 check(checkPath(digraph, suurballe.path(i), source, target), |
175 "Wrong path"); |
175 "Wrong path"); |
180 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
180 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
181 check(suurballe.run(5) == 3, "Wrong number of paths"); |
181 check(suurballe.run(5) == 3, "Wrong number of paths"); |
182 check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), |
182 check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), |
183 "The flow is not feasible"); |
183 "The flow is not feasible"); |
184 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
184 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
185 check(checkOptimality(digraph, length, suurballe.flowMap(), |
185 check(checkOptimality(digraph, length, suurballe.flowMap(), |
186 suurballe.potentialMap()), |
186 suurballe.potentialMap()), |
187 "Wrong potentials"); |
187 "Wrong potentials"); |
188 for (int i = 0; i < suurballe.pathNum(); ++i) |
188 for (int i = 0; i < suurballe.pathNum(); ++i) |
189 check(checkPath(digraph, suurballe.path(i), source, target), |
189 check(checkPath(digraph, suurballe.path(i), source, target), |
190 "Wrong path"); |
190 "Wrong path"); |