COIN-OR::LEMON - Graph Library

Opened 15 years ago

Closed 15 years ago

#266 closed task (fixed)

Revise the interface of Circulation and Suurballe

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

Description

When the interface of NetworkSimplex is clarified and accepted (see #234), the interface of Circulation and Suurballe have to be synchronized with it.

Attachments (6)

circ-dacc2cee2b4c.patch (24.8 KB) - added by Peter Kovacs 15 years ago.
circ-ea2c9187404a.patch (2.0 KB) - added by Peter Kovacs 15 years ago.
circ-debug-0eb152268d6d.patch (1.1 KB) - added by Peter Kovacs 15 years ago.
suurballe-1a9b60b22a8d.patch (21.9 KB) - added by Peter Kovacs 15 years ago.
circ-impr-c20b7ed31aad.patch (1.9 KB) - added by Peter Kovacs 15 years ago.
Flow-Value-756a5ec551c8.patch (17.8 KB) - added by Peter Kovacs 15 years ago.

Download all attachments as: .zip

Change History (32)

Changed 15 years ago by Peter Kovacs

Attachment: circ-dacc2cee2b4c.patch added

comment:1 Changed 15 years ago by Peter Kovacs

The attached changeset [dacc2cee2b4c] could be the first step in this task. It slightly modifies the interface of Circulation and Preflow in order to synchronize them to the interface of NetworkSimplex.

  • Circulation:
    • The "delta" notation is replaced by "supply".
    • lowerCapMap(), upperCapMap() are renamed to lowerMap() and upperMap().
    • Value is renamed to Flow.
  • Preflow:
    • Value is renamed to Flow.

comment:2 Changed 15 years ago by Peter Kovacs

Apart from the above changes I suggest using named parameters for specifying the parameters in the Circulation algorithm similarly to NetworkSimplex.

So it would have only two template parameters: Graph and Flow, and the constructor would take only one parameter: the digraph. The other parameters could be defined by the optional named parameters: lowerMap(), upperMap(), boundMaps(), supplyMap(), stSupply().

What do you think about it? At first I wasn't so keen about the named parameters in NetworkSimplex, but now I do like the new interface and I think it would be much better to have almost the same interface for Circulation. For a little motivation see the lines 1158-1208 in network_simplex.h in [e6927fe719e6], where Circulation is used. It would be much easier and shorter with named parameters.

comment:3 Changed 15 years ago by Peter Kovacs

Another question: in Circulation there are checker functions for the primal and dual solution, however there isn't any other algorithm with such checker functions. What concept should we follow about it?

I suggest removing these functions, or more precisely move them to the test file, as for other algorithms. Theoretically the algorithms must provide good solutions, thus it doesn't seem necessary to check the results for a user. That's why we implement the algoirthms and the test files carefully. :)

comment:4 in reply to:  2 ; Changed 15 years ago by Peter Kovacs

Replying to kpeter:

Apart from the above changes I suggest using named parameters for specifying the parameters in the Circulation algorithm similarly to NetworkSimplex.

In fact, it requires the maps to be copied. However if it is really important, than we could introduce a parameterized run() function as well, for the sake of convenience and efficiency, i.e.

  Circulation<GR> circ(gr);
  circ.boundMaps(lo, up).supplyMap(sup).run();

and

  Circulation<GR> circ(gr);
  circ.run(lo, up, sup);

It would be a little bit tricky to implement both of them, since the internal functions should be template then.

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

Resolution: done
Status: newclosed

Replying to kpeter:

Replying to kpeter:

Apart from the above changes I suggest using named parameters for specifying the parameters in the Circulation algorithm similarly to NetworkSimplex.

In fact, it requires the maps to be copied.

I suggest making a different "copying" circulation implementation instead. Sometimes in the future.

comment:6 in reply to:  5 ; Changed 15 years ago by Peter Kovacs

Resolution: done
Status: closedreopened

