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