Boost Graph Library Dijkstra's algorithm fails

[NordCoder]

Hi Daniweb,

I doing an assignment for a course I'm taking at my university. The assignment involves using the Boost Graph Library (version 1.43). So far, I haven't had any trouble at all. Then I tried calling dijkstra_shortest_paths(...). The named parameters way of calling this function does not work in MSVC++ which I am using, so I went with the other. Here's a link to the algorithm. I defined a couple of bundled properties and typedefs as follows:

struct VertexProperty
{
   string id;
};

struct EdgeProperty
{
   string id;
   int weight;
};

typedef adjacency_list<vecS, listS, undirectedS, VertexProperty, EdgeProperty, no_property, listS> UndirectedGraph;
typedef graph_traits<UndirectedGraph>::vertex_descriptor BVertexDescriptor;
typedef graph_traits<UndirectedGraph>::edge_descriptor BEdgeDescriptor;

Here's the code involved (the graph is populated elsewhere):

BVertexDescriptor vertexDescriptor = vertex(0, uGraph) // uGraph is an undirected graph
vector<BVertexDescriptor> path(num_vertices(uGraph), 0);

property_map<UndirectedGraph, vertex_index_t>::type indexmap = get(vertex_index, uGraph);
vector<int> distances(num_vertices(uGraph));

dijkstra_shortest_paths(uGraph, vertexDescriptor, &path[0], distance_map(make_iterator_property_map(distances.begin(), get(vertex_index, uGraph))),
weight_map(get(&EdgeProperty::weight, uGraph)),
indexmap, std::less<int>(), closed_plus<int>(), (std::numeric_limits<int>::max)(), 0,
default_dijkstra_visitor());

What I think is one problem is that I use a std::list for the vertices, which abolishes invalidation but lacks an indexmap. I don't know how to create one though. There also might be a problem with the use of bundled properties, but I am not sure.

I get 23 errors in all. These errors are really long, so I will only post all of them on request. Here's the first one though:

