Changeset 2070:1287ef6c180f in lemon0.x for lemon/bellman_ford.h
 Timestamp:
 05/08/06 19:03:52 (14 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2730
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bellman_ford.h
r2059 r2070 606 606 ///@{ 607 607 608 /// \brief Lemon iterator for get a active nodes. 609 /// 610 /// Lemon iterator for get a active nodes. This class provides a 611 /// common style lemon iterator which gives back a subset of the 612 /// nodes. The iterated nodes are active in the algorithm after 613 /// the last phase so these should be checked in the next phase to 614 /// find augmenting edges from these. 615 class ActiveIt { 616 public: 617 618 /// \brief Constructor. 619 /// 620 /// Constructor for get the nodeset of the variable. 621 ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm) 622 { 623 _index = _algorithm>_process.size()  1; 624 } 625 626 /// \brief Invalid constructor. 627 /// 628 /// Invalid constructor. 629 ActiveIt(Invalid) : _algorithm(0), _index(1) {} 630 631 /// \brief Conversion to node. 632 /// 633 /// Conversion to node. 634 operator Node() const { 635 return _index >= 0 ? _algorithm>_process[_index] : INVALID; 636 } 637 638 /// \brief Increment operator. 639 /// 640 /// Increment operator. 641 ActiveIt& operator++() { 642 _index; 643 return *this; 644 } 645 646 bool operator==(const ActiveIt& it) const { 647 return (Node)(*this) == (Node)it; 648 } 649 bool operator!=(const ActiveIt& it) const { 650 return (Node)(*this) != (Node)it; 651 } 652 bool operator<(const ActiveIt& it) const { 653 return (Node)(*this) < (Node)it; 654 } 655 656 private: 657 const BellmanFord* _algorithm; 658 int _index; 659 }; 660 608 661 /// \brief Copies the shortest path to \c t into \c p 609 662 /// … … 624 677 b.commit(); 625 678 return true; 679 } 680 return false; 681 } 682 683 /// \brief Copies a negative cycle into path \c p. 684 /// 685 /// This function copies a negative cycle into path \c p. 686 /// If the algorithm have not found yet negative cycle it will not change 687 /// the given path and gives back false. 688 /// 689 /// \return Returns \c true if a cycle was actually copied to \c p, 690 /// \c false otherwise. 691 /// \sa DirPath 692 template <typename Path> 693 bool getNegativeCycle(Path& p) { 694 typename Graph::template NodeMap<int> state(*graph, 0); 695 for (ActiveIt it(*this); it != INVALID; ++it) { 696 if (state[it] == 0) { 697 for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) { 698 if (state[t] == 0) { 699 state[t] = 1; 700 } else if (state[t] == 2) { 701 break; 702 } else { 703 p.clear(); 704 typename Path::Builder b(p); 705 b.setStartNode(t); 706 b.pushFront(predEdge(t)); 707 for(Node s = predNode(t); s != t; s = predNode(s)) { 708 b.pushFront(predEdge(s)); 709 } 710 b.commit(); 711 return true; 712 } 713 } 714 for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) { 715 if (state[t] == 1) { 716 state[t] = 2; 717 } else { 718 break; 719 } 720 } 721 } 626 722 } 627 723 return false;
Note: See TracChangeset
for help on using the changeset viewer.