contribution: Yen k-shortest paths

[Irek Szcześniak <irek@…>]

I wanna contribute the implementation of the Yen k-shortest paths algorithm. Please find attached the implementation and the unit test.

[Irek Szcześniak <irek@…>]

the implementation

[Irek Szcześniak <irek@…>]

the unit test

[Jürgen Hunold]

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.

[Irek Szcześniak <irek@…>]

Will do! Thanks for the info!

[Irek Szcześniak <irek@…>]

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

[Irek Szcześniak <irek@…>]

the implementation - v2

[Irek Szcześniak <irek@…>]

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]

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

[anonymous]

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]

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]

Hi Rytis,

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

Best, Irek

[anonymous]

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

[Ireneusz Szcześniak <irek@…>]

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

[Ireneusz Szcześniak <irek@…>]

This implementation does not return the same path many times.

[Ireneusz Szcześniak <irek@…>]

Here is the repository:

​https://github.com/iszczesniak/yen

Or you can clone:

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

[anonymous]

Is it not added yet?

[anonymous]

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

[irek@…]

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]

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

[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 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@…]

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