1.1 --- a/test/suurballe_test.cc Sat Apr 25 18:25:59 2009 +0200
1.2 +++ b/test/suurballe_test.cc Sat Apr 25 02:12:41 2009 +0200
1.3 @@ -22,6 +22,7 @@
1.4 #include <lemon/lgf_reader.h>
1.5 #include <lemon/path.h>
1.6 #include <lemon/suurballe.h>
1.7 +#include <lemon/concepts/digraph.h>
1.8
1.9 #include "test_tools.h"
1.10
1.11 @@ -29,47 +30,97 @@
1.12
1.13 char test_lgf[] =
1.14 "@nodes\n"
1.15 - "label supply1 supply2 supply3\n"
1.16 - "1 0 20 27\n"
1.17 - "2 0 -4 0\n"
1.18 - "3 0 0 0\n"
1.19 - "4 0 0 0\n"
1.20 - "5 0 9 0\n"
1.21 - "6 0 -6 0\n"
1.22 - "7 0 0 0\n"
1.23 - "8 0 0 0\n"
1.24 - "9 0 3 0\n"
1.25 - "10 0 -2 0\n"
1.26 - "11 0 0 0\n"
1.27 - "12 0 -20 -27\n"
1.28 + "label\n"
1.29 + "1\n"
1.30 + "2\n"
1.31 + "3\n"
1.32 + "4\n"
1.33 + "5\n"
1.34 + "6\n"
1.35 + "7\n"
1.36 + "8\n"
1.37 + "9\n"
1.38 + "10\n"
1.39 + "11\n"
1.40 + "12\n"
1.41 "@arcs\n"
1.42 - " cost capacity lower1 lower2\n"
1.43 - " 1 2 70 11 0 8\n"
1.44 - " 1 3 150 3 0 1\n"
1.45 - " 1 4 80 15 0 2\n"
1.46 - " 2 8 80 12 0 0\n"
1.47 - " 3 5 140 5 0 3\n"
1.48 - " 4 6 60 10 0 1\n"
1.49 - " 4 7 80 2 0 0\n"
1.50 - " 4 8 110 3 0 0\n"
1.51 - " 5 7 60 14 0 0\n"
1.52 - " 5 11 120 12 0 0\n"
1.53 - " 6 3 0 3 0 0\n"
1.54 - " 6 9 140 4 0 0\n"
1.55 - " 6 10 90 8 0 0\n"
1.56 - " 7 1 30 5 0 0\n"
1.57 - " 8 12 60 16 0 4\n"
1.58 - " 9 12 50 6 0 0\n"
1.59 - "10 12 70 13 0 5\n"
1.60 - "10 2 100 7 0 0\n"
1.61 - "10 7 60 10 0 0\n"
1.62 - "11 10 20 14 0 6\n"
1.63 - "12 11 30 10 0 0\n"
1.64 + " length\n"
1.65 + " 1 2 70\n"
1.66 + " 1 3 150\n"
1.67 + " 1 4 80\n"
1.68 + " 2 8 80\n"
1.69 + " 3 5 140\n"
1.70 + " 4 6 60\n"
1.71 + " 4 7 80\n"
1.72 + " 4 8 110\n"
1.73 + " 5 7 60\n"
1.74 + " 5 11 120\n"
1.75 + " 6 3 0\n"
1.76 + " 6 9 140\n"
1.77 + " 6 10 90\n"
1.78 + " 7 1 30\n"
1.79 + " 8 12 60\n"
1.80 + " 9 12 50\n"
1.81 + "10 12 70\n"
1.82 + "10 2 100\n"
1.83 + "10 7 60\n"
1.84 + "11 10 20\n"
1.85 + "12 11 30\n"
1.86 "@attributes\n"
1.87 "source 1\n"
1.88 "target 12\n"
1.89 "@end\n";
1.90
1.91 +// Check the interface of Suurballe
1.92 +void checkSuurballeCompile()
1.93 +{
1.94 + typedef int VType;
1.95 + typedef concepts::Digraph Digraph;
1.96 +
1.97 + typedef Digraph::Node Node;
1.98 + typedef Digraph::Arc Arc;
1.99 + typedef concepts::ReadMap<Arc, VType> LengthMap;
1.100 +
1.101 + typedef Suurballe<Digraph, LengthMap> SuurballeType;
1.102 +
1.103 + Digraph g;
1.104 + Node n;
1.105 + Arc e;
1.106 + LengthMap len;
1.107 + SuurballeType::FlowMap flow(g);
1.108 + SuurballeType::PotentialMap pi(g);
1.109 +
1.110 + SuurballeType suurb_test(g, len);
1.111 + const SuurballeType& const_suurb_test = suurb_test;
1.112 +
1.113 + suurb_test
1.114 + .flowMap(flow)
1.115 + .potentialMap(pi);
1.116 +
1.117 + int k;
1.118 + k = suurb_test.run(n, n);
1.119 + k = suurb_test.run(n, n, k);
1.120 + suurb_test.init(n);
1.121 + k = suurb_test.findFlow(n);
1.122 + k = suurb_test.findFlow(n, k);
1.123 + suurb_test.findPaths();
1.124 +
1.125 + int f;
1.126 + VType c;
1.127 + c = const_suurb_test.totalLength();
1.128 + f = const_suurb_test.flow(e);
1.129 + const SuurballeType::FlowMap& fm =
1.130 + const_suurb_test.flowMap();
1.131 + c = const_suurb_test.potential(n);
1.132 + const SuurballeType::PotentialMap& pm =
1.133 + const_suurb_test.potentialMap();
1.134 + k = const_suurb_test.pathNum();
1.135 + Path<Digraph> p = const_suurb_test.path(k);
1.136 +
1.137 + ignore_unused_variable_warning(fm);
1.138 + ignore_unused_variable_warning(pm);
1.139 +}
1.140 +
1.141 // Check the feasibility of the flow
1.142 template <typename Digraph, typename FlowMap>
1.143 bool checkFlow( const Digraph& gr, const FlowMap& flow,
1.144 @@ -118,7 +169,6 @@
1.145 bool checkPath( const Digraph& gr, const Path& path,
1.146 typename Digraph::Node s, typename Digraph::Node t)
1.147 {
1.148 - // Check the "Complementary Slackness" optimality condition
1.149 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
1.150 Node n = s;
1.151 for (int i = 0; i < path.length(); ++i) {
1.152 @@ -136,58 +186,55 @@
1.153 // Read the test digraph
1.154 ListDigraph digraph;
1.155 ListDigraph::ArcMap<int> length(digraph);
1.156 - Node source, target;
1.157 + Node s, t;
1.158
1.159 std::istringstream input(test_lgf);
1.160 DigraphReader<ListDigraph>(digraph, input).
1.161 - arcMap("cost", length).
1.162 - node("source", source).
1.163 - node("target", target).
1.164 + arcMap("length", length).
1.165 + node("source", s).
1.166 + node("target", t).
1.167 run();
1.168
1.169 // Find 2 paths
1.170 {
1.171 - Suurballe<ListDigraph> suurballe(digraph, length, source, target);
1.172 - check(suurballe.run(2) == 2, "Wrong number of paths");
1.173 - check(checkFlow(digraph, suurballe.flowMap(), source, target, 2),
1.174 + Suurballe<ListDigraph> suurballe(digraph, length);
1.175 + check(suurballe.run(s, t) == 2, "Wrong number of paths");
1.176 + check(checkFlow(digraph, suurballe.flowMap(), s, t, 2),
1.177 "The flow is not feasible");
1.178 check(suurballe.totalLength() == 510, "The flow is not optimal");
1.179 check(checkOptimality(digraph, length, suurballe.flowMap(),
1.180 suurballe.potentialMap()),
1.181 "Wrong potentials");
1.182 for (int i = 0; i < suurballe.pathNum(); ++i)
1.183 - check(checkPath(digraph, suurballe.path(i), source, target),
1.184 - "Wrong path");
1.185 + check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
1.186 }
1.187
1.188 // Find 3 paths
1.189 {
1.190 - Suurballe<ListDigraph> suurballe(digraph, length, source, target);
1.191 - check(suurballe.run(3) == 3, "Wrong number of paths");
1.192 - check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
1.193 + Suurballe<ListDigraph> suurballe(digraph, length);
1.194 + check(suurballe.run(s, t, 3) == 3, "Wrong number of paths");
1.195 + check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
1.196 "The flow is not feasible");
1.197 check(suurballe.totalLength() == 1040, "The flow is not optimal");
1.198 check(checkOptimality(digraph, length, suurballe.flowMap(),
1.199 suurballe.potentialMap()),
1.200 "Wrong potentials");
1.201 for (int i = 0; i < suurballe.pathNum(); ++i)
1.202 - check(checkPath(digraph, suurballe.path(i), source, target),
1.203 - "Wrong path");
1.204 + check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
1.205 }
1.206
1.207 // Find 5 paths (only 3 can be found)
1.208 {
1.209 - Suurballe<ListDigraph> suurballe(digraph, length, source, target);
1.210 - check(suurballe.run(5) == 3, "Wrong number of paths");
1.211 - check(checkFlow(digraph, suurballe.flowMap(), source, target, 3),
1.212 + Suurballe<ListDigraph> suurballe(digraph, length);
1.213 + check(suurballe.run(s, t, 5) == 3, "Wrong number of paths");
1.214 + check(checkFlow(digraph, suurballe.flowMap(), s, t, 3),
1.215 "The flow is not feasible");
1.216 check(suurballe.totalLength() == 1040, "The flow is not optimal");
1.217 check(checkOptimality(digraph, length, suurballe.flowMap(),
1.218 suurballe.potentialMap()),
1.219 "Wrong potentials");
1.220 for (int i = 0; i < suurballe.pathNum(); ++i)
1.221 - check(checkPath(digraph, suurballe.path(i), source, target),
1.222 - "Wrong path");
1.223 + check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path");
1.224 }
1.225
1.226 return 0;