COIN-OR::LEMON - Graph Library

Changeset 2070:1287ef6c180f in lemon-0.x for lemon


Ignore:
Timestamp:
05/08/06 19:03:52 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2730
Message:

Getting Negative Cycle

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bellman_ford.h

    r2059 r2070  
    606606    ///@{
    607607
     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
    608661    /// \brief Copies the shortest path to \c t into \c p
    609662    ///   
     
    624677        b.commit();
    625678        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        }
    626722      }
    627723      return false;
Note: See TracChangeset for help on using the changeset viewer.