lemon/bellman_ford.h
changeset 751 f5f260a63a9b
parent 697 9496ed797f20
child 781 6f10c6ec5a21
child 786 e20173729589
equal deleted inserted replaced
1:b02dde7dca4c 2:f1afc74c4caf
   768     /// using this function.
   768     /// using this function.
   769     bool reached(Node v) const {
   769     bool reached(Node v) const {
   770       return (*_dist)[v] != OperationTraits::infinity();
   770       return (*_dist)[v] != OperationTraits::infinity();
   771     }
   771     }
   772 
   772 
   773     // TODO: implement negative cycle
   773     /// \brief Gives back a negative cycle.
   774 //    /// \brief Gives back a negative cycle.
   774     ///    
   775 //    ///    
   775     /// This function gives back a directed cycle with negative total
   776 //    /// This function gives back a negative cycle.
   776     /// length if the algorithm has already found one.
   777 //    /// If the algorithm have not found yet negative cycle it will give back
   777     /// Otherwise it gives back an empty path.
   778 //    /// an empty path.
   778     lemon::Path<Digraph> negativeCycle() {
   779 //    Path negativeCycle() {
   779       typename Digraph::template NodeMap<int> state(*_gr, -1);
   780 //      typename Digraph::template NodeMap<int> state(*digraph, 0);
   780       lemon::Path<Digraph> cycle;
   781 //      for (ActiveIt it(*this); it != INVALID; ++it) {
   781       for (int i = 0; i < int(_process.size()); ++i) {
   782 //        if (state[it] == 0) {
   782         if (state[_process[i]] != -1) continue;
   783 //          for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
   783         for (Node v = _process[i]; (*_pred)[v] != INVALID;
   784 //            if (state[t] == 0) {
   784              v = _gr->source((*_pred)[v])) {
   785 //              state[t] = 1;
   785           if (state[v] == i) {
   786 //            } else if (state[t] == 2) {
   786             cycle.addFront((*_pred)[v]);
   787 //              break;
   787             for (Node u = _gr->source((*_pred)[v]); u != v;
   788 //            } else {
   788                  u = _gr->source((*_pred)[u])) {
   789 //              p.clear();
   789               cycle.addFront((*_pred)[u]);
   790 //              typename Path::Builder b(p);
   790             }
   791 //              b.setStartNode(t);
   791             return cycle;
   792 //              b.pushFront(predArc(t));
   792           }
   793 //              for(Node s = predNode(t); s != t; s = predNode(s)) {
   793           else if (state[v] >= 0) {
   794 //                b.pushFront(predArc(s));
   794             break;
   795 //              }
   795           }
   796 //              b.commit();
   796           state[v] = i;
   797 //              return true;
   797         }
   798 //            }
   798       }
   799 //          }
   799       return cycle;
   800 //          for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
   800     }
   801 //            if (state[t] == 1) {
       
   802 //              state[t] = 2;
       
   803 //            } else {
       
   804 //              break;
       
   805 //            }
       
   806 //          }
       
   807 //        }
       
   808 //      }
       
   809 //      return false;
       
   810 //    }
       
   811     
   801     
   812     ///@}
   802     ///@}
   813   };
   803   };
   814  
   804  
   815   /// \brief Default traits class of bellmanFord() function.
   805   /// \brief Default traits class of bellmanFord() function.