15 * purpose. |
15 * purpose. |
16 * |
16 * |
17 */ |
17 */ |
18 |
18 |
19 #include <iostream> |
19 #include <iostream> |
|
20 #include <fstream> |
|
21 |
20 #include <lemon/list_graph.h> |
22 #include <lemon/list_graph.h> |
|
23 #include <lemon/graph_reader.h> |
|
24 #include <lemon/path.h> |
21 #include <lemon/suurballe.h> |
25 #include <lemon/suurballe.h> |
22 //#include <path.h> |
26 |
23 #include "test_tools.h" |
27 #include "test_tools.h" |
24 |
28 |
25 using namespace lemon; |
29 using namespace lemon; |
26 |
30 |
|
31 // Checks the feasibility of the flow |
|
32 template <typename Graph, typename FlowMap> |
|
33 bool checkFlow( const Graph& gr, const FlowMap& flow, |
|
34 typename Graph::Node s, typename Graph::Node t, |
|
35 int value ) |
|
36 { |
|
37 GRAPH_TYPEDEFS(typename Graph); |
|
38 for (EdgeIt e(gr); e != INVALID; ++e) |
|
39 if (!(flow[e] == 0 || flow[e] == 1)) return false; |
27 |
40 |
28 bool passed = true; |
41 for (NodeIt n(gr); n != INVALID; ++n) { |
|
42 int sum = 0; |
|
43 for (OutEdgeIt e(gr, n); e != INVALID; ++e) |
|
44 sum += flow[e]; |
|
45 for (InEdgeIt 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 Graph, typename CostMap, |
|
57 typename FlowMap, typename PotentialMap > |
|
58 bool checkOptimality( const Graph& gr, const CostMap& cost, |
|
59 const FlowMap& flow, const PotentialMap& pi ) |
|
60 { |
|
61 // Checking the Complementary Slackness optimality condition |
|
62 GRAPH_TYPEDEFS(typename Graph); |
|
63 bool opt = true; |
|
64 for (EdgeIt 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 Graph, typename Path > |
|
76 bool checkPath( const Graph& gr, const Path& path, |
|
77 typename Graph::Node s, typename Graph::Node t) |
|
78 { |
|
79 // Checking the Complementary Slackness optimality condition |
|
80 GRAPH_TYPEDEFS(typename Graph); |
|
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 } |
29 |
88 |
30 |
89 |
31 int main() |
90 int main() |
32 { |
91 { |
33 typedef ListGraph Graph; |
92 GRAPH_TYPEDEFS(ListGraph); |
34 typedef Graph::Node Node; |
|
35 typedef Graph::Edge Edge; |
|
36 |
93 |
37 Graph graph; |
94 // Reading the test graph |
|
95 ListGraph graph; |
|
96 ListGraph::EdgeMap<int> length(graph); |
|
97 Node source, target; |
38 |
98 |
39 //Ahuja könyv példája |
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"; |
40 |
104 |
41 Node s=graph.addNode(); |
105 std::ifstream input(fname.c_str()); |
42 Node v1=graph.addNode(); |
106 check(input, "Input file '" << fname << "' not found"); |
43 Node v2=graph.addNode(); |
107 GraphReader<ListGraph>(input, graph). |
44 Node v3=graph.addNode(); |
108 readEdgeMap("cost", length). |
45 Node v4=graph.addNode(); |
109 readNode("source", source). |
46 Node v5=graph.addNode(); |
110 readNode("target", target). |
47 Node t=graph.addNode(); |
111 run(); |
|
112 input.close(); |
|
113 |
|
114 // Finding 2 paths |
|
115 { |
|
116 Suurballe<ListGraph> suurballe(graph, length, source, target); |
|
117 check(suurballe.run(2) == 2, "Wrong number of paths"); |
|
118 check(checkFlow(graph, suurballe.flowMap(), source, target, 2), |
|
119 "The flow is not feasible"); |
|
120 check(suurballe.totalLength() == 510, "The flow is not optimal"); |
|
121 check(checkOptimality(graph, length, suurballe.flowMap(), |
|
122 suurballe.potentialMap()), |
|
123 "Wrong potentials"); |
|
124 for (int i = 0; i < suurballe.pathNum(); ++i) |
|
125 check(checkPath(graph, suurballe.path(i), source, target), |
|
126 "Wrong path"); |
|
127 } |
48 |
128 |
49 Edge s_v1=graph.addEdge(s, v1); |
129 // Finding 3 paths |
50 Edge v1_v2=graph.addEdge(v1, v2); |
130 { |
51 Edge s_v3=graph.addEdge(s, v3); |
131 Suurballe<ListGraph> suurballe(graph, length, source, target); |
52 Edge v2_v4=graph.addEdge(v2, v4); |
132 check(suurballe.run(3) == 3, "Wrong number of paths"); |
53 Edge v2_v5=graph.addEdge(v2, v5); |
133 check(checkFlow(graph, suurballe.flowMap(), source, target, 3), |
54 Edge v3_v5=graph.addEdge(v3, v5); |
134 "The flow is not feasible"); |
55 Edge v4_t=graph.addEdge(v4, t); |
135 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
56 Edge v5_t=graph.addEdge(v5, t); |
136 check(checkOptimality(graph, length, suurballe.flowMap(), |
57 |
137 suurballe.potentialMap()), |
|
138 "Wrong potentials"); |
|
139 for (int i = 0; i < suurballe.pathNum(); ++i) |
|
140 check(checkPath(graph, suurballe.path(i), source, target), |
|
141 "Wrong path"); |
|
142 } |
58 |
143 |
59 Graph::EdgeMap<int> length(graph); |
144 // Finding 5 paths (only 3 can be found) |
|
145 { |
|
146 Suurballe<ListGraph> suurballe(graph, length, source, target); |
|
147 check(suurballe.run(5) == 3, "Wrong number of paths"); |
|
148 check(checkFlow(graph, suurballe.flowMap(), source, target, 3), |
|
149 "The flow is not feasible"); |
|
150 check(suurballe.totalLength() == 1040, "The flow is not optimal"); |
|
151 check(checkOptimality(graph, length, suurballe.flowMap(), |
|
152 suurballe.potentialMap()), |
|
153 "Wrong potentials"); |
|
154 for (int i = 0; i < suurballe.pathNum(); ++i) |
|
155 check(checkPath(graph, suurballe.path(i), source, target), |
|
156 "Wrong path"); |
|
157 } |
60 |
158 |
61 length.set(s_v1, 6); |
159 return 0; |
62 length.set(v1_v2, 4); |
|
63 length.set(s_v3, 10); |
|
64 length.set(v2_v4, 5); |
|
65 length.set(v2_v5, 1); |
|
66 length.set(v3_v5, 5); |
|
67 length.set(v4_t, 8); |
|
68 length.set(v5_t, 8); |
|
69 |
|
70 std::cout << "Minlengthpaths algorithm test..." << std::endl; |
|
71 |
|
72 |
|
73 int k=3; |
|
74 Suurballe< Graph, Graph::EdgeMap<int> > |
|
75 surb_test(graph, length, s, t); |
|
76 |
|
77 check( surb_test.run(k) == 2 && surb_test.totalLength() == 46, |
|
78 "Two paths, total length should be 46"); |
|
79 |
|
80 check( surb_test.checkComplementarySlackness(), |
|
81 "Complementary slackness conditions are not met."); |
|
82 |
|
83 // typedef DirPath<Graph> DPath; |
|
84 // DPath P(graph); |
|
85 |
|
86 /* |
|
87 surb_test.getPath(P,0); |
|
88 check(P.length() == 4, "First path should contain 4 edges."); |
|
89 std::cout<<P.length()<<std::endl; |
|
90 surb_test.getPath(P,1); |
|
91 check(P.length() == 3, "Second path: 3 edges."); |
|
92 std::cout<<P.length()<<std::endl; |
|
93 */ |
|
94 |
|
95 k=1; |
|
96 check( surb_test.run(k) == 1 && surb_test.totalLength() == 19, |
|
97 "One path, total length should be 19"); |
|
98 |
|
99 check( surb_test.checkComplementarySlackness(), |
|
100 "Complementary slackness conditions are not met."); |
|
101 |
|
102 // surb_test.getPath(P,0); |
|
103 // check(P.length() == 4, "First path should contain 4 edges."); |
|
104 |
|
105 std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!") |
|
106 << std::endl; |
|
107 |
|
108 return passed ? 0 : 1; |
|
109 |
|
110 } |
160 } |