COIN-OR::LEMON - Graph Library

Opened 11 years ago

Closed 9 years ago

#51 closed task (done)

Port the remaining shortest path algorithms

Reported by: Alpar Juttner Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.2 release
Component: core Version:
Keywords: Cc:
Revision id:

Description

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

Attachments (11)

51-1-port-c9b9da1a90a0.patch (36.8 KB) - added by Peter Kovacs 9 years ago.
Port the Bellman-Ford algorithm
51-2-impr-4d7606b85250.patch (61.0 KB) - added by Peter Kovacs 9 years ago.
Improvements for the interface and the doc of Bellman-Ford
51-3-test-82bc26d0572d.patch (7.2 KB) - added by Peter Kovacs 9 years ago.
Add a test file for Bellman-Ford
51-2-impr-new-9496ed797f20.patch (61.0 KB) - added by Peter Kovacs 9 years ago.
Better version of [4d7606b85250]
51-3-test-new-03f1dc010de8.patch (7.2 KB) - added by Peter Kovacs 9 years ago.
Add a test file for Bellman-Ford (on the top of [9496ed797f20])
51-3-test-new-f9746e45246e.patch (7.1 KB) - added by Peter Kovacs 9 years ago.
Add a test file for Bellman-Ford (on the top of [9496ed797f20]) , fixed version
51-4-neg-cycle-75325dfccf38.patch (4.5 KB) - added by Peter Kovacs 9 years ago.
Add negativeCycle() function to BellmanFord
51-bellman-ford.bundle (15.1 KB) - added by Peter Kovacs 9 years ago.
51-fixes-6f10c6ec5a21.patch (1.6 KB) - added by Peter Kovacs 9 years ago.
51-bugfix-4db8d5ccd26b.patch (756 bytes) - added by Peter Kovacs 9 years ago.
51-bf-tolerance-a6eb9698c321.patch (4.5 KB) - added by Peter Kovacs 9 years ago.

Download all attachments as: .zip

Change History (35)

comment:1 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.0 releasePost 1.0

comment:2 Changed 10 years ago by Peter Kovacs

Owner: changed from Alpar Juttner to Peter Kovacs
Status: newassigned

comment:3 Changed 10 years ago by Alpar Juttner

Shouldn't we move this ticket to Milestone 1.2?

If yes, please do it.

comment:4 Changed 10 years ago by Peter Kovacs

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

comment:5 Changed 10 years ago by Alpar Juttner

Milestone: LEMON 1.1 releaseLEMON 1.2 release

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

Changed 9 years ago by Peter Kovacs

Port the Bellman-Ford algorithm

Changed 9 years ago by Peter Kovacs

Improvements for the interface and the doc of Bellman-Ford

Changed 9 years ago by Peter Kovacs

Add a test file for Bellman-Ford

comment:6 Changed 9 years ago by Peter Kovacs

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

Changed 9 years ago by Peter Kovacs

Better version of [4d7606b85250]

Changed 9 years ago by Peter Kovacs

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

comment:7 in reply to:  6 ; Changed 9 years ago by 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].

Changed 9 years ago by Peter Kovacs

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

Changed 9 years ago by Peter Kovacs

Add negativeCycle() function to BellmanFord

Changed 9 years ago by Peter Kovacs

Attachment: 51-bellman-ford.bundle added

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

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

comment:10 in reply to:  9 ; Changed 9 years ago by 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.

comment:11 Changed 9 years ago by Alpar Juttner

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

comment:12 in reply to:  10 Changed 9 years ago by 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.

comment:13 Changed 9 years ago by Alpar Juttner

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

comment:14 in reply to:  13 ; Changed 9 years ago by 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.

comment:15 in reply to:  14 ; Changed 9 years ago by 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?

comment:16 in reply to:  15 ; Changed 9 years ago by 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.
  1. We could provide standard operation traits classes that have a less() function using the tolerance concept.

Changed 9 years ago by Peter Kovacs

Attachment: 51-fixes-6f10c6ec5a21.patch added

comment:17 Changed 9 years ago by Peter Kovacs

[6f10c6ec5a21] contains small fixes.

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

comment:19 in reply to:  18 Changed 9 years ago by 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.

Changed 9 years ago by Peter Kovacs

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

comment:21 Changed 9 years ago by Alpar Juttner

Is there any open issue here?

comment:22 in reply to:  16 ; Changed 9 years ago by 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.
  1. 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?

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

Changed 9 years ago by Peter Kovacs

comment:24 in reply to:  22 Changed 9 years ago by Peter Kovacs

Resolution: done
Status: assignedclosed

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.

Note: See TracTickets for help on using tickets.