Revise the interface of Circulation and Suurballe

[Peter Kovacs]

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

[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.

[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.

[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. :)

[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.

[Alpar Juttner]

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.

[Peter Kovacs]

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?

[Alpar Juttner]

Replying to kpeter:

Should we create a ticket about this?

Yes, we should.

[Peter Kovacs]

Replying to alpar:

Yes, we should.

Here it is: #269.

[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.

[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].

[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.

[Peter Kovacs]

What do you think about this new interface of Suurballe?

[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?

[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?

[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.

[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.

[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.

[Peter Kovacs]

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

[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.

[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)

[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?

[Peter Kovacs]

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

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

[Alpar Juttner]

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.

[Peter Kovacs]

[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.

[Peter Kovacs]

[756a5ec551c8] went to the main branch.