Boost graph library causing errors when applying dijkstra's algorithm

Question

I have been loosely following this example, this one, and this stack overflow post to try to apply Dijkstra's algorithm to find the cost of the shortest path between two nodes.

If I try to follow the first example, I get an error with the typedef statement for NameMap. This error is cryptic, verbose, and I don't quite know what to do with it.

If I try to follow the second example (copy-pasted from the Boost documentation!!) it does not compile. The error is even more cryptic and verbose.

The third one (the stack overflow post) relies on the same typedef as the first one.

Is this user error? It probably is, but how should I interpret an error message that spawns from the library code?

Update 1

I am using g++ (Debian 4.8.2-21) 4.8.2 from debian testing.

Update 2

Here is a condensed version of the source code that doesn't work. There are two lines prefaced by "// The following line causes an error" are the ones in question.

Update 3 I have changed

typedef adjacency_list<listS, vecS, directedS, allow_parallel_edge_tag, EdgeWeightProperty> Graph;

typedef adjacency_list<listS, vecS, directedS, no_property            , EdgeWeightProperty> Graph;

Answer 1

Your first attempt didn't define a property with the vertex_name_t tag (or pass it as a adjacency_list template parameter), so when you try to create a property_map with that tag the compiler emits an error.

Your code:

typedef property<edge_weight_t, Weight> EdgeWeightProperty;
typedef boost::adjacency_list<listS, vecS, directedS, allow_parallel_edge_tag, EdgeWeightProperty> Graph;
                                                  //  ^ What's this?

The example code you cited:

typedef boost::property<boost::edge_weight_t, Weight> WeightProperty;
typedef boost::property<boost::vertex_name_t, std::string> NameProperty;  // <-- not in your code
typedef boost::adjacency_list < boost::listS, boost::vecS, boost::directedS, NameProperty, WeightProperty > Graph;
                                                                         //  ^ Used here

I have no idea why you are passing allow_parallel_edge_tag as a template parameter. If I'm reading the documentation correctly, that struct is designed for parallel_edge_traits specializations when you are using custom container types.

Edit: The second case is actually easy to diagnose once you have the code. Going through the error messages emitted by the compiler, we look for reasons why the compiler didn't select the 3-parameter overload for dijkstra_shortest_paths. A lot of the messages merely tells you that it rejected overloads with about a dozen parameters - as it should!

Now, this error message (emitted by g++ using Coliru) is pertinent, because it tells you why compiler rejected the three-parameter version:

In file included from main.cpp:5:0:
/usr/local/include/boost/graph/dijkstra_shortest_paths.hpp:602:3: note: void boost::
dijkstra_shortest_paths(const VertexListGraph&, typename boost::graph_traits<Graph>::
vertex_descriptor, const boost::bgl_named_params<T, Tag, Base>&) [ /* irrelevant stuff
telling you how it deduced the template parameters here */ ] <near match>
   dijkstra_shortest_paths
   ^
/usr/local/include/boost/graph/dijkstra_shortest_paths.hpp:602:3: note:   no known conversion for
 argument 2 from 'long int [6]' to 'boost::graph_traits<boost::adjacency_list<boost::listS, 
boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, long int> > 
>::vertex_descriptor {aka long unsigned int}'

You passed s, the array containing source vertices, as the second parameter designating the starting vertex, when you should have passed v0, and the compiler is rightfully complaining that it cannot convert an array of longs to a single vertex.