I've reopened this ticket because the Suurballe interface should be revised.

Replying to alpar:

I suggest making a different "copying" circulation implementation instead. Sometimes in the future.

Maybe we could have a function interface for Circulation (in the future), which would be as efficient as the current class interface and as flexible as the proposed named parameters. Its functions should be very similar to the interface of NetworkSimplex. What do you think? Should we create a ticket about this?

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

Replying to kpeter:

Should we create a ticket about this?

Yes, we should.

comment:8 in reply to:  7 Changed 15 years ago by Peter Kovacs

Replying to alpar:

Yes, we should.

Here it is: #269.

Changed 15 years ago by Peter Kovacs

Attachment: circ-ea2c9187404a.patch added

comment:9 Changed 15 years ago by Peter Kovacs

[ea2c9187404a] contains the following changes to Circulation (according to the interface of NS):

  • Add capacityMap() as an alias for upperMap().
  • Add boundMaps() as an alternative for lowerMap() + upperMap().
  • A bug fix in upperMap().
  • Doc improvement.

It is on the top of [547e6b876ee1], see #270.

Changed 15 years ago by Peter Kovacs

comment:10 Changed 15 years ago by Peter Kovacs

[0eb152268d6d] contains a LEMON_DEBUG check for lower(e)<=upper(e) on the arcs. What do you think about it?

This constraint must hold in order to say: "This algorithm either calculates a feasible circulation or provides a barrier, which prooves that a feasible soultion cannot exist", see [ea2c9187404a].

Changed 15 years ago by Peter Kovacs

comment:11 Changed 15 years ago by Peter Kovacs

[1a9b60b22a8d] contains the following changes for Suurballe.

  • Move the parameters s and t from the constructor to the run() function. It makes the interface capable for multiple run(s,t,k) calls (possible improvement in the future) and it is more similar to Dijkstra.
  • Simliarly init() and findFlow(k) were replaced by init(s) and findFlow(t,k). The separation of parameters s and t is for the future plans of supporting multiple targets with one source node. For more information see #181.
  • LEMON_ASSERT for the Length type (check if it is integer).
  • Doc improvements.
  • Rearrange query functions.
  • Extend test file.

comment:12 Changed 15 years ago by Peter Kovacs

What do you think about this new interface of Suurballe?

comment:13 Changed 15 years ago by Peter Kovacs

Here is another question.

There is flowValue() in Preflow (not maxValue() or maxFlowValue()), matchingSize() and matchingWeight() in the matching algorithms (not maxWeight()), however there is totalLength() in Suurballe (not flowLength()).

So how should we call the query function in NetworkSimplex? totalCost() similarly to Suurballe::totalLength() or flowCost() similarly to max. flow and matching algorithms? Or should we use both of them? (I don't think so.)

It could be annoying the we use length for Suurballe (just like Dijkstra), although it is actually a special case of MCF. Should we introduce totalCost() as an alias for totalLength() in Suurballe?

comment:14 in reply to:  9 ; Changed 15 years ago by Alpar Juttner

Replying to kpeter:

  • Add capacityMap() as an alias for upperMap().

In general I'm not quite happy with these kind of aliases. They make the sw maintenance more difficult, and make the doc bloated with zero added functionality.

In this case the meaning of upperMap() is even clearer that that of the capacityMap(). What's the advantage of having the latter one, too?

  • Add boundMaps() as an alternative for lowerMap() + upperMap().

The same question. Why do we need it?

comment:15 in reply to:  13 ; Changed 15 years ago by Alpar Juttner

Replying to kpeter:

So how should we call the query function in NetworkSimplex?

It is good as is.

It could be annoying the we use length for Suurballe (just like Dijkstra), although it is actually a special case of MCF.

We know that it is a special MCF, but most engineers regards it as extension of Dijkstra. That's the reason on the name choice.

Should we introduce totalCost() as an alias for totalLength() in Suurballe?

NO. See my previous comment.

comment:16 in reply to:  14 ; Changed 15 years ago by Peter Kovacs

Replying to alpar:

In general I'm not quite happy with these kind of aliases. They make the sw maintenance more difficult, and make the doc bloated with zero added functionality.

I see. So they won't be in Circulation. What about NS? I prefer having capacityMap() there, since lowerMap() is not necessary, and if only one map is used, it is natural to call it capacity as in max flow algorithms.

In this case the meaning of upperMap() is even clearer that that of the capacityMap(). What's the advantage of having the latter one, too?

In NS I see advantages, but in Circulation it is not so useful or logical, I admit.

  • Add boundMaps() as an alternative for lowerMap() + upperMap().

The same question. Why do we need it?

I agree, we don't need it in Circulation. Do we need it in NS? The only reason for having this could be the shortness.

comment:17 in reply to:  15 Changed 15 years ago by Peter Kovacs

Replying to alpar:

Replying to kpeter:

So how should we call the query function in NetworkSimplex?

It is good as is.

Okay.

It could be annoying the we use length for Suurballe (just like Dijkstra), although it is actually a special case of MCF.

We know that it is a special MCF, but most engineers regards it as extension of Dijkstra. That's the reason on the name choice.

I agree with the name, I just propose a question. :)

