COIN-OR::LEMON - Graph Library

Opened 11 years ago

Closed 11 years ago

#243 closed enhancement (done)

Handling negative/infinity capacities in the dimacs readers

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

Description

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?

Attachments (3)

dimacs-cap-780ce5fdf189.patch (2.5 KB) - added by Peter Kovacs 11 years ago.
5d1dc5085b44.patch (9.6 KB) - added by Alpar Juttner 11 years ago.
dimacs-impr-1b3cd69531df.patch (6.4 KB) - added by Peter Kovacs 11 years ago.

Download all attachments as: .zip

Change History (12)

Changed 11 years ago by Peter Kovacs

comment:1 Changed 11 years ago by Peter Kovacs

Status: newassigned

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?

comment:2 in reply to:  1 Changed 11 years ago by 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.

comment:3 in reply to:  description ; Changed 11 years ago by 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)

comment:4 in reply to:  3 ; Changed 11 years ago by 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.

comment:5 in reply to:  4 Changed 11 years ago by 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?

Changed 11 years ago by Alpar Juttner

Attachment: 5d1dc5085b44.patch added

comment:6 Changed 11 years ago by 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.)

comment:7 Changed 11 years ago by 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.

Changed 11 years ago by Peter Kovacs

comment:8 in reply to:  7 Changed 11 years ago by 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].

comment:9 Changed 11 years ago by Alpar Juttner

Resolution: done
Status: assignedclosed
Note: See TracTickets for help on using tickets.