Changeset 746:75325dfccf38 in lemon for lemon/bellman_ford.h
 Timestamp:
 08/03/09 00:54:04 (15 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/bellman_ford.h
r744 r746 771 771 } 772 772 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 } 811 801 812 802 ///@}
Note: See TracChangeset
for help on using the changeset viewer.