Should we introduce totalCost() as an alias for totalLength() in Suurballe?

NO. See my previous comment.

Okay.

Changed 15 years ago by Peter Kovacs

comment:18 Changed 15 years ago by Peter Kovacs

Forget [ea2c9187404a] and [0eb152268d6d]. The new patch [c20b7ed31aad] contains all important changes of them, without adding new functions.

comment:19 in reply to:  11 ; Changed 15 years ago by Alpar Juttner

Replying to kpeter:

  • LEMON_ASSERT for the Length type (check if it is integer).

Why do we need this? I always thought Suurballe works well with float/double.

comment:20 in reply to:  19 Changed 15 years ago by Peter Kovacs

Replying to alpar:

Replying to kpeter:

  • LEMON_ASSERT for the Length type (check if it is integer).

Why do we need this? I always thought Suurballe works well with float/double.

The current implementation doesn't use tolerance technique. With this modification it will surely support float/double costs. (It is just because I modify the CapacityScaling algorithm to implement Suurballe, and up to now the MCF algorithms don't support real data, see #261)

comment:21 in reply to:  16 Changed 15 years ago by Peter Kovacs

Replying to kpeter:

I agree, we don't need it in Circulation. Do we need it in NS? The only reason for having this could be the shortness.

Could you answer it please? Do you find boundMaps() good in NS or should it be removed?

comment:22 Changed 15 years ago by Peter Kovacs

Now only one changeset is relevant here: [1a9b60b22a8d] for Suurballe.

See also [28f58740b6f8] in #270 about Circulation.

comment:23 in reply to:  22 Changed 15 years ago by Alpar Juttner

Resolution: done
Status: reopenedclosed

Replying to kpeter:

Now only one changeset is relevant here: [1a9b60b22a8d] for Suurballe.

I fixed a compilation bug in it and reapplied to the tip, see [7c1324b35d89] in the main branch.

Changed 15 years ago by Peter Kovacs

comment:24 Changed 15 years ago by Peter Kovacs

Resolution: done
Status: closedreopened

[756a5ec551c8] renames Flow to Value in the flow algorithms. It is on the top of [6c408d864fa1], see #270.

We agreed that using Flow for the value type is misleading, since a flow should be rather a function on the arcs, not a single value.

This patch reverts the changes of [dacc2cee2b4c] for Preflow and Circulation.

comment:25 Changed 15 years ago by Peter Kovacs

[756a5ec551c8] went to the main branch.

comment:26 Changed 15 years ago by Peter Kovacs

Resolution: fixed
Status: reopenedclosed
Note: See TracTickets for help on using tickets.