[Boost-users] Graph concepts for Dijkstra shortest-path searches

Subject: [Boost-users] Graph concepts for Dijkstra shortest-path searches
From: Clayton Davis (Clayton.Davis_at_[hidden])
Date: 2014-09-22 17:12:37

Hi,

I am somewhat uncertain on which concepts are required for the Dijkstra searches in the BGL and parallel BGL.

For the sequential BGL, documentation at http://www.boost.org/doc/libs/1_56_0/libs/graph/doc/dijkstra_shortest_paths.html would seem to indicate that a VertexListGraph is required, even when the no_init version is used.  Looking at the code, I think that is accurate - use of the index map at https://github.com/boostorg/graph/blob/master/include/boost/graph/dijkstra_shortest_paths.hpp#L368 seems to require vertex list traversal - but I would also think that defeats the purpose of the no_init option.

Conversely, for the parallel BGL documentation at http://www.boost.org/doc/libs/1_56_0/libs/graph_parallel/doc/html/dijkstra_shortest_paths.html says only that DistributedGraph is required, which is a refinement of Graph but not VertexListGraph or IncidenceGraph.  However, just a little bit of searching seems to show that the parallel Dijkstra search requires both, along with perhaps PropertyGraph (see for instance https://github.com/boostorg/graph_parallel/blob/master/include/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp#L117 and https://github.com/boostorg/graph_parallel/blob/master/include/boost/graph/distributed/eager_dijkstra_shortest_paths.hpp#L358).  I won't pretend to understand the code; but I would expect these functions to require something stronger than the documentation indicates.

Could someone please clarify what the requirements are for these functions?  Any help is greatly appreciated.

Thanks,

Clayton