COIN-OR::LEMON - Graph Library

Changeset 699:75325dfccf38 in lemon-1.2 for lemon/bellman_ford.h


Ignore:
Timestamp:
08/03/09 00:54:04 (10 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Phase:
public
Message:

Add negativeCycle() function to BellmanFord? (#51)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bellman_ford.h

    r697 r699  
    771771    }
    772772
    773     // TODO: implement negative cycle
    774 //    /// \brief Gives back a negative cycle.
    775 //    ///   
    776 //    /// This function gives back a negative cycle.
    777 //    /// If the algorithm have not found yet negative cycle it will give back
    778 //    /// an empty path.
    779 //    Path negativeCycle() {
    780 //      typename Digraph::template NodeMap<int> state(*digraph, 0);
    781 //      for (ActiveIt it(*this); it != INVALID; ++it) {
    782 //        if (state[it] == 0) {
    783 //          for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
    784 //            if (state[t] == 0) {
    785 //              state[t] = 1;
    786 //            } else if (state[t] == 2) {
    787 //              break;
    788 //            } else {
    789 //              p.clear();
    790 //              typename Path::Builder b(p);
    791 //              b.setStartNode(t);
    792 //              b.pushFront(predArc(t));
    793 //              for(Node s = predNode(t); s != t; s = predNode(s)) {
    794 //                b.pushFront(predArc(s));
    795 //              }
    796 //              b.commit();
    797 //              return true;
    798 //            }
    799 //          }
    800 //          for (Node t = it; predArc(t) != INVALID; t = predNode(t)) {
    801 //            if (state[t] == 1) {
    802 //              state[t] = 2;
    803 //            } else {
    804 //              break;
    805 //            }
    806 //          }
    807 //        }
    808 //      }
    809 //      return false;
    810 //    }
     773    /// \brief Gives back a negative cycle.
     774    ///   
     775    /// This function gives back a directed cycle with negative total
     776    /// length if the algorithm has already found one.
     777    /// Otherwise it gives back an empty path.
     778    lemon::Path<Digraph> negativeCycle() {
     779      typename Digraph::template NodeMap<int> state(*_gr, -1);
     780      lemon::Path<Digraph> cycle;
     781      for (int i = 0; i < int(_process.size()); ++i) {
     782        if (state[_process[i]] != -1) continue;
     783        for (Node v = _process[i]; (*_pred)[v] != INVALID;
     784             v = _gr->source((*_pred)[v])) {
     785          if (state[v] == i) {
     786            cycle.addFront((*_pred)[v]);
     787            for (Node u = _gr->source((*_pred)[v]); u != v;
     788                 u = _gr->source((*_pred)[u])) {
     789              cycle.addFront((*_pred)[u]);
     790            }
     791            return cycle;
     792          }
     793          else if (state[v] >= 0) {
     794            break;
     795          }
     796          state[v] = i;
     797        }
     798      }
     799      return cycle;
     800    }
    811801   
    812802    ///@}
Note: See TracChangeset for help on using the changeset viewer.