|
1 /* -*- C++ -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library |
|
4 * |
|
5 * Copyright (C) 2003-2008 |
|
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
7 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
8 * |
|
9 * Permission to use, modify and distribute this software is granted |
|
10 * provided that this copyright notice appears in all copies. For |
|
11 * precise terms see the accompanying LICENSE file. |
|
12 * |
|
13 * This software is provided "AS IS" with no warranty of any kind, |
|
14 * express or implied, and with no claim as to its suitability for any |
|
15 * purpose. |
|
16 * |
|
17 */ |
|
18 |
|
19 #include <iostream> |
|
20 #include <fstream> |
|
21 |
|
22 #include <lemon/list_graph.h> |
|
23 #include <lemon/lgf_reader.h> |
|
24 #include <lemon/path.h> |
|
25 #include <lemon/suurballe.h> |
|
26 |
|
27 #include "test_tools.h" |
|
28 |
|
29 using namespace lemon; |
|
30 |
|
31 // Checks the feasibility of the flow |
|
32 template <typename Digraph, typename FlowMap> |
|
33 bool checkFlow( const Digraph& gr, const FlowMap& flow, |
|
34 typename Digraph::Node s, typename Digraph::Node t, |
|
35 int value ) |
|
36 { |
|
37 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
|
38 for (ArcIt e(gr); e != INVALID; ++e) |
|
39 if (!(flow[e] == 0 || flow[e] == 1)) return false; |
|
40 |
|
41 for (NodeIt n(gr); n != INVALID; ++n) { |
|
42 int sum = 0; |
|
43 for (OutArcIt e(gr, n); e != INVALID; ++e) |
|
44 sum += flow[e]; |
|
45 for (InArcIt e(gr, n); e != INVALID; ++e) |
|
46 sum -= flow[e]; |
|
47 if (n == s && sum != value) return false; |
|
48 if (n == t && sum != -value) return false; |
|
49 if (n != s && n != t && sum != 0) return false; |
|
50 } |
|
51 |
|
52 return true; |
|
53 } |
|
54 |
|
55 // Checks the optimalitiy of the flow |
|
56 template < typename Digraph, typename CostMap, |
|
57 typename FlowMap, typename PotentialMap > |
|
58 bool checkOptimality( const Digraph& gr, const CostMap& cost, |
|
59 const FlowMap& flow, const PotentialMap& pi ) |
|
60 { |
|
61 // Checking the Complementary Slackness optimality condition |
|
62 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
|
63 bool opt = true; |
|
64 for (ArcIt e(gr); e != INVALID; ++e) { |
|
65 typename CostMap::Value red_cost = |
|
66 cost[e] + pi[gr.source(e)] - pi[gr.target(e)]; |
|
67 opt = (flow[e] == 0 && red_cost >= 0) || |
|
68 (flow[e] == 1 && red_cost <= 0); |
|
69 if (!opt) break; |
|
70 } |
|
71 return opt; |
|
72 } |
|
73 |
|
74 // Checks a path |
|
75 template < typename Digraph, typename Path > |
|
76 bool checkPath( const Digraph& gr, const Path& path, |
|
77 typename Digraph::Node s, typename Digraph::Node t) |
|
78 { |
|
79 // Checking the Complementary Slackness optimality condition |
|
80 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
|
81 Node n = s; |
|
82 for (int i = 0; i < path.length(); ++i) { |
|
83 if (gr.source(path.nth(i)) != n) return false; |
|
84 n = gr.target(path.nth(i)); |
|
85 } |
|
86 return n == t; |
|
87 } |
|
88 |
|
89 |
|
90 int main() |
|
91 { |
|
92 DIGRAPH_TYPEDEFS(ListDigraph); |
|
93 |
|
94 // Reading the test digraph |
|
95 ListDigraph digraph; |
|
96 ListDigraph::ArcMap<int> length(digraph); |
|
97 Node source, target; |
|
98 |
|
99 std::string fname; |
|
100 if(getenv("srcdir")) |
|
101 fname = std::string(getenv("srcdir")); |
|
102 else fname = "."; |
|
103 fname += "/test/min_cost_flow_test.lgf"; |
|
104 |
|
105 std::ifstream input(fname.c_str()); |
|
106 check(input, "Input file '" << fname << "' not found"); |
|
107 DigraphReader<ListDigraph>(digraph, input). |
|
108 arcMap("cost", length). |
|
109 node("source", source). |
|
110 node("target", target). |
|
111 run(); |
|
112 input.close(); |
|
113 |
|
114 // Finding 2 paths |
|
115 { |
|
116 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
|
117 check(suurballe.run(2) == 2, "Wrong number of paths"); |
|
118 check(checkFlow(digraph, suurballe.flowMap(), source, target, 2), |
|
119 "The flow is not feasible"); |
|
120 check(suurballe.totalLength() == 510, "The flow is not optimal"); |
|
121 check(checkOptimality(digraph, length, suurballe.flowMap(), |
|
122 suurballe.potentialMap()), |
|
123 "Wrong potentials"); |
|
124 for (int i = 0; i < suurballe.pathNum(); ++i) |
|
125 check(checkPath(digraph, suurballe.path(i), source, target), |
|
126 "Wrong path"); |
|
127 } |
|
128 |
|
129 // Finding 3 paths |
|
130 { |
|
131 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
|
132 check(suurballe.run(3) == 3, "Wrong number of paths"); |
|
133 check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), |
|
134 "The flow is not feasible"); |
|
135 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
|
136 check(checkOptimality(digraph, length, suurballe.flowMap(), |
|
137 suurballe.potentialMap()), |
|
138 "Wrong potentials"); |
|
139 for (int i = 0; i < suurballe.pathNum(); ++i) |
|
140 check(checkPath(digraph, suurballe.path(i), source, target), |
|
141 "Wrong path"); |
|
142 } |
|
143 |
|
144 // Finding 5 paths (only 3 can be found) |
|
145 { |
|
146 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
|
147 check(suurballe.run(5) == 3, "Wrong number of paths"); |
|
148 check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), |
|
149 "The flow is not feasible"); |
|
150 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
|
151 check(checkOptimality(digraph, length, suurballe.flowMap(), |
|
152 suurballe.potentialMap()), |
|
153 "Wrong potentials"); |
|
154 for (int i = 0; i < suurballe.pathNum(); ++i) |
|
155 check(checkPath(digraph, suurballe.path(i), source, target), |
|
156 "Wrong path"); |
|
157 } |
|
158 |
|
159 return 0; |
|
160 } |