Boost C++ Libraries: Ticket #11804: Contribution: edge-disjoint k-shortest paths

attachment set

Wed, 18 Nov 2015 22:05:09 GMT

attachment → edge_disjoint_ksp.hpp

the implementation

attachment set

Wed, 18 Nov 2015 22:05:33 GMT

attachment → edge_disjoint_ksp.cc

the unit test

attachment set

Mon, 23 Nov 2015 11:04:47 GMT

attachment → edge_disjoint_ksp.2.hpp

the implementation - v2

attachment set

Mon, 23 Nov 2015 11:05:24 GMT

attachment → edge_disjoint_ksp.2.cc

the unit test - v2

Mon, 23 Nov 2015 11:09:54 GMT

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.

Mon, 23 Nov 2015 11:20:28 GMT

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.

attachment set

Thu, 03 Dec 2015 08:10:03 GMT

attachment → edge_disjoint_ksp.3.hpp

attachment set

Thu, 03 Dec 2015 08:10:33 GMT

attachment → edge_disjoint_ksp.3.cc

the unit test - v3

Thu, 03 Dec 2015 08:23:32 GMT

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).

attachment set

Tue, 08 Dec 2015 09:07:09 GMT

attachment → edge_disjoint_ksp.4.hpp

the implementation - v4

attachment set

Tue, 08 Dec 2015 09:08:38 GMT

attachment → custom_dijkstra_call.hpp

the implementation of the custom dijkstra call - v1

attachment set

Tue, 08 Dec 2015 09:09:21 GMT

attachment → exclude_filter.hpp

the implementation of the exclude filter - v1

Tue, 08 Dec 2015 09:10:51 GMT

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.

Tue, 08 Dec 2015 09:12:56 GMT

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!

attachment set

Tue, 08 Dec 2015 09:37:28 GMT

attachment → edge_disjoint_ksp.5.hpp

the implementation - v5

attachment set

Tue, 08 Dec 2015 09:37:51 GMT

attachment → custom_dijkstra_call.2.hpp

the implementation of the custom dijkstra call - v2

Tue, 08 Dec 2015 09:39:38 GMT

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

Wed, 09 Dec 2015 09:52:56 GMT

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

anonymous — Mon, 14 Mar 2016 21:13:32 GMT

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

attachment set

Mon, 14 Mar 2016 21:26:19 GMT

attachment → edge_disjoint_ksp.6.hpp

the implementation - v6

attachment set

Mon, 14 Mar 2016 21:26:57 GMT

attachment → edge_disjoint_ksp.4.cc

the unit test - v4

Mon, 14 Mar 2016 21:29:25 GMT

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.