COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 9 years ago

#319 closed enhancement (done)

Infinite capacities in Preflow

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.2 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description (last modified by Peter Kovacs)

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.

Thus we should do one the followings:

  1. Add a warning about this problem to the doc of the class and the dimacs solver.
  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.
  3. 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.

Attachments (1)

319-a7e93de12cbd.patch (832 bytes) - added by Peter Kovacs 9 years ago.

Download all attachments as: .zip

Change History (8)

comment:1 Changed 9 years ago by Peter Kovacs

Description: modified (diff)
Status: newassigned
Summary: Infinite capacities in push-relabel algorithmsInfinite capacities in Preflow

Circulation is safe in this manner, since it uses the excess of the corresponding node as an upper bound for each push operation.

comment:2 Changed 9 years ago by Peter Kovacs

Description: modified (diff)

comment:3 Changed 9 years ago by Peter Kovacs

Milestone: LEMON 1.2 release

comment:4 Changed 9 years ago by Peter Kovacs

Description: modified (diff)

I suggest to apply the first solution soon. The second or third solution could be done later, but they are not as critical as adding a warning about this problem to the documentation.

comment:5 in reply to:  4 Changed 9 years ago by Alpar Juttner

Replying to kpeter:

I suggest to apply the first solution soon. The second or third solution could be done later, but they are not as critical as adding a warning about this problem to the documentation.

Agreed.

comment:6 Changed 9 years ago by Peter Kovacs

The attached patch [a7e93de12cbd] adds a warning to the doc.

#338 is a follow-up of this ticket about the possible support of infinite capacities (in the future).

Changed 9 years ago by Peter Kovacs

Attachment: 319-a7e93de12cbd.patch added

comment:7 in reply to:  6 Changed 9 years ago by Alpar Juttner

Resolution: done
Status: assignedclosed

Replying to kpeter:

The attached patch [a7e93de12cbd] adds a warning to the doc.

Thanks. It has been pushed to the main branch.

Note: See TracTickets for help on using tickets.