COIN-OR::LEMON - Graph Library

Opened 8 years ago

#338 new enhancement

Infinite capacities in Preflow

Reported by: kpeter Owned by: alpar
Priority: minor Milestone:
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

Infinite (or very high) capacities typically cause problems in Preflow, since the algorithm usually saturate arcs.

This problem could be overcome by finding a finite cut and replace the huge 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.

This solution could be implemented in the Preflow class itself or rather in a separate wrapper class (it should be used in the DIMACS solver utility, as well).

This ticket is a follow-up of #319.

Change History (0)

Note: See TracTickets for help on using tickets.