Contribution: edge-disjoint k-shortest paths

[Irek Szcześniak <irek@…>]

Hi,

I want to contribute a function that calculates edge-disjoint k-shortest paths.

The algorithm searches for a shortest path. Then it disables the edges of the shortest path, and repeats the search. On so on, until no path can be found.

I'm attaching the source file and a unit test.

There are two things that bug me in the code:

• the predecessor map is hardcoded as:

boost::vector_property_map<edge_descriptor> pred(num_vertices(g));

while perhaps it should depend on the graph type,

• the formatting of this call is ugly:

boost::dijkstra_shortest_paths

(fg, s,

visitor(make_dijkstra_visitor(record_edge_predecessors(pred, on_edge_relaxed()))));

I would appreciate it, if someone could give me a hint on these two problems.

I would also appreciate very much any comments and improvements.

Thanks!

[Irek Szcześniak <irek@…>]

the implementation

[Irek Szcześniak <irek@…>]

the unit test

[Irek Szcześniak <irek@…>]

the implementation - v2

[Irek Szcześniak <irek@…>]

the unit test - v2

[Irek Szcześniak <irek@…>]

I attached the second version of the implementation and the unit test. Now the function returns its results in a list, not in a multiset anymore.

[Irek Szcześniak <irek@…>]

The reasoning for the used data types:

• the excluded edges are stored in a set in edksp_filter, to make sure that the edge lookup is fast,

• the path is a list (and not a vector), because the length of the path is not known up front (building a path as a vector could resize the vector), and the paths are not expected to be heavily used to merit the use of a vector,

• for the same reasons as for a path, the found paths are returned in a list, not a vector.

[Irek Szcześniak <irek@…>]

the unit test - v3

[Irek Szcześniak <irek@…>]

I attached the third version of the implementation and the unit test. This revision has a number of changes:

• bug fix: the Dijkstra call is using the right property map (wm), and not the graph's built in,

• new feature: the user is allowed to provide an optional argument K, which limits the search to at most K shortest paths,

• performance improvement: the Dijkstra search is stopped as soon as the shortest path to the destination vertex is found,

• added more comments,

• moved the call to Dijkstra to a separate function, and made the call well-formatted (i.e., it's not very long).

[Irek Szcześniak <irek@…>]

the implementation - v4

[Irek Szcześniak <irek@…>]

the implementation of the custom dijkstra call - v1

[Irek Szcześniak <irek@…>]

the implementation of the exclude filter - v1

[Irek Szcześniak <irek@…>]

Made the implementation more generic by allowing a user to provide the vector index map. I also moved the implementation of the exclude filter and the custom dijkstra call to separate files.

[Irek Szcześniak <irek@…>]

Thanks to Daniel Hofmann for his advice on how to better call the Dijkstra function, i.e. to use the iterator_property_map, and to let the user provide the vector index map. Many thanks!

[Irek Szcześniak <irek@…>]

the implementation - v5

[Irek Szcześniak <irek@…>]

the implementation of the custom dijkstra call - v2

[Irek Szcześniak <irek@…>]

In revisions just added (edge_disjoint_ksp.5.hpp and custom_dijkstra_call.2.hpp), I only cleaned up the inclusion of header files.

[Irek Szcześniak <irek@…>]

I would appreciate some advice on what I should do next to contribute this code. Please let me know.

[anonymous]

Compile the unit test like this:

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

[Irek Szcześniak <irek@…>]

the implementation - v6

[Irek Szcześniak <irek@…>]

the unit test - v4

[Irek Szcześniak <irek@…>]

I added a simplified implementation and a modified unit test. This implementation does not use the exclude_filter.hpp, which I implemented. Instead, we use the filter provided by the filtered_graph.