Port the remaining shortest path algorithms

[Alpar Juttner]

The following files are affected:

• lemon/floyd_warshall.h
• lemon/bellman_ford.h
• lemon/johnson.h
• lemon/dag_shortest_path.h

• test/all_pairs_shortest_path_test.cc

[Alpar Juttner]

Shouldn't we move this ticket to Milestone 1.2?

If yes, please do it.

[Peter Kovacs]

Maybe Bellman-Ford would worth to have in this release, but the others can surely be postponed.

[Alpar Juttner]

Well, the deadline for release 1.1 is approaching fast, let's focus our effort on what we must do.

[Peter Kovacs]

Port the Bellman-Ford algorithm

[Peter Kovacs]

Improvements for the interface and the doc of Bellman-Ford

[Peter Kovacs]

Add a test file for Bellman-Ford

[Peter Kovacs]

[c9b9da1a90a0] ports, [4d7606b85250] improves, [82bc26d0572d] tests the BellmanFord algorithm.

[Peter Kovacs]

Better version of [4d7606b85250]

[Peter Kovacs]

Add a test file for Bellman-Ford (on the top of [9496ed797f20])

[Peter Kovacs]

Replying to kpeter:

[c9b9da1a90a0] ports, [4d7606b85250] improves, [82bc26d0572d] tests the BellmanFord algorithm.

Consider to use the newer patches ([9496ed797f20] and [03f1dc010de8]) on the top of [c9b9da1a90a0].

[Peter Kovacs]

Add a test file for Bellman-Ford (on the top of [9496ed797f20]) , fixed version

[Peter Kovacs]

Add negativeCycle() function to BellmanFord

[Peter Kovacs]

Replying to kpeter:

Consider to use the newer patches ([9496ed797f20] and [03f1dc010de8]) on the top of [c9b9da1a90a0].

I'm sorry, but an unwanted std::cout command was left in the test file in [03f1dc010de8], use [f9746e45246e] instead.

[75325dfccf38] adds a new function negativeCycle() to BellmanFord and tests it.

The attached bundle file contains all the four changesets about BF to be merged into the main branch, namely: [c9b9da1a90a0], [9496ed797f20], [f9746e45246e], [75325dfccf38].

[Peter Kovacs]

Another question: how can you run BellmanFord algorithm using the "tolerance technique"? In Dijkstra and BellmanFord an OperationTraits class is used, which provides more felxiblity in modifying the various numerical operations, but it seems to be difficult to use it for the simple "tolerance technique". First, you have to specify an own operation traits class for it, second, all the functions of these classes are static, so they cannot depend on member variables, e.g. an epsilon value.

Maybe non-static functions for the operation traits class would be better, and we could provide an op. traits class for floating point types that uses the "tolerance technique". For Dijkstra it is not so important, since the correctness and efficency don't depend on that, but in BellmanFord both aspects could be affected by using the "tolerance technique" (consider a directed cycle of total cost e.g. -1e-15).

[Alpar Juttner]

Replying to kpeter:

Another question: how can you run BellmanFord algorithm using the "tolerance technique"? In Dijkstra and BellmanFord an OperationTraits class is used, which provides more felxiblity in modifying the various numerical operations, but it seems to be difficult to use it for the simple "tolerance technique". First, you have to specify an own operation traits class for it, second, all the functions of these classes are static, so they cannot depend on member variables, e.g. an epsilon value.

Maybe non-static functions for the operation traits class would be better, and we could provide an op. traits class for floating point types that uses the "tolerance technique". For Dijkstra it is not so important, since the correctness and efficency don't depend on that, but in BellmanFord both aspects could be affected by using the "tolerance technique" (consider a directed cycle of total cost e.g. -1e-15).

I don't understand this comment. What do you mean by "tolerance technique"? I can't really see any "efficiency" aspects here, either.

[Alpar Juttner]

The port has been merged into the main branch, anyway.

[Peter Kovacs]

Replying to alpar:

Replying to kpeter:

