equal
deleted
inserted
replaced
26 |
26 |
27 #include "test_tools.h" |
27 #include "test_tools.h" |
28 |
28 |
29 using namespace lemon; |
29 using namespace lemon; |
30 |
30 |
31 // Checks the feasibility of the flow |
31 // Check the feasibility of the flow |
32 template <typename Digraph, typename FlowMap> |
32 template <typename Digraph, typename FlowMap> |
33 bool checkFlow( const Digraph& gr, const FlowMap& flow, |
33 bool checkFlow( const Digraph& gr, const FlowMap& flow, |
34 typename Digraph::Node s, typename Digraph::Node t, |
34 typename Digraph::Node s, typename Digraph::Node t, |
35 int value ) |
35 int value ) |
36 { |
36 { |
50 } |
50 } |
51 |
51 |
52 return true; |
52 return true; |
53 } |
53 } |
54 |
54 |
55 // Checks the optimalitiy of the flow |
55 // Check the optimalitiy of the flow |
56 template < typename Digraph, typename CostMap, |
56 template < typename Digraph, typename CostMap, |
57 typename FlowMap, typename PotentialMap > |
57 typename FlowMap, typename PotentialMap > |
58 bool checkOptimality( const Digraph& gr, const CostMap& cost, |
58 bool checkOptimality( const Digraph& gr, const CostMap& cost, |
59 const FlowMap& flow, const PotentialMap& pi ) |
59 const FlowMap& flow, const PotentialMap& pi ) |
60 { |
60 { |
61 // Checking the Complementary Slackness optimality condition |
61 // Check the "Complementary Slackness" optimality condition |
62 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
62 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
63 bool opt = true; |
63 bool opt = true; |
64 for (ArcIt e(gr); e != INVALID; ++e) { |
64 for (ArcIt e(gr); e != INVALID; ++e) { |
65 typename CostMap::Value red_cost = |
65 typename CostMap::Value red_cost = |
66 cost[e] + pi[gr.source(e)] - pi[gr.target(e)]; |
66 cost[e] + pi[gr.source(e)] - pi[gr.target(e)]; |
69 if (!opt) break; |
69 if (!opt) break; |
70 } |
70 } |
71 return opt; |
71 return opt; |
72 } |
72 } |
73 |
73 |
74 // Checks a path |
74 // Check a path |
75 template < typename Digraph, typename Path > |
75 template <typename Digraph, typename Path> |
76 bool checkPath( const Digraph& gr, const Path& path, |
76 bool checkPath( const Digraph& gr, const Path& path, |
77 typename Digraph::Node s, typename Digraph::Node t) |
77 typename Digraph::Node s, typename Digraph::Node t) |
78 { |
78 { |
79 // Checking the Complementary Slackness optimality condition |
79 // Check the "Complementary Slackness" optimality condition |
80 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
80 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); |
81 Node n = s; |
81 Node n = s; |
82 for (int i = 0; i < path.length(); ++i) { |
82 for (int i = 0; i < path.length(); ++i) { |
83 if (gr.source(path.nth(i)) != n) return false; |
83 if (gr.source(path.nth(i)) != n) return false; |
84 n = gr.target(path.nth(i)); |
84 n = gr.target(path.nth(i)); |
89 |
89 |
90 int main() |
90 int main() |
91 { |
91 { |
92 DIGRAPH_TYPEDEFS(ListDigraph); |
92 DIGRAPH_TYPEDEFS(ListDigraph); |
93 |
93 |
94 // Reading the test digraph |
94 // Read the test digraph |
95 ListDigraph digraph; |
95 ListDigraph digraph; |
96 ListDigraph::ArcMap<int> length(digraph); |
96 ListDigraph::ArcMap<int> length(digraph); |
97 Node source, target; |
97 Node source, target; |
98 |
98 |
99 std::string fname; |
99 std::string fname; |
109 node("source", source). |
109 node("source", source). |
110 node("target", target). |
110 node("target", target). |
111 run(); |
111 run(); |
112 input.close(); |
112 input.close(); |
113 |
113 |
114 // Finding 2 paths |
114 // Find 2 paths |
115 { |
115 { |
116 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
116 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
117 check(suurballe.run(2) == 2, "Wrong number of paths"); |
117 check(suurballe.run(2) == 2, "Wrong number of paths"); |
118 check(checkFlow(digraph, suurballe.flowMap(), source, target, 2), |
118 check(checkFlow(digraph, suurballe.flowMap(), source, target, 2), |
119 "The flow is not feasible"); |
119 "The flow is not feasible"); |
124 for (int i = 0; i < suurballe.pathNum(); ++i) |
124 for (int i = 0; i < suurballe.pathNum(); ++i) |
125 check(checkPath(digraph, suurballe.path(i), source, target), |
125 check(checkPath(digraph, suurballe.path(i), source, target), |
126 "Wrong path"); |
126 "Wrong path"); |
127 } |
127 } |
128 |
128 |
129 // Finding 3 paths |
129 // Find 3 paths |
130 { |
130 { |
131 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
131 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
132 check(suurballe.run(3) == 3, "Wrong number of paths"); |
132 check(suurballe.run(3) == 3, "Wrong number of paths"); |
133 check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), |
133 check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), |
134 "The flow is not feasible"); |
134 "The flow is not feasible"); |
139 for (int i = 0; i < suurballe.pathNum(); ++i) |
139 for (int i = 0; i < suurballe.pathNum(); ++i) |
140 check(checkPath(digraph, suurballe.path(i), source, target), |
140 check(checkPath(digraph, suurballe.path(i), source, target), |
141 "Wrong path"); |
141 "Wrong path"); |
142 } |
142 } |
143 |
143 |
144 // Finding 5 paths (only 3 can be found) |
144 // Find 5 paths (only 3 can be found) |
145 { |
145 { |
146 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
146 Suurballe<ListDigraph> suurballe(digraph, length, source, target); |
147 check(suurballe.run(5) == 3, "Wrong number of paths"); |
147 check(suurballe.run(5) == 3, "Wrong number of paths"); |
148 check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), |
148 check(checkFlow(digraph, suurballe.flowMap(), source, target, 3), |
149 "The flow is not feasible"); |
149 "The flow is not feasible"); |