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

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/suurballe.h
r584 r623 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 ///
Note: See TracChangeset
for help on using the changeset viewer.