Another question: how can you run BellmanFord algorithm using the "tolerance technique"? In Dijkstra and BellmanFord an OperationTraits class is used, which provides more felxiblity in modifying the various numerical operations, but it seems to be difficult to use it for the simple "tolerance technique". First, you have to specify an own operation traits class for it, second, all the functions of these classes are static, so they cannot depend on member variables, e.g. an epsilon value.

Maybe non-static functions for the operation traits class would be better, and we could provide an op. traits class for floating point types that uses the "tolerance technique". For Dijkstra it is not so important, since the correctness and efficency don't depend on that, but in BellmanFord both aspects could be affected by using the "tolerance technique" (consider a directed cycle of total cost e.g. -1e-15).

I don't understand this comment. What do you mean by "tolerance technique"? I can't really see any "efficiency" aspects here, either.

Maybe I did not explained it clearly. Let us suppose that you would like to use BellmanFord to check if there is a negative cycle in a digraph or not (and compute node distance or potentials if they are feasible). The costs are real values and you would like to avoid finding such cycles whose total cost is nearly zero, so you search for cycles whose total cost is less then -eps for a positive eps value. (That's what I called tolerance technique.) I think it is a clear and important use case. How could you use the BellmanFord class for that?

Well, you could use an own OperationTraits class, in which you could define any kind of less() function, but this class should have static less() method, that cannot depend on a member variable, e.g. an eps value. That's why I suggest to use this functuion through an instance in the implementation of the class so as to support non-static less() function, as well. Moreover it would be nice to provide a simpler way for this use case, which does not require defining an own OperationTraits class, similarly to other classes, e.g. Preflow, Circulation, the new min. cost flow classes (see #179) etc.

I hope I could made my questions clear.

[Alpar Juttner]

Why not use the tolerance concept? It is designed exactly for this use-case.

[Peter Kovacs]

Replying to alpar:

Why not use the tolerance concept? It is designed exactly for this use-case.

I know how to use it for other algorithms, but BellmanFord does not support it. That is my problem, indeed.

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

Why not use the tolerance concept? It is designed exactly for this use-case.

I know how to use it for other algorithms, but BellmanFord does not support it. That is my problem, indeed.

So, what's the conclusion?

[Peter Kovacs]

Replying to alpar:

So, what's the conclusion?

My conclusions are the followings.

1. It would be better if every operation tratits class (Dijkstra, BellmanFord etc.) was used through an instance, not requiring its functions to be static.

2. We could provide standard operation traits classes that have a less() function using the tolerance concept.

[Peter Kovacs]

[6f10c6ec5a21] contains small fixes.

[Peter Kovacs]

I think, the operation traits question should be solved for BellmanFord in this milestone. However, the porting of all pairs shortest path algorthms could be postponed.

[Alpar Juttner]

Replying to kpeter:

I think, the operation traits question should be solved for BellmanFord in this milestone. However, the porting of all pairs shortest path algorthms could be postponed.

Let us do so.

[Peter Kovacs]

[4db8d5ccd26b] fixes a bug that causes memory leak if run() (or init()) is called more than once for an instance of the class.

[Alpar Juttner]

Is there any open issue here?

[Peter Kovacs]

Replying to kpeter:

My conclusions are the followings.

1. It would be better if every operation tratits class (Dijkstra, BellmanFord etc.) was used through an instance, not requiring its functions to be static.

2. We could provide standard operation traits classes that have a less() function using the tolerance concept.

I propose another solution: an operation traits class that has a template value parameter for epsilon can provide a suitable less() function.

The patch [a6eb9698c321] introduces such an op. traits class, but it is not used by default. How do you like this solution?

[Peter Kovacs]

I created a new ticket #346 in the next milestone about the remaining shortest path algorithms, thus this ticket can be closed once this tolerance question is solved.

[Peter Kovacs]

Replying to kpeter:

I propose another solution: an operation traits class that has a template value parameter for epsilon can provide a suitable less() function.

The patch [a6eb9698c321] introduces such an op. traits class, but it is not used by default. How do you like this solution?

It went to the main branch, thus this ticket can be closed. See #346 for the follow-up ticket.