Changeset 670:7c1324b35d89 in lemon
 Timestamp:
 04/25/09 02:12:41 (13 years ago)
 Branch:
 default
 Phase:
 public
 Files:

 3 edited
Legend:
 Unmodified
 Added
 Removed

lemon/suurballe.h
r631 r670 26 26 27 27 #include <vector> 28 #include <limits> 28 29 #include <lemon/bin_heap.h> 29 30 #include <lemon/path.h> … … 43 44 /// from a given source node to a given target node in a digraph. 44 45 /// 45 /// In fact, this implementation is the specialization of the 46 /// \ref CapacityScaling "successive shortest path" algorithm. 46 /// Note that this problem is a special case of the \ref min_cost_flow 47 /// "minimum cost flow problem". This implementation is actually an 48 /// efficient specialized version of the \ref CapacityScaling 49 /// "Successive Shortest Path" algorithm directly for this problem. 50 /// Therefore this class provides query functions for flow values and 51 /// node potentials (the dual solution) just like the minimum cost flow 52 /// algorithms. 47 53 /// 48 54 /// \tparam GR The digraph type the algorithm runs on. 49 /// The default value is \c ListDigraph. 50 /// \tparam LEN The type of the length (cost) map. 51 /// The default value is <tt>Digraph::ArcMap<int></tt>. 55 /// \tparam LEN The type of the length map. 56 /// The default value is <tt>GR::ArcMap<int></tt>. 52 57 /// 53 58 /// \warning Length values should be \e nonnegative \e integers. 54 59 /// 55 60 /// \note For finding nodedisjoint paths this algorithm can be used 56 /// with \ref SplitNodes.61 /// along with the \ref SplitNodes adaptor. 57 62 #ifdef DOXYGEN 58 63 template <typename GR, typename LEN> 59 64 #else 60 template < typename GR = ListDigraph,65 template < typename GR, 61 66 typename LEN = typename GR::template ArcMap<int> > 62 67 #endif … … 76 81 /// The type of the lengths. 77 82 typedef typename LengthMap::Value Length; 83 #ifdef DOXYGEN 84 /// The type of the flow map. 85 typedef GR::ArcMap<int> FlowMap; 86 /// The type of the potential map. 87 typedef GR::NodeMap<Length> PotentialMap; 88 #else 78 89 /// The type of the flow map. 79 90 typedef typename Digraph::template ArcMap<int> FlowMap; 80 91 /// The type of the potential map. 81 92 typedef typename Digraph::template NodeMap<Length> PotentialMap; 93 #endif 94 82 95 /// The type of the path structures. 83 typedef SimplePath< Digraph> Path;96 typedef SimplePath<GR> Path; 84 97 85 98 private: 86 99 87 /// \brief Special implementation of the Dijkstra algorithm 88 /// for finding shortest paths in the residual network. 89 /// 90 /// \ref ResidualDijkstra is a special implementation of the 91 /// \ref Dijkstra algorithm for finding shortest paths in the 92 /// residual network of the digraph with respect to the reduced arc 93 /// lengths and modifying the node potentials according to the 94 /// distance of the nodes. 100 // ResidualDijkstra is a special implementation of the 101 // Dijkstra algorithm for finding shortest paths in the 102 // residual network with respect to the reduced arc lengths 103 // and modifying the node potentials according to the 104 // distance of the nodes. 95 105 class ResidualDijkstra 96 106 { … … 121 131 122 132 /// Constructor. 123 ResidualDijkstra( const Digraph & digraph,133 ResidualDijkstra( const Digraph &graph, 124 134 const FlowMap &flow, 125 135 const LengthMap &length, … … 127 137 PredMap &pred, 128 138 Node s, Node t ) : 129 _graph( digraph), _flow(flow), _length(length), _potential(potential),130 _dist( digraph), _pred(pred), _s(s), _t(t) {}139 _graph(graph), _flow(flow), _length(length), _potential(potential), 140 _dist(graph), _pred(pred), _s(s), _t(t) {} 131 141 132 142 /// \brief Run the algorithm. It returns \c true if a path is found … … 237 247 /// Constructor. 238 248 /// 239 /// \param digraph The digraph the algorithm runs on.249 /// \param graph The digraph the algorithm runs on. 240 250 /// \param length The length (cost) values of the arcs. 241 /// \param s The source node.242 /// \param t The target node.243 Suurballe( const Digraph &digraph,244 const LengthMap &length,245 Node s, Node t ) :246 _graph(digraph), _length(length), _flow(0), _local_flow(false),247 _potential(0), _local_potential(false), _source(s), _target(t),248 _pred(digraph) {}251 Suurballe( const Digraph &graph, 252 const LengthMap &length ) : 253 _graph(graph), _length(length), _flow(0), _local_flow(false), 254 _potential(0), _local_potential(false), _pred(graph) 255 { 256 LEMON_ASSERT(std::numeric_limits<Length>::is_integer, 257 "The length type of Suurballe must be integer"); 258 } 249 259 250 260 /// Destructor. … … 258 268 /// 259 269 /// This function sets the flow map. 260 /// 261 /// The found flow contains only 0 and 1 values. It is the union of 262 /// the found arcdisjoint paths. 270 /// If it is not used before calling \ref run() or \ref init(), 271 /// an instance will be allocated automatically. The destructor 272 /// deallocates this automatically allocated map, of course. 273 /// 274 /// The found flow contains only 0 and 1 values, since it is the 275 /// union of the found arcdisjoint paths. 263 276 /// 264 277 /// \return <tt>(*this)</tt> … … 275 288 /// 276 289 /// This function sets the potential map. 277 /// 278 /// The potentials provide the dual solution of the underlying 279 /// minimum cost flow problem. 290 /// If it is not used before calling \ref run() or \ref init(), 291 /// an instance will be allocated automatically. The destructor 292 /// deallocates this automatically allocated map, of course. 293 /// 294 /// The node potentials provide the dual solution of the underlying 295 /// \ref min_cost_flow "minimum cost flow problem". 280 296 /// 281 297 /// \return <tt>(*this)</tt> … … 302 318 /// This function runs the algorithm. 303 319 /// 320 /// \param s The source node. 321 /// \param t The target node. 304 322 /// \param k The number of paths to be found. 305 323 /// … … 308 326 /// arcdisjoint paths found. 309 327 /// 310 /// \note Apart from the return value, <tt>s.run( k)</tt> is just a311 /// shortcut of the following code.328 /// \note Apart from the return value, <tt>s.run(s, t, k)</tt> is 329 /// just a shortcut of the following code. 312 330 /// \code 313 /// s.init( );314 /// s.findFlow( k);331 /// s.init(s); 332 /// s.findFlow(t, k); 315 333 /// s.findPaths(); 316 334 /// \endcode 317 int run( int k = 2) {318 init( );319 findFlow( k);335 int run(const Node& s, const Node& t, int k = 2) { 336 init(s); 337 findFlow(t, k); 320 338 findPaths(); 321 339 return _path_num; … … 325 343 /// 326 344 /// This function initializes the algorithm. 327 void init() { 345 /// 346 /// \param s The source node. 347 void init(const Node& s) { 348 _source = s; 349 328 350 // Initialize maps 329 351 if (!_flow) { … … 337 359 for (ArcIt e(_graph); e != INVALID; ++e) (*_flow)[e] = 0; 338 360 for (NodeIt n(_graph); n != INVALID; ++n) (*_potential)[n] = 0; 339 340 _dijkstra = new ResidualDijkstra( _graph, *_flow, _length, 341 *_potential, _pred, 342 _source, _target ); 343 } 344 345 /// \brief Execute the successive shortest path algorithm to find 346 /// an optimal flow. 361 } 362 363 /// \brief Execute the algorithm to find an optimal flow. 347 364 /// 348 365 /// This function executes the successive shortest path algorithm to 349 /// find a minimum cost flow, which is the union of \c k or less366 /// find a minimum cost flow, which is the union of \c k (or less) 350 367 /// arcdisjoint paths. 351 368 /// 369 /// \param t The target node. 370 /// \param k The number of paths to be found. 371 /// 352 372 /// \return \c k if there are at least \c k arcdisjoint paths from 353 /// \c s to \c t in the digraph. Otherwise it returns the number of354 /// arcdisjoint paths found.373 /// the source node to the given node \c t in the digraph. 374 /// Otherwise it returns the number of arcdisjoint paths found. 355 375 /// 356 376 /// \pre \ref init() must be called before using this function. 357 int findFlow(int k = 2) { 377 int findFlow(const Node& t, int k = 2) { 378 _target = t; 379 _dijkstra = 380 new ResidualDijkstra( _graph, *_flow, _length, *_potential, _pred, 381 _source, _target ); 382 358 383 // Find shortest paths 359 384 _path_num = 0; … … 381 406 /// \brief Compute the paths from the flow. 382 407 /// 383 /// This function computes the paths from the flow. 408 /// This function computes the paths from the found minimum cost flow, 409 /// which is the union of some arcdisjoint paths. 384 410 /// 385 411 /// \pre \ref init() and \ref findFlow() must be called before using 386 412 /// this function. 387 413 void findPaths() { 388 // Create the residual flow map (the union of the paths not found389 // so far)390 414 FlowMap res_flow(_graph); 391 415 for(ArcIt a(_graph); a != INVALID; ++a) res_flow[a] = (*_flow)[a]; … … 414 438 /// @{ 415 439 416 /// \brief Return a const reference to the arc map storing the 417 /// found flow. 418 /// 419 /// This function returns a const reference to the arc map storing 420 /// the flow that is the union of the found arcdisjoint paths. 421 /// 422 /// \pre \ref run() or \ref findFlow() must be called before using 423 /// this function. 424 const FlowMap& flowMap() const { 425 return *_flow; 426 } 427 428 /// \brief Return a const reference to the node map storing the 429 /// found potentials (the dual solution). 430 /// 431 /// This function returns a const reference to the node map storing 432 /// the found potentials that provide the dual solution of the 433 /// underlying minimum cost flow problem. 434 /// 435 /// \pre \ref run() or \ref findFlow() must be called before using 436 /// this function. 437 const PotentialMap& potentialMap() const { 438 return *_potential; 439 } 440 441 /// \brief Return the flow on the given arc. 442 /// 443 /// This function returns the flow on the given arc. 444 /// It is \c 1 if the arc is involved in one of the found paths, 445 /// otherwise it is \c 0. 446 /// 447 /// \pre \ref run() or \ref findFlow() must be called before using 448 /// this function. 449 int flow(const Arc& arc) const { 450 return (*_flow)[arc]; 451 } 452 453 /// \brief Return the potential of the given node. 454 /// 455 /// This function returns the potential of the given node. 456 /// 457 /// \pre \ref run() or \ref findFlow() must be called before using 458 /// this function. 459 Length potential(const Node& node) const { 460 return (*_potential)[node]; 461 } 462 463 /// \brief Return the total length (cost) of the found paths (flow). 464 /// 465 /// This function returns the total length (cost) of the found paths 466 /// (flow). The complexity of the function is O(e). 440 /// \brief Return the total length of the found paths. 441 /// 442 /// This function returns the total length of the found paths, i.e. 443 /// the total cost of the found flow. 444 /// The complexity of the function is O(e). 467 445 /// 468 446 /// \pre \ref run() or \ref findFlow() must be called before using … … 475 453 } 476 454 455 /// \brief Return the flow value on the given arc. 456 /// 457 /// This function returns the flow value on the given arc. 458 /// It is \c 1 if the arc is involved in one of the found arcdisjoint 459 /// paths, otherwise it is \c 0. 460 /// 461 /// \pre \ref run() or \ref findFlow() must be called before using 462 /// this function. 463 int flow(const Arc& arc) const { 464 return (*_flow)[arc]; 465 } 466 467 /// \brief Return a const reference to an arc map storing the 468 /// found flow. 469 /// 470 /// This function returns a const reference to an arc map storing 471 /// the flow that is the union of the found arcdisjoint paths. 472 /// 473 /// \pre \ref run() or \ref findFlow() must be called before using 474 /// this function. 475 const FlowMap& flowMap() const { 476 return *_flow; 477 } 478 479 /// \brief Return the potential of the given node. 480 /// 481 /// This function returns the potential of the given node. 482 /// The node potentials provide the dual solution of the 483 /// underlying \ref min_cost_flow "minimum cost flow problem". 484 /// 485 /// \pre \ref run() or \ref findFlow() must be called before using 486 /// this function. 487 Length potential(const Node& node) const { 488 return (*_potential)[node]; 489 } 490 491 /// \brief Return a const reference to a node map storing the 492 /// found potentials (the dual solution). 493 /// 494 /// This function returns a const reference to a node map storing 495 /// the found potentials that provide the dual solution of the 496 /// underlying \ref min_cost_flow "minimum cost flow problem". 497 /// 498 /// \pre \ref run() or \ref findFlow() must be called before using 499 /// this function. 500 const PotentialMap& potentialMap() const { 501 return *_potential; 502 } 503 477 504 /// \brief Return the number of the found paths. 478 505 /// … … 489 516 /// This function returns a const reference to the specified path. 490 517 /// 491 /// \param i The function returns the \c ith path.518 /// \param i The function returns the <tt>i</tt>th path. 492 519 /// \c i must be between \c 0 and <tt>%pathNum()1</tt>. 493 520 /// 
test/suurballe_test.cc
r463 r670 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 
tools/lgfgen.cc
r663 r670 481 481 g.erase(*ei); 482 482 ConstMap<Arc,int> cegy(1); 483 Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy ,a,b);484 int k=sur.run( 2);483 Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy); 484 int k=sur.run(a,b,2); 485 485 if(k<2  sur.totalLength()>d) 486 486 g.addEdge(a,b); … … 512 512 if(e==INVALID) { 513 513 ConstMap<Arc,int> cegy(1); 514 Suurballe<ListGraph,ConstMap<Arc,int> > 515 sur(g,cegy,pi>a,pi>b); 516 int k=sur.run(2); 514 Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy); 515 int k=sur.run(pi>a,pi>b,2); 517 516 if(k<2  sur.totalLength()>d) 518 517 {
Note: See TracChangeset
for help on using the changeset viewer.