Boost C++ Libraries: Ticket #11838: contribution: Yen k-shortest paths

attachment set

Thu, 10 Dec 2015 21:11:00 GMT

attachment → yen_ksp.hpp

the implementation

attachment set

Thu, 10 Dec 2015 21:11:28 GMT

attachment → yen_ksp.cc

the unit test

component, severity, type changed; cc, owner set

Thu, 10 Dec 2015 21:13:25 GMT

cc irek@… added
owner set to Jeremiah Willcock
component None → graph
severity Problem → Not Applicable
type Bugs → Library Submissions

attachment set

Thu, 10 Dec 2015 21:22:50 GMT

attachment → custom_dijkstra_call.hpp

attachment set

Thu, 10 Dec 2015 21:23:19 GMT

attachment → exclude_filter.hpp

Jürgen Hunold — Fri, 11 Dec 2015 10:21:07 GMT

New features should be submitted as pull requests on github See https://github.com/boostorg/graph And make sure you make your PR against the "develop" branch.

Fri, 11 Dec 2015 10:52:21 GMT

Will do! Thanks for the info!

Mon, 14 Mar 2016 22:00:09 GMT

Compile the unit test like this:

g++ -std=c++11 yen_ksp.cc -l boost_unit_test_framework -l boost_test_exec_monitor -o yen_ksp

attachment set

Mon, 14 Mar 2016 22:05:00 GMT

attachment → yen_ksp.2.hpp

the implementation - v2

Mon, 14 Mar 2016 22:07:08 GMT

I added a simpler and improved implementation (yen_ksp.2.hpp), which doesn't use the exclude_filter that I implemented. Instead, the filter provided by filtered_graph are used.

anonymous — Fri, 24 Jun 2016 09:58:48 GMT

Thank you, I was looking for something like that for some time. Did you implement the Martins and Pascoal?

anonymous — Fri, 24 Jun 2016 10:17:38 GMT

Glad to hear! No, I didn't work on Martins and Pascoal, nor many other algorithms like that.

You may want to have a look at the edge-disjoint KSP:

https://svn.boost.org/trac/boost/ticket/11804

anonymous — Tue, 28 Jun 2016 18:26:25 GMT

Hi again. Sorry, I think that there is a bug in yen_ksp.2.hpp. Basically I tested your program with a graph in which several composite paths have equal lengths, and where I could easily check by hand all the KSPs. What happens is that previously already identified KSPs reappear somewhere down the list of shortest paths. Of course they were all properly ordered and weights were correctly computed.

Below are the relevant snippets for the reproduction of the issue, for a KSP from O to D, and the weight-path output. As you can see, some repeated paths occur, which should not happen.

Best, Rytis

  Vertex X = *i++;
  Vertex O = *i++;
  Vertex D = *i++;
  Vertex L = *i++;
  Vertex R = *i;
  tie(ab, ba) = aue(g, O, X, 16);
  tie(ae, ea) = aue(g, X, D, 4 );
  tie(ac, ca) = aue(g, X, L, 25);
  tie(be, eb) = aue(g, X, R, 9 );
  tie(cd1, dc1) = aue(g, O, R, 25);
  tie(cd2, dc2) = aue(g, R, D, 13);
  tie(ce, ec)   = aue(g, D, L, 29);
  tie(aa,bb)   = aue(g, L, O, 41);

20.000  O -- X -- D
38.000  O -- R -- D
38.000  O -- X -- R -- D
38.000  O -- R -- X -- D
70.000  O -- L -- D
70.000  O -- L -- D
70.000  O -- X -- L -- D
70.000  O -- L -- D
70.000  O -- L -- X -- D
70.000  O -- L -- X -- D
70.000  O -- L -- X -- D
88.000  O -- R -- X -- L -- D
88.000  O -- L -- X -- R -- D
88.000  O -- L -- X -- R -- D
88.000  O -- L -- X -- R -- D

anonymous — Tue, 28 Jun 2016 18:33:45 GMT

Hi Rytis,

Thank you for the info! I'll look into it and definitely fix it within a few days.

Best, Irek

anonymous — Tue, 28 Jun 2016 18:41:14 GMT

I'll be looking forward to it. Too bad I am not proficient enough with boost, otherwise I'd try to help. Thank you!

Mon, 13 Feb 2017 13:07:56 GMT

Hi Rytis,

I fixed the implementation. Sorry it took me so long. The problem was that the algorithm can find the same tentative path many times, which is pushed into the list B of tentative paths many times, and then it is moved to the list A of shortest paths many times.

I came up with a simple test case:

  /-----4-----\
 a--1--b---1---c
        \--2--/

Finding the shortest paths between a and c should give 3 paths, while before the implementation would return 4. I implemented this example as a unit test.

I improved the implementation and the performance a bit, and added more comments. I also took advantage of the move semantics.

I'm going to attach the new implementation and the unit tests. This time I'm including a compressed archive, not separate files. Please find it below.

Best, Irek

attachment set

Mon, 13 Feb 2017 13:11:59 GMT

attachment → yen.tar.gz

This implementation does not return the same path many times.

Tue, 14 Feb 2017 06:36:14 GMT

Here is the repository:

https://github.com/iszczesniak/yen

Or you can clone:

git clone git@github.com:iszczesniak/yen.git

anonymous — Tue, 12 Jun 2018 14:21:14 GMT

Is it not added yet?

anonymous — Tue, 12 Jun 2018 14:24:47 GMT

Very nice algorithm for boost, because just Dijkstra's algorithm not enough in case, when you need chose path among several nearest paths.

irek@… — Tue, 12 Jun 2018 15:35:02 GMT

Replying to anonymous:

Is it not added yet?

It's not added, because I just don't have time to do it. Please feel free to submit the code, and be a coauthor.

andrewmw94 — Tue, 17 Jul 2018 14:09:44 GMT

I'm interested in getting this added. What still needs to be done?

andrewmw94 — Tue, 17 Jul 2018 15:55:48 GMT

Replying to andrewmw94:

I'm interested in getting this added. What still needs to be done?

More specifically is this just fixing the algorithm or is there extra paperwork / API change stuff that I would need to do?

I think the issue (or at least one issue) with the algorithm is that the Kth shortest path is not guaranteed to be a variant of the K-1th shortest path. The loop needs to consider all previous shortest paths. So we have to do more than just loop through the edges of psp.

irek@… — Wed, 18 Jul 2018 20:58:48 GMT

Replying to andrewmw94:

Replying to andrewmw94:

I'm interested in getting this added. What still needs to be done?

More specifically is this just fixing the algorithm or is there extra paperwork / API change stuff that I would need to do?

I'm happy to hear you want to submit the code! Good luck!

The implementation is already fixed, and is available at:

https://github.com/iszczesniak/yen

I don't know what should be exactly done to submit the code to Boost. I think the documentation, the right files in the right place, I guess.

Best, Irek