Context Navigation

Changes between Initial Version and Version 1 of Ticket #319

Timestamp:: 10/06/09 12:28:10 (15 years ago)
Author:: Peter Kovacs
Comment:: Circulation is safe in this manner, since it uses the excess of the corresponding node as an upper bound for each push operation.

Ticket #319
- Property Status changed from new to assigned
- Property Summary changed from Infinite capacities in push-relabel algorithms to Infinite capacities in Preflow

-                      initial
+                      v1
 If you run a push-relabel algorithm using floating point capacity type on a graph having some arcs of infinite capacity (represented by either the `infinity()` or the `max()` value of the type), then it could cause problems, since the algorithm usually saturate arcs.
+If you run `Preflow` using floating point capacity type on a network in which the source node has some outgoing arcs of infinite capacity (represented by either the `infinity()` or the `max()` value of the type), then it will cause problems, since the algorithm saturates these arcs.
 To prevent this problem, we could replace the infinite capacities with sufficiently large finite values. For `Preflow` it would require the finding a finite value cut (if one exists). However for `Circulation` the `SUM[-sup(v) : sup(v)<0]` value could be used (if it is finite), so it would be simpler.
+To prevent this problem, we could replace the infinite capacities with sufficiently large finite values. However it would require the finding a finite value cut (if one exists).
 I suggest to either make these algorithms safer in this manner or add a warning to the doc of these classes and the dimacs solver about this problem.
+I suggest to either make the algorithm safer in this manner or add a warning about this problem to the doc of the class and the dimacs solver.