Warning in MATLAB_BGL

Asked by snehamoy on 2009-11-05

Hi,
I am working on minimum cut problem with a large data set. In my problem, I have a constraint that a node will not be in the minimum cut unless some perticular blocks are in cut. I fixed those constraints by putting a infinite capacity arcs ( by giving a large numeric value like 9.9e+17) from those nodes to its precedence nodes. I have total 230000 nodes in total. When I am running the push relable algorithm I am getting follwoing warning:
"Warning: The rounded (unrounded) value of the minimum cut is -2147483648 (1.2969e+017),but
the value of the max-flow is 371223564. These values should be equal "

I am sure that the minimum cut providing after this warning is not the true minimum cut. I have tried by reduceing the value of the infinite capacity arcs value. On that case the progrm is running without warning but it is not respect my constraints.

Could you plese help me to solve this problem.
If you need more information I am ready to provide.

With regards,

Question information

Language:
English Edit question
Status:
Answered
For:
Matlab BGL Edit question
Assignee:
No assignee Edit question
Last query:
Last reply:
Revision history for this message
David Gleich (dgleich) said :
#1

Hi,

The issue is that you are overflowing the internal integer counters. The largest value of infinity you can try is well under one billion (1e9). If you reduce it, you are going to be adding links with negative capacity, I believe. (It's been a while since I studied this particular implementation, so that may be incorrect.)

Anyway, you'll have to figure out some way that the max-flow and all the capacities fit within an integer range. I'll look at extending the range to a 64-bit value in the next version.

David

Can you help with this problem?

Provide an answer of your own, or ask snehamoy for more information if necessary.

To post a message you must log in.