1>------ Build started: Project: FileParserTest, Configuration: Debug Win32 ------
1>Compiling...
1>BoostGraph.cpp
1>c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\fileparsertest\fileparsertest\boostgraph.cpp(145) : warning C4018: '<' : signed/unsigned mismatch
1>c:\documents and settings\admin\dokumenter\boost\boost_1_43_0\boost\graph\dijkstra_shortest_paths.hpp(377) : error C2784: 'void boost::put(const boost::two_bit_color_map<IndexMap> &,property_traits<PA>::key_type,boost::two_bit_color_type)' : could not deduce template argument for 'const boost::two_bit_color_map<IndexMap> &' from 'boost::bgl_named_params<T,Tag,Base>'
1> with
1> [
1> T=boost::iterator_property_map<std::_Vector_iterator<int,std::allocator<int>>,boost::adj_list_vertex_property_map<UndirectedGraph,boost::detail::error_property_not_found,boost::detail::error_property_not_found &,boost::vertex_index_t>,int,int &>,
1> Tag=boost::vertex_distance_t,
1> Base=boost::no_property
1> ]
1> c:\documents and settings\admin\dokumenter\boost\boost_1_43_0\boost\graph\two_bit_color_map.hpp(79) : see declaration of 'boost::put'
1> c:\documents and settings\admin\dokumenter\boost\boost_1_43_0\boost\graph\dijkstra_shortest_paths.hpp(355) : see reference to function template instantiation 'void boost::dijkstra_shortest_paths<VertexListGraph,DijkstraVisitor,PredecessorMap,DistanceMap,WeightMap,IndexMap,Compare,Combine,DistInf,DistZero,boost::two_bit_color_map<IndexMap>>(const VertexListGraph &,void *,PredecessorMap,DistanceMap,WeightMap,IndexMap,Compare,Combine,DistInf,DistZero,DijkstraVisitor,ColorMap)' being compiled
1> with
1> [
1> VertexListGraph=UndirectedGraph,
1> DijkstraVisitor=boost::dijkstra_visitor<>,
1> PredecessorMap=void **,
1> DistanceMap=boost::bgl_named_params<boost::iterator_property_map<std::_Vector_iterator<int,std::allocator<int>>,boost::adj_list_vertex_property_map<UndirectedGraph,boost::detail::error_property_not_found,boost::detail::error_property_not_found &,boost::vertex_index_t>,int,int &>,boost::vertex_distance_t,boost::no_property>,
1> WeightMap=boost::bgl_named_params<boost::bundle_property_map<boost::adjacency_list<boost::vecS,boost::listS,boost::undirectedS,VertexProperty,EdgeProperty,boost::no_property,boost::listS>,boost::detail::edge_desc_impl<boost::undirected_tag,void *>,EdgeProperty,int>,boost::edge_weight_t,boost::no_property>,
1> IndexMap=boost::adj_list_vertex_property_map<UndirectedGraph,boost::detail::error_property_not_found,boost::detail::error_property_not_found &,boost::vertex_index_t>,
1> Compare=std::less<int>,
1> Combine=boost::closed_plus<int>,
1> DistInf=std::numeric_limits<int>::_Ty,
1> DistZero=int,
1> ColorMap=boost::two_bit_color_map<boost::adj_list_vertex_property_map<UndirectedGraph,boost::detail::error_property_not_found,boost::detail::error_property_not_found &,boost::vertex_index_t>>
1> ]
1> c:\documents and settings\admin\dokumenter\boost\boost_1_43_0\boost\graph\dijkstra_shortest_paths.hpp(403) : see reference to function template instantiation 'void boost::dijkstra_shortest_paths<VertexListGraph,DijkstraVisitor,PredecessorMap,DistanceMap,WeightMap,IndexMap,Compare,Combine,DistInf,DistZero,char,boost::detail::unused_tag_type,boost::no_property>(const VertexListGraph &,void *,PredecessorMap,DistanceMap,WeightMap,IndexMap,Compare,Combine,DistInf,DistZero,DijkstraVisitor,const boost::bgl_named_params<T,Tag> &,boost::graph::detail::no_parameter)' being compiled
1> with
1> [
1> VertexListGraph=UndirectedGraph,
1> DijkstraVisitor=boost::dijkstra_visitor<>,
1> PredecessorMap=void **,
1> DistanceMap=boost::bgl_named_params<boost::iterator_property_map<std::_Vector_iterator<int,std::allocator<int>>,boost::adj_list_vertex_property_map<UndirectedGraph,boost::detail::error_property_not_found,boost::detail::error_property_not_found &,boost::vertex_index_t>,int,int &>,boost::vertex_distance_t,boost::no_property>,
1> WeightMap=boost::bgl_named_params<boost::bundle_property_map<boost::adjacency_list<boost::vecS,boost::listS,boost::undirectedS,VertexProperty,EdgeProperty,boost::no_property,boost::listS>,boost::detail::edge_desc_impl<boost::undirected_tag,void *>,EdgeProperty,int>,boost::edge_weight_t,boost::no_property>,
1> IndexMap=boost::adj_list_vertex_property_map<UndirectedGraph,boost::detail::error_property_not_found,boost::detail::error_property_not_found &,boost::vertex_index_t>,
1> Compare=std::less<int>,
1> Combine=boost::closed_plus<int>,
1> DistInf=std::numeric_limits<int>::_Ty,
1> DistZero=int,
1> T=char,
1> Tag=boost::detail::unused_tag_type
1> ]
1> c:\documents and settings\admin\dokumenter\dtu\5. semester\cbs specialkursus\msvc++ project\fileparsertest\fileparsertest\boostgraph.cpp(141) : see reference to function template instantiation 'void boost::dijkstra_shortest_paths<UndirectedGraph,boost::dijkstra_visitor<>,void**,boost::bgl_named_params<T,Tag,Base>,boost::bgl_named_params<boost::bundle_property_map<Graph,Descriptor,Bundle,int>,boost::edge_weight_t,Base>,boost::adj_list_vertex_property_map<Graph,ValueType,Reference,boost::vertex_index_t>,std::less<_Ty>,boost::closed_plus<int>,std::numeric_limits<int>::_Ty,int>(const VertexListGraph &,void *,PredecessorMap,DistanceMap,WeightMap,IndexMap,Compare,Combine,DistInf,DistZero,DijkstraVisitor)' being compiled
1> with
1> [
1> T=boost::iterator_property_map<std::_Vector_iterator<int,std::allocator<int>>,boost::adj_list_vertex_property_map<UndirectedGraph,boost::detail::error_property_not_found,boost::detail::error_property_not_found &,boost::vertex_index_t>,int,int &>,
1> Tag=boost::vertex_distance_t,
1> Base=boost::no_property,
1> Graph=boost::adjacency_list<boost::vecS,boost::listS,boost::undirectedS,VertexProperty,EdgeProperty,boost::no_property,boost::listS>,
1> Descriptor=boost::detail::edge_desc_impl<boost::undirected_tag,void *>,
1> Bundle=EdgeProperty,
1> ValueType=boost::detail::error_property_not_found,
1> Reference=boost::detail::error_property_not_found &,
1> _Ty=int,
1> VertexListGraph=UndirectedGraph,
1> PredecessorMap=void **,
1> DistanceMap=boost::bgl_named_params<boost::iterator_property_map<std::_Vector_iterator<int,std::allocator<int>>,boost::adj_list_vertex_property_map<UndirectedGraph,boost::detail::error_property_not_found,boost::detail::error_property_not_found &,boost::vertex_index_t>,int,int &>,boost::vertex_distance_t,boost::no_property>,
1> WeightMap=boost::bgl_named_params<boost::bundle_property_map<boost::adjacency_list<boost::vecS,boost::listS,boost::undirectedS,VertexProperty,EdgeProperty,boost::no_property,boost::listS>,boost::detail::edge_desc_impl<boost::undirected_tag,void *>,EdgeProperty,int>,boost::edge_weight_t,boost::no_property>,
1> IndexMap=boost::adj_list_vertex_property_map<UndirectedGraph,boost::detail::error_property_not_found,boost::detail::error_property_not_found &,boost::vertex_index_t>,
1> Compare=std::less<int>,
1> Combine=boost::closed_plus<int>,
1> DistInf=std::numeric_limits<int>::_Ty,
1> DistZero=int,
1> DijkstraVisitor=boost::dijkstra_visitor<>
1> ]