36 namespace lemon { |
36 namespace lemon { |
37 |
37 |
38 /// \brief Default OperationTraits for the BellmanFord algorithm class. |
38 /// \brief Default OperationTraits for the BellmanFord algorithm class. |
39 /// |
39 /// |
40 /// It defines all computational operations and constants which are |
40 /// It defines all computational operations and constants which are |
41 /// used in the bellman ford algorithm. The default implementation |
41 /// used in the Bellman-Ford algorithm. The default implementation |
42 /// is based on the numeric_limits class. If the numeric type does not |
42 /// is based on the numeric_limits class. If the numeric type does not |
43 /// have infinity value then the maximum value is used as extremal |
43 /// have infinity value then the maximum value is used as extremal |
44 /// infinity value. |
44 /// infinity value. |
45 template < |
45 template < |
46 typename Value, |
46 typename Value, |
98 typedef _LengthMap LengthMap; |
98 typedef _LengthMap LengthMap; |
99 |
99 |
100 // The type of the length of the edges. |
100 // The type of the length of the edges. |
101 typedef typename _LengthMap::Value Value; |
101 typedef typename _LengthMap::Value Value; |
102 |
102 |
103 /// \brief Operation traits for bellman-ford algorithm. |
103 /// \brief Operation traits for Bellman-Ford algorithm. |
104 /// |
104 /// |
105 /// It defines the infinity type on the given Value type |
105 /// It defines the infinity type on the given Value type |
106 /// and the used operation. |
106 /// and the used operation. |
107 /// \see BellmanFordDefaultOperationTraits |
107 /// \see BellmanFordDefaultOperationTraits |
108 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; |
108 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; |
408 } |
408 } |
409 } |
409 } |
410 |
410 |
411 /// \brief Adds a new source node. |
411 /// \brief Adds a new source node. |
412 /// |
412 /// |
413 /// The optional second parameter is the initial distance of the node. |
413 /// Adds a new source node. The optional second parameter is the |
414 /// It just sets the distance of the node to the given value. |
414 /// initial distance of the node. It just sets the distance of the |
|
415 /// node to the given value. |
415 void addSource(Node source, Value dst = OperationTraits::zero()) { |
416 void addSource(Node source, Value dst = OperationTraits::zero()) { |
416 _dist->set(source, dst); |
417 _dist->set(source, dst); |
417 if (!(*_mask)[source]) { |
418 if (!(*_mask)[source]) { |
418 _process.push_back(source); |
419 _process.push_back(source); |
419 _mask->set(source, true); |
420 _mask->set(source, true); |
420 } |
421 } |
421 } |
422 } |
422 |
423 |
423 /// \brief Executes one round from the bellman ford algorithm. |
424 /// \brief Executes one round from the Bellman-Ford algorithm. |
424 /// |
425 /// |
425 /// If the algoritm calculated the distances in the previous round |
426 /// If the algoritm calculated the distances in the previous round |
426 /// exactly for all at most \f$ k \f$ length path lengths then it will |
427 /// exactly for all at most \f$ k \f$ length path lengths then it will |
427 /// calculate the distances exactly for all at most \f$ k + 1 \f$ |
428 /// calculate the distances exactly for all at most \f$ k + 1 \f$ |
428 /// length path lengths. With \f$ k \f$ iteration this function |
429 /// length path lengths. With \f$ k \f$ iteration this function |
461 } |
462 } |
462 _process.swap(nextProcess); |
463 _process.swap(nextProcess); |
463 return _process.empty(); |
464 return _process.empty(); |
464 } |
465 } |
465 |
466 |
466 /// \brief Executes one weak round from the bellman ford algorithm. |
467 /// \brief Executes one weak round from the Bellman-Ford algorithm. |
467 /// |
468 /// |
468 /// If the algorithm calculated the distances in the |
469 /// If the algorithm calculated the distances in the |
469 /// previous round at least for all at most k length paths then it will |
470 /// previous round at least for all at most k length paths then it will |
470 /// calculate the distances at least for all at most k + 1 length paths. |
471 /// calculate the distances at least for all at most k + 1 length paths. |
471 /// This function does not make it possible to calculate strictly the |
472 /// This function does not make it possible to calculate strictly the |
515 |
516 |
516 /// \brief Executes the algorithm and checks the negative cycles. |
517 /// \brief Executes the algorithm and checks the negative cycles. |
517 /// |
518 /// |
518 /// \pre init() must be called and at least one node should be added |
519 /// \pre init() must be called and at least one node should be added |
519 /// with addSource() before using this function. If there is |
520 /// with addSource() before using this function. If there is |
520 /// a negative cycles in the graph it gives back false. |
521 /// a negative cycle in the graph it gives back false. |
521 /// |
522 /// |
522 /// This method runs the %BellmanFord algorithm from the root node(s) |
523 /// This method runs the %BellmanFord algorithm from the root node(s) |
523 /// in order to compute the shortest path to each node. The algorithm |
524 /// in order to compute the shortest path to each node. The algorithm |
524 /// computes |
525 /// computes |
525 /// - The shortest path tree. |
526 /// - The shortest path tree. |
605 /// Before the use of these functions, |
606 /// Before the use of these functions, |
606 /// either run() or start() must be called. |
607 /// either run() or start() must be called. |
607 |
608 |
608 ///@{ |
609 ///@{ |
609 |
610 |
610 /// \brief Lemon iterator for get a active nodes. |
611 /// \brief Lemon iterator for get the active nodes. |
611 /// |
612 /// |
612 /// Lemon iterator for get the active nodes. This class provides a |
613 /// Lemon iterator for get the active nodes. This class provides a |
613 /// common style lemon iterator which gives back a subset of the |
614 /// common style lemon iterator which gives back a subset of the |
614 /// nodes. The iterated nodes are active in the algorithm after |
615 /// nodes. The iterated nodes are active in the algorithm after |
615 /// the last phase so these should be checked in the next phase to |
616 /// the last phase so these should be checked in the next phase to |
782 typedef _LengthMap LengthMap; |
783 typedef _LengthMap LengthMap; |
783 |
784 |
784 /// \brief The value type of the length map. |
785 /// \brief The value type of the length map. |
785 typedef typename _LengthMap::Value Value; |
786 typedef typename _LengthMap::Value Value; |
786 |
787 |
787 /// \brief Operation traits for bellman-ford algorithm. |
788 /// \brief Operation traits for Bellman-Ford algorithm. |
788 /// |
789 /// |
789 /// It defines the infinity type on the given Value type |
790 /// It defines the infinity type on the given Value type |
790 /// and the used operation. |
791 /// and the used operation. |
791 /// \see BellmanFordDefaultOperationTraits |
792 /// \see BellmanFordDefaultOperationTraits |
792 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; |
793 typedef BellmanFordDefaultOperationTraits<Value> OperationTraits; |