Opened 3 years ago

Last modified 4 months ago

#11838 new Library Submissions

contribution: Yen k-shortest paths

Reported by: Irek Szcześniak <irek@…> Owned by: Jeremiah Willcock
Milestone: To Be Determined Component: graph
Version: Boost 1.57.0 Severity: Not Applicable
Keywords: Cc: irek@…

Description

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

Attachments (6)

yen_ksp.hpp (5.7 KB) - added by Irek Szcześniak <irek@…> 3 years ago.
the implementation
yen_ksp.cc (2.3 KB) - added by Irek Szcześniak <irek@…> 3 years ago.
the unit test
custom_dijkstra_call.hpp (3.8 KB) - added by Irek Szcześniak <irek@…> 3 years ago.
exclude_filter.hpp (1.1 KB) - added by Irek Szcześniak <irek@…> 3 years ago.
yen_ksp.2.hpp (5.6 KB) - added by Irek Szcześniak <irek@…> 3 years ago.
the implementation - v2
yen.tar.gz (4.8 KB) - added by Ireneusz Szcześniak <irek@…> 21 months ago.
This implementation does not return the same path many times.

Download all attachments as: .zip

Change History (24)

Changed 3 years ago by Irek Szcześniak <irek@…>

Attachment: yen_ksp.hpp added

the implementation

Changed 3 years ago by Irek Szcześniak <irek@…>

Attachment: yen_ksp.cc added

the unit test

comment:1 Changed 3 years ago by Irek Szcześniak <irek@…>

Cc: irek@… added
Component: Nonegraph
Owner: set to Jeremiah Willcock
Severity: ProblemNot Applicable
Type: BugsLibrary Submissions

Changed 3 years ago by Irek Szcześniak <irek@…>

Attachment: custom_dijkstra_call.hpp added

Changed 3 years ago by Irek Szcześniak <irek@…>

Attachment: exclude_filter.hpp added

comment:2 Changed 3 years ago by 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.

comment:3 Changed 3 years ago by Irek Szcześniak <irek@…>

Will do! Thanks for the info!

comment:4 Changed 3 years ago by 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

Changed 3 years ago by Irek Szcześniak <irek@…>

Attachment: yen_ksp.2.hpp added

the implementation - v2

comment:5 Changed 3 years ago by 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.

comment:6 Changed 2 years ago by anonymous

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

comment:7 Changed 2 years ago by 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

comment:8 Changed 2 years ago by 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

comment:9 Changed 2 years ago by anonymous

Hi Rytis,

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

Best, Irek

comment:10 Changed 2 years ago by 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!

comment:11 Changed 21 months ago by 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

Changed 21 months ago by Ireneusz Szcześniak <irek@…>

Attachment: yen.tar.gz added

This implementation does not return the same path many times.

comment:12 Changed 21 months ago by 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

comment:13 Changed 5 months ago by anonymous

Is it not added yet?

comment:14 Changed 5 months ago by anonymous

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

comment:15 in reply to:  13 Changed 5 months ago by 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.

comment:16 Changed 4 months ago by andrewmw94

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

comment:17 in reply to:  16 ; Changed 4 months ago by 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.

comment:18 in reply to:  17 Changed 4 months ago by 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

Note: See TracTickets for help on using tickets.