r699:75325dfccf38
Mon, 03 Aug 2009 00:54:04
[Not Reviewed]
0 comments (0 inline)
0
2
0
| ... | ... |
@@ -770,44 +770,34 @@ |
| 770 | 770 |
return (*_dist)[v] != OperationTraits::infinity(); |
| 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 |
///@} |
| 813 | 803 |
}; |
| ... | ... |
@@ -220,8 +220,64 @@ |
| 220 | 220 |
} |
| 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 |
} |
0 comments (0 inline)