Changeset 623:7c1324b35d89 in lemon1.2 for test/suurballe_test.cc
 Timestamp:
 04/25/09 02:12:41 (10 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

test/suurballe_test.cc
r440 r623 23 23 #include <lemon/path.h> 24 24 #include <lemon/suurballe.h> 25 #include <lemon/concepts/digraph.h> 25 26 26 27 #include "test_tools.h" … … 30 31 char test_lgf[] = 31 32 "@nodes\n" 32 "label supply1 supply2 supply3\n"33 "1 0 20 27\n"34 "2 0 4 0\n"35 "3 0 0 0\n"36 "4 0 0 0\n"37 "5 0 9 0\n"38 "6 0 6 0\n"39 "7 0 0 0\n"40 "8 0 0 0\n"41 "9 0 3 0\n"42 "10 0 2 0\n"43 "11 0 0 0\n"44 "12 0 20 27\n"33 "label\n" 34 "1\n" 35 "2\n" 36 "3\n" 37 "4\n" 38 "5\n" 39 "6\n" 40 "7\n" 41 "8\n" 42 "9\n" 43 "10\n" 44 "11\n" 45 "12\n" 45 46 "@arcs\n" 46 " cost capacity lower1 lower2\n"47 " 1 2 70 11 0 8\n"48 " 1 3 150 3 0 1\n"49 " 1 4 80 15 0 2\n"50 " 2 8 80 12 0 0\n"51 " 3 5 140 5 0 3\n"52 " 4 6 60 10 0 1\n"53 " 4 7 80 2 0 0\n"54 " 4 8 110 3 0 0\n"55 " 5 7 60 14 0 0\n"56 " 5 11 120 12 0 0\n"57 " 6 3 0 3 0 0\n"58 " 6 9 140 4 0 0\n"59 " 6 10 90 8 0 0\n"60 " 7 1 30 5 0 0\n"61 " 8 12 60 16 0 4\n"62 " 9 12 50 6 0 0\n"63 "10 12 70 13 0 5\n"64 "10 2 100 7 0 0\n"65 "10 7 60 10 0 0\n"66 "11 10 20 14 0 6\n"67 "12 11 30 10 0 0\n"47 " length\n" 48 " 1 2 70\n" 49 " 1 3 150\n" 50 " 1 4 80\n" 51 " 2 8 80\n" 52 " 3 5 140\n" 53 " 4 6 60\n" 54 " 4 7 80\n" 55 " 4 8 110\n" 56 " 5 7 60\n" 57 " 5 11 120\n" 58 " 6 3 0\n" 59 " 6 9 140\n" 60 " 6 10 90\n" 61 " 7 1 30\n" 62 " 8 12 60\n" 63 " 9 12 50\n" 64 "10 12 70\n" 65 "10 2 100\n" 66 "10 7 60\n" 67 "11 10 20\n" 68 "12 11 30\n" 68 69 "@attributes\n" 69 70 "source 1\n" 70 71 "target 12\n" 71 72 "@end\n"; 73 74 // Check the interface of Suurballe 75 void checkSuurballeCompile() 76 { 77 typedef int VType; 78 typedef concepts::Digraph Digraph; 79 80 typedef Digraph::Node Node; 81 typedef Digraph::Arc Arc; 82 typedef concepts::ReadMap<Arc, VType> LengthMap; 83 84 typedef Suurballe<Digraph, LengthMap> SuurballeType; 85 86 Digraph g; 87 Node n; 88 Arc e; 89 LengthMap len; 90 SuurballeType::FlowMap flow(g); 91 SuurballeType::PotentialMap pi(g); 92 93 SuurballeType suurb_test(g, len); 94 const SuurballeType& const_suurb_test = suurb_test; 95 96 suurb_test 97 .flowMap(flow) 98 .potentialMap(pi); 99 100 int k; 101 k = suurb_test.run(n, n); 102 k = suurb_test.run(n, n, k); 103 suurb_test.init(n); 104 k = suurb_test.findFlow(n); 105 k = suurb_test.findFlow(n, k); 106 suurb_test.findPaths(); 107 108 int f; 109 VType c; 110 c = const_suurb_test.totalLength(); 111 f = const_suurb_test.flow(e); 112 const SuurballeType::FlowMap& fm = 113 const_suurb_test.flowMap(); 114 c = const_suurb_test.potential(n); 115 const SuurballeType::PotentialMap& pm = 116 const_suurb_test.potentialMap(); 117 k = const_suurb_test.pathNum(); 118 Path<Digraph> p = const_suurb_test.path(k); 119 120 ignore_unused_variable_warning(fm); 121 ignore_unused_variable_warning(pm); 122 } 72 123 73 124 // Check the feasibility of the flow … … 119 170 typename Digraph::Node s, typename Digraph::Node t) 120 171 { 121 // Check the "Complementary Slackness" optimality condition122 172 TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); 123 173 Node n = s; … … 137 187 ListDigraph digraph; 138 188 ListDigraph::ArcMap<int> length(digraph); 139 Node s ource, target;189 Node s, t; 140 190 141 191 std::istringstream input(test_lgf); 142 192 DigraphReader<ListDigraph>(digraph, input). 143 arcMap(" cost", length).144 node("source", s ource).145 node("target", t arget).193 arcMap("length", length). 194 node("source", s). 195 node("target", t). 146 196 run(); 147 197 148 198 // Find 2 paths 149 199 { 150 Suurballe<ListDigraph> suurballe(digraph, length , source, target);151 check(suurballe.run( 2) == 2, "Wrong number of paths");152 check(checkFlow(digraph, suurballe.flowMap(), s ource, target, 2),200 Suurballe<ListDigraph> suurballe(digraph, length); 201 check(suurballe.run(s, t) == 2, "Wrong number of paths"); 202 check(checkFlow(digraph, suurballe.flowMap(), s, t, 2), 153 203 "The flow is not feasible"); 154 204 check(suurballe.totalLength() == 510, "The flow is not optimal"); … … 157 207 "Wrong potentials"); 158 208 for (int i = 0; i < suurballe.pathNum(); ++i) 159 check(checkPath(digraph, suurballe.path(i), source, target), 160 "Wrong path"); 209 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); 161 210 } 162 211 163 212 // Find 3 paths 164 213 { 165 Suurballe<ListDigraph> suurballe(digraph, length , source, target);166 check(suurballe.run( 3) == 3, "Wrong number of paths");167 check(checkFlow(digraph, suurballe.flowMap(), s ource, target, 3),214 Suurballe<ListDigraph> suurballe(digraph, length); 215 check(suurballe.run(s, t, 3) == 3, "Wrong number of paths"); 216 check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), 168 217 "The flow is not feasible"); 169 218 check(suurballe.totalLength() == 1040, "The flow is not optimal"); … … 172 221 "Wrong potentials"); 173 222 for (int i = 0; i < suurballe.pathNum(); ++i) 174 check(checkPath(digraph, suurballe.path(i), source, target), 175 "Wrong path"); 223 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); 176 224 } 177 225 178 226 // Find 5 paths (only 3 can be found) 179 227 { 180 Suurballe<ListDigraph> suurballe(digraph, length , source, target);181 check(suurballe.run( 5) == 3, "Wrong number of paths");182 check(checkFlow(digraph, suurballe.flowMap(), s ource, target, 3),228 Suurballe<ListDigraph> suurballe(digraph, length); 229 check(suurballe.run(s, t, 5) == 3, "Wrong number of paths"); 230 check(checkFlow(digraph, suurballe.flowMap(), s, t, 3), 183 231 "The flow is not feasible"); 184 232 check(suurballe.totalLength() == 1040, "The flow is not optimal"); … … 187 235 "Wrong potentials"); 188 236 for (int i = 0; i < suurballe.pathNum(); ++i) 189 check(checkPath(digraph, suurballe.path(i), source, target), 190 "Wrong path"); 237 check(checkPath(digraph, suurballe.path(i), s, t), "Wrong path"); 191 238 } 192 239
Note: See TracChangeset
for help on using the changeset viewer.