1.1 --- a/test/suurballe_test.cc Thu Feb 28 16:33:40 2008 +0000
1.2 +++ b/test/suurballe_test.cc Fri Feb 29 15:55:13 2008 +0000
1.3 @@ -17,94 +17,144 @@
1.4 */
1.5
1.6 #include <iostream>
1.7 +#include <fstream>
1.8 +
1.9 #include <lemon/list_graph.h>
1.10 +#include <lemon/graph_reader.h>
1.11 +#include <lemon/path.h>
1.12 #include <lemon/suurballe.h>
1.13 -//#include <path.h>
1.14 +
1.15 #include "test_tools.h"
1.16
1.17 using namespace lemon;
1.18
1.19 +// Checks the feasibility of the flow
1.20 +template <typename Graph, typename FlowMap>
1.21 +bool checkFlow( const Graph& gr, const FlowMap& flow,
1.22 + typename Graph::Node s, typename Graph::Node t,
1.23 + int value )
1.24 +{
1.25 + GRAPH_TYPEDEFS(typename Graph);
1.26 + for (EdgeIt e(gr); e != INVALID; ++e)
1.27 + if (!(flow[e] == 0 || flow[e] == 1)) return false;
1.28
1.29 -bool passed = true;
1.30 + for (NodeIt n(gr); n != INVALID; ++n) {
1.31 + int sum = 0;
1.32 + for (OutEdgeIt e(gr, n); e != INVALID; ++e)
1.33 + sum += flow[e];
1.34 + for (InEdgeIt e(gr, n); e != INVALID; ++e)
1.35 + sum -= flow[e];
1.36 + if (n == s && sum != value) return false;
1.37 + if (n == t && sum != -value) return false;
1.38 + if (n != s && n != t && sum != 0) return false;
1.39 + }
1.40 +
1.41 + return true;
1.42 +}
1.43 +
1.44 +// Checks the optimalitiy of the flow
1.45 +template < typename Graph, typename CostMap,
1.46 + typename FlowMap, typename PotentialMap >
1.47 +bool checkOptimality( const Graph& gr, const CostMap& cost,
1.48 + const FlowMap& flow, const PotentialMap& pi )
1.49 +{
1.50 + // Checking the Complementary Slackness optimality condition
1.51 + GRAPH_TYPEDEFS(typename Graph);
1.52 + bool opt = true;
1.53 + for (EdgeIt e(gr); e != INVALID; ++e) {
1.54 + typename CostMap::Value red_cost =
1.55 + cost[e] + pi[gr.source(e)] - pi[gr.target(e)];
1.56 + opt = (flow[e] == 0 && red_cost >= 0) ||
1.57 + (flow[e] == 1 && red_cost <= 0);
1.58 + if (!opt) break;
1.59 + }
1.60 + return opt;
1.61 +}
1.62 +
1.63 +// Checks a path
1.64 +template < typename Graph, typename Path >
1.65 +bool checkPath( const Graph& gr, const Path& path,
1.66 + typename Graph::Node s, typename Graph::Node t)
1.67 +{
1.68 + // Checking the Complementary Slackness optimality condition
1.69 + GRAPH_TYPEDEFS(typename Graph);
1.70 + Node n = s;
1.71 + for (int i = 0; i < path.length(); ++i) {
1.72 + if (gr.source(path.nth(i)) != n) return false;
1.73 + n = gr.target(path.nth(i));
1.74 + }
1.75 + return n == t;
1.76 +}
1.77
1.78
1.79 int main()
1.80 {
1.81 - typedef ListGraph Graph;
1.82 - typedef Graph::Node Node;
1.83 - typedef Graph::Edge Edge;
1.84 + GRAPH_TYPEDEFS(ListGraph);
1.85
1.86 - Graph graph;
1.87 + // Reading the test graph
1.88 + ListGraph graph;
1.89 + ListGraph::EdgeMap<int> length(graph);
1.90 + Node source, target;
1.91
1.92 - //Ahuja könyv példája
1.93 + std::string fname;
1.94 + if(getenv("srcdir"))
1.95 + fname = std::string(getenv("srcdir"));
1.96 + else fname = ".";
1.97 + fname += "/test/min_cost_flow_test.lgf";
1.98
1.99 - Node s=graph.addNode();
1.100 - Node v1=graph.addNode();
1.101 - Node v2=graph.addNode();
1.102 - Node v3=graph.addNode();
1.103 - Node v4=graph.addNode();
1.104 - Node v5=graph.addNode();
1.105 - Node t=graph.addNode();
1.106 + std::ifstream input(fname.c_str());
1.107 + check(input, "Input file '" << fname << "' not found");
1.108 + GraphReader<ListGraph>(input, graph).
1.109 + readEdgeMap("cost", length).
1.110 + readNode("source", source).
1.111 + readNode("target", target).
1.112 + run();
1.113 + input.close();
1.114 +
1.115 + // Finding 2 paths
1.116 + {
1.117 + Suurballe<ListGraph> suurballe(graph, length, source, target);
1.118 + check(suurballe.run(2) == 2, "Wrong number of paths");
1.119 + check(checkFlow(graph, suurballe.flowMap(), source, target, 2),
1.120 + "The flow is not feasible");
1.121 + check(suurballe.totalLength() == 510, "The flow is not optimal");
1.122 + check(checkOptimality(graph, length, suurballe.flowMap(),
1.123 + suurballe.potentialMap()),
1.124 + "Wrong potentials");
1.125 + for (int i = 0; i < suurballe.pathNum(); ++i)
1.126 + check(checkPath(graph, suurballe.path(i), source, target),
1.127 + "Wrong path");
1.128 + }
1.129
1.130 - Edge s_v1=graph.addEdge(s, v1);
1.131 - Edge v1_v2=graph.addEdge(v1, v2);
1.132 - Edge s_v3=graph.addEdge(s, v3);
1.133 - Edge v2_v4=graph.addEdge(v2, v4);
1.134 - Edge v2_v5=graph.addEdge(v2, v5);
1.135 - Edge v3_v5=graph.addEdge(v3, v5);
1.136 - Edge v4_t=graph.addEdge(v4, t);
1.137 - Edge v5_t=graph.addEdge(v5, t);
1.138 -
1.139 + // Finding 3 paths
1.140 + {
1.141 + Suurballe<ListGraph> suurballe(graph, length, source, target);
1.142 + check(suurballe.run(3) == 3, "Wrong number of paths");
1.143 + check(checkFlow(graph, suurballe.flowMap(), source, target, 3),
1.144 + "The flow is not feasible");
1.145 + check(suurballe.totalLength() == 1040, "The flow is not optimal");
1.146 + check(checkOptimality(graph, length, suurballe.flowMap(),
1.147 + suurballe.potentialMap()),
1.148 + "Wrong potentials");
1.149 + for (int i = 0; i < suurballe.pathNum(); ++i)
1.150 + check(checkPath(graph, suurballe.path(i), source, target),
1.151 + "Wrong path");
1.152 + }
1.153
1.154 - Graph::EdgeMap<int> length(graph);
1.155 + // Finding 5 paths (only 3 can be found)
1.156 + {
1.157 + Suurballe<ListGraph> suurballe(graph, length, source, target);
1.158 + check(suurballe.run(5) == 3, "Wrong number of paths");
1.159 + check(checkFlow(graph, suurballe.flowMap(), source, target, 3),
1.160 + "The flow is not feasible");
1.161 + check(suurballe.totalLength() == 1040, "The flow is not optimal");
1.162 + check(checkOptimality(graph, length, suurballe.flowMap(),
1.163 + suurballe.potentialMap()),
1.164 + "Wrong potentials");
1.165 + for (int i = 0; i < suurballe.pathNum(); ++i)
1.166 + check(checkPath(graph, suurballe.path(i), source, target),
1.167 + "Wrong path");
1.168 + }
1.169
1.170 - length.set(s_v1, 6);
1.171 - length.set(v1_v2, 4);
1.172 - length.set(s_v3, 10);
1.173 - length.set(v2_v4, 5);
1.174 - length.set(v2_v5, 1);
1.175 - length.set(v3_v5, 5);
1.176 - length.set(v4_t, 8);
1.177 - length.set(v5_t, 8);
1.178 -
1.179 - std::cout << "Minlengthpaths algorithm test..." << std::endl;
1.180 -
1.181 -
1.182 - int k=3;
1.183 - Suurballe< Graph, Graph::EdgeMap<int> >
1.184 - surb_test(graph, length, s, t);
1.185 -
1.186 - check( surb_test.run(k) == 2 && surb_test.totalLength() == 46,
1.187 - "Two paths, total length should be 46");
1.188 -
1.189 - check( surb_test.checkComplementarySlackness(),
1.190 - "Complementary slackness conditions are not met.");
1.191 -
1.192 - // typedef DirPath<Graph> DPath;
1.193 - // DPath P(graph);
1.194 -
1.195 - /*
1.196 - surb_test.getPath(P,0);
1.197 - check(P.length() == 4, "First path should contain 4 edges.");
1.198 - std::cout<<P.length()<<std::endl;
1.199 - surb_test.getPath(P,1);
1.200 - check(P.length() == 3, "Second path: 3 edges.");
1.201 - std::cout<<P.length()<<std::endl;
1.202 - */
1.203 -
1.204 - k=1;
1.205 - check( surb_test.run(k) == 1 && surb_test.totalLength() == 19,
1.206 - "One path, total length should be 19");
1.207 -
1.208 - check( surb_test.checkComplementarySlackness(),
1.209 - "Complementary slackness conditions are not met.");
1.210 -
1.211 - // surb_test.getPath(P,0);
1.212 - // check(P.length() == 4, "First path should contain 4 edges.");
1.213 -
1.214 - std::cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
1.215 - << std::endl;
1.216 -
1.217 - return passed ? 0 : 1;
1.218 -
1.219 + return 0;
1.220 }