Changeset 746:75325dfccf38 in lemon
- Timestamp:
- 08/03/09 00:54:04 (15 years ago)
- Branch:
- default
- Phase:
- public
- Files:
-
- 2 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 ///@} -
test/bellman_ford_test.cc
r745 r746 221 221 } 222 222 223 void checkBellmanFordNegativeCycle() { 224 DIGRAPH_TYPEDEFS(SmartDigraph); 225 226 SmartDigraph gr; 227 IntArcMap length(gr); 228 229 Node n1 = gr.addNode(); 230 Node n2 = gr.addNode(); 231 Node n3 = gr.addNode(); 232 Node n4 = gr.addNode(); 233 234 Arc a1 = gr.addArc(n1, n2); 235 Arc a2 = gr.addArc(n2, n2); 236 237 length[a1] = 2; 238 length[a2] = -1; 239 240 { 241 BellmanFord<SmartDigraph, IntArcMap> bf(gr, length); 242 bf.run(n1); 243 StaticPath<SmartDigraph> p = bf.negativeCycle(); 244 check(p.length() == 1 && p.front() == p.back() && p.front() == a2, 245 "Wrong negative cycle."); 246 } 247 248 length[a2] = 0; 249 250 { 251 BellmanFord<SmartDigraph, IntArcMap> bf(gr, length); 252 bf.run(n1); 253 check(bf.negativeCycle().empty(), 254 "Negative cycle should not be found."); 255 } 256 257 length[gr.addArc(n1, n3)] = 5; 258 length[gr.addArc(n4, n3)] = 1; 259 length[gr.addArc(n2, n4)] = 2; 260 length[gr.addArc(n3, n2)] = -4; 261 262 { 263 BellmanFord<SmartDigraph, IntArcMap> bf(gr, length); 264 bf.init(); 265 bf.addSource(n1); 266 for (int i = 0; i < 4; ++i) { 267 check(bf.negativeCycle().empty(), 268 "Negative cycle should not be found."); 269 bf.processNextRound(); 270 } 271 StaticPath<SmartDigraph> p = bf.negativeCycle(); 272 check(p.length() == 3, "Wrong negative cycle."); 273 check(length[p.nth(0)] + length[p.nth(1)] + length[p.nth(2)] == -1, 274 "Wrong negative cycle."); 275 } 276 } 277 223 278 int main() { 224 279 checkBellmanFord<ListDigraph, int>(); 225 280 checkBellmanFord<SmartDigraph, double>(); 281 checkBellmanFordNegativeCycle(); 226 282 return 0; 227 283 }
Note: See TracChangeset
for help on using the changeset viewer.