Handling negative/infinity capacities in the dimacs readers

[Peter Kovacs]

In [6a17a722b50e] the readDimacsMin() function stores the negative capacities as -1 values and readDimacsMax() does not check whether the capacities are negative or not.

The attached changeset changes this behavior. It stores negative capacity values (or values that are strictly less than the lower bound) as std::numeric_limits<Capacity>::max() or std::numeric_limits<Capacity>::infinity() if it is available.

What is your opinion?

[Peter Kovacs]

Another question is that readDimacsSp() and readDimacsMax() performs an if() for each arc definition line, however it could be avoided with a little code duplication. Would it worth it? Or the operator>> functions are more costly?

[Alpar Juttner]

Replying to kpeter:

Another question is that readDimacsSp() and readDimacsMax() performs an if() for each arc definition line, however it could be avoided with a little code duplication. Would it worth it? Or the operator>> functions are more costly?

I don't think running time is an issue here.

[Alpar Juttner]

Replying to kpeter:

The attached changeset changes this behavior. It stores negative capacity values (or values that are strictly less than the lower bound) as std::numeric_limits<Capacity>::max() or std::numeric_limits<Capacity>::infinity() if it is available.

Please make sure if the network flow algorithms will work reliably with std::numeric_limits<Capacity>::max() (i.e. there won't be integer overflow)

[Peter Kovacs]

Replying to alpar:

Please make sure if the network flow algorithms will work reliably with std::numeric_limits<Capacity>::max() (i.e. there won't be integer overflow)

NetworkSimplex supports such values, but I'm not sure about Preflow, Circulation and other algorithms for the max flow or the min cost flow problem.

As you have suggested (in a personal discussion), it could be much better to have an extra parameter for setting the value used for denoting infinite capacity, both in dimacs readers and in the dimacs solver.

[Alpar Juttner]

Replying to kpeter:

As you have suggested (in a personal discussion), it could be much better to have an extra parameter for setting the value used for denoting infinite capacity, both in dimacs readers and in the dimacs solver.

Could you modify the path according to this?

[Alpar Juttner]

[5d1dc5085b44] is another attempt for handling infinite capacities.

Could you please review and test it?

(It compiles well for me, but I haven't tested it at all. Should you have any dimacs file in your hand, please run dimacs-solver on it to test the readers. Thanks.)

[Peter Kovacs]

I fixed some typos in the code and made doc improvements, see [1b3cd69531df]. I checked it, it seems to be all right, however there is a little problem with the readDimacsCap() function. The doc says it handles negative values as "infinte" (whether it is of type 'sp' or 'max'), but it does so only in case of 'max' type. Setting the problem descriptor to 'max' wouldn't be enough, since the node definition lines differ in these cases.

[Alpar Juttner]

A merged of all these changes went to the main branch as [6e0525ec5355]

I checked it, it seems to be all right, however there is a little problem with the readDimacsCap() function. The doc says it handles negative values as "infinte" (whether it is of type 'sp' or 'max'), but it does so only in case of 'max' type. Setting the problem descriptor to 'max' wouldn't be enough, since the node definition lines differ in these cases.

My interpretation was that there are no capacities in an 'sp' format, even if we use the input in that sense in readDimacsCap(). Anyway, I made this point clear in the doc in [6e0525ec5355].