Changes between Version 1 and Version 2 of Ticket #319
- Timestamp:
- 10/06/09 17:58:00 (15 years ago)
Legend:
- Unmodified
- Added
- Removed
- Modified
-
Ticket #319 – Description
v1 v2 1 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 willcause problems, since the algorithm saturates these arcs.1 If you run `Preflow` 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 most likely cause problems, since the algorithm saturates these arcs. 2 2 3 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). 3 Thus we should do one the followings: 4 1. Add a warning about this problem to the doc of the class and the dimacs solver. 5 2. Support infinite capacities in the algorithm (and in the dimacs solver as well). We could search for a finite cut and replace the infinite capacities on the outgoing arcs of the source node with the value of the found cut if such a cut exists. Otherwise the max. flow value is infinite. 4 6 5 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.7 A possible combination would be to choose the first solution and create a wrapper function/class for `Preflow` that supports infinite capacities applying the second solution.
