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

Timestamp:

05/08/06 19:03:52 (18 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2730

Message:

Getting Negative Cycle

File:

• lemon/bellman_ford.h (modified) (2 diffs)

lemon/bellman_ford.h

@@ -606 +606 @@
     ///@{
 
+    /// \brief Lemon iterator for get a active nodes.
+    ///
+    /// Lemon iterator for get a active nodes. This class provides a
+    /// common style lemon iterator which gives back a subset of the
+    /// nodes. The iterated nodes are active in the algorithm after
+    /// the last phase so these should be checked in the next phase to
+    /// find augmenting edges from these.
+    class ActiveIt {
+    public:
+
+      /// \brief Constructor.
+      ///
+      /// Constructor for get the nodeset of the variable. 
+      ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
+      {
+        _index = _algorithm->_process.size() - 1;
+      }
+
+      /// \brief Invalid constructor.
+      ///
+      /// Invalid constructor.
+      ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
+
+      /// \brief Conversion to node.
+      ///
+      /// Conversion to node.
+      operator Node() const { 
+        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
+      }
+
+      /// \brief Increment operator.
+      ///
+      /// Increment operator.
+      ActiveIt& operator++() {
+        --_index;
+        return *this; 
+      }
+
+      bool operator==(const ActiveIt& it) const { 
+        return (Node)(*this) == (Node)it; 
+      }
+      bool operator!=(const ActiveIt& it) const { 
+        return (Node)(*this) != (Node)it; 
+      }
+      bool operator<(const ActiveIt& it) const { 
+        return (Node)(*this) < (Node)it; 
+      }
+      
+    private:
+      const BellmanFord* _algorithm;
+      int _index;
+    };
+
     /// \brief Copies the shortest path to \c t into \c p
     ///    
@@ -624 +677 @@
         b.commit();
         return true;
+      }
+      return false;
+    }
+
+    /// \brief Copies a negative cycle into path \c p.
+    ///    
+    /// This function copies a negative cycle into path \c p.
+    /// If the algorithm have not found yet negative cycle it will not change
+    /// the given path and gives back false.
+    ///
+    /// \return Returns \c true if a cycle was actually copied to \c p,
+    /// \c false otherwise.
+    /// \sa DirPath
+    template <typename Path>
+    bool getNegativeCycle(Path& p) {
+      typename Graph::template NodeMap<int> state(*graph, 0);
+      for (ActiveIt it(*this); it != INVALID; ++it) {
+        if (state[it] == 0) {
+          for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
+            if (state[t] == 0) {
+              state[t] = 1;
+            } else if (state[t] == 2) {
+              break;
+            } else {
+              p.clear();
+              typename Path::Builder b(p);
+              b.setStartNode(t);
+              b.pushFront(predEdge(t));
+              for(Node s = predNode(t); s != t; s = predNode(s)) {
+                b.pushFront(predEdge(s));
+              }
+              b.commit();
+              return true;
+            }
+          }
+          for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
+            if (state[t] == 1) {
+              state[t] = 2;
+            } else {
+              break;
+            }
+          }
+        }
       }
       return false;