1.1 --- a/lemon/bellman_ford.h	Fri May 05 10:48:58 2006 +0000
     1.2 +++ b/lemon/bellman_ford.h	Mon May 08 17:03:52 2006 +0000
     1.3 @@ -605,6 +605,59 @@
     1.4      
     1.5      ///@{
     1.6  
     1.7 +    /// \brief Lemon iterator for get a active nodes.
     1.8 +    ///
     1.9 +    /// Lemon iterator for get a active nodes. This class provides a
    1.10 +    /// common style lemon iterator which gives back a subset of the
    1.11 +    /// nodes. The iterated nodes are active in the algorithm after
    1.12 +    /// the last phase so these should be checked in the next phase to
    1.13 +    /// find augmenting edges from these.
    1.14 +    class ActiveIt {
    1.15 +    public:
    1.16 +
    1.17 +      /// \brief Constructor.
    1.18 +      ///
    1.19 +      /// Constructor for get the nodeset of the variable. 
    1.20 +      ActiveIt(const BellmanFord& algorithm) : _algorithm(&algorithm)
    1.21 +      {
    1.22 +        _index = _algorithm->_process.size() - 1;
    1.23 +      }
    1.24 +
    1.25 +      /// \brief Invalid constructor.
    1.26 +      ///
    1.27 +      /// Invalid constructor.
    1.28 +      ActiveIt(Invalid) : _algorithm(0), _index(-1) {}
    1.29 +
    1.30 +      /// \brief Conversion to node.
    1.31 +      ///
    1.32 +      /// Conversion to node.
    1.33 +      operator Node() const { 
    1.34 +        return _index >= 0 ? _algorithm->_process[_index] : INVALID;
    1.35 +      }
    1.36 +
    1.37 +      /// \brief Increment operator.
    1.38 +      ///
    1.39 +      /// Increment operator.
    1.40 +      ActiveIt& operator++() {
    1.41 +        --_index;
    1.42 +        return *this; 
    1.43 +      }
    1.44 +
    1.45 +      bool operator==(const ActiveIt& it) const { 
    1.46 +        return (Node)(*this) == (Node)it; 
    1.47 +      }
    1.48 +      bool operator!=(const ActiveIt& it) const { 
    1.49 +        return (Node)(*this) != (Node)it; 
    1.50 +      }
    1.51 +      bool operator<(const ActiveIt& it) const { 
    1.52 +        return (Node)(*this) < (Node)it; 
    1.53 +      }
    1.54 +      
    1.55 +    private:
    1.56 +      const BellmanFord* _algorithm;
    1.57 +      int _index;
    1.58 +    };
    1.59 +
    1.60      /// \brief Copies the shortest path to \c t into \c p
    1.61      ///    
    1.62      /// This function copies the shortest path to \c t into \c p.
    1.63 @@ -626,6 +679,49 @@
    1.64        }
    1.65        return false;
    1.66      }
    1.67 +
    1.68 +    /// \brief Copies a negative cycle into path \c p.
    1.69 +    ///    
    1.70 +    /// This function copies a negative cycle into path \c p.
    1.71 +    /// If the algorithm have not found yet negative cycle it will not change
    1.72 +    /// the given path and gives back false.
    1.73 +    ///
    1.74 +    /// \return Returns \c true if a cycle was actually copied to \c p,
    1.75 +    /// \c false otherwise.
    1.76 +    /// \sa DirPath
    1.77 +    template <typename Path>
    1.78 +    bool getNegativeCycle(Path& p) {
    1.79 +      typename Graph::template NodeMap<int> state(*graph, 0);
    1.80 +      for (ActiveIt it(*this); it != INVALID; ++it) {
    1.81 +        if (state[it] == 0) {
    1.82 +          for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
    1.83 +            if (state[t] == 0) {
    1.84 +              state[t] = 1;
    1.85 +            } else if (state[t] == 2) {
    1.86 +              break;
    1.87 +            } else {
    1.88 +              p.clear();
    1.89 +              typename Path::Builder b(p);
    1.90 +              b.setStartNode(t);
    1.91 +              b.pushFront(predEdge(t));
    1.92 +              for(Node s = predNode(t); s != t; s = predNode(s)) {
    1.93 +                b.pushFront(predEdge(s));
    1.94 +              }
    1.95 +              b.commit();
    1.96 +              return true;
    1.97 +            }
    1.98 +          }
    1.99 +          for (Node t = it; predEdge(t) != INVALID; t = predNode(t)) {
   1.100 +            if (state[t] == 1) {
   1.101 +              state[t] = 2;
   1.102 +            } else {
   1.103 +              break;
   1.104 +            }
   1.105 +          }
   1.106 +        }
   1.107 +      }
   1.108 +      return false;
   1.109 +    }
   1.110  	  
   1.111      /// \brief The distance of a node from the root.
   1.112      ///