[Boost-users] Parallel Dijkstra with Predecessors

Subject: [Boost-users] Parallel Dijkstra with Predecessors
From: Florian Meier (florian.meier_at_[hidden])
Date: 2014-02-14 12:49:53

Hi,
I am trying to use the parallel Dijkstra implementation with predecessors, 
but I am not able to compile it. Please have a look at the following diff against
boost_1_53_0/libs/graph_parallel/example/dijkstra_shortest_paths.cpp
(You can find the modified version attached.)

-------------------------------------------
@@ -45,8 +45,10 @@
 
 /* An undirected, weighted graph with distance values stored on the
    vertices. */
+typedef adjacency_list_traits<vecS, distributedS<mpi_process_group, vecS>, undirectedS>::vertex_descriptor vertex_descriptor;
+
 typedef adjacency_list<vecS, distributedS<mpi_process_group, vecS>, undirectedS,
-                       /*Vertex properties=*/property<vertex_distance_t, float>,
+                       /*Vertex properties=*/property<vertex_distance_t, float, property<vertex_predecessor_t, vertex_descriptor> >,
                        /*Edge properties=*/property<edge_weight_t, float> >
   Graph;
 
@@ -71,7 +73,7 @@
 
   // Compute shortest paths from vertex 0
   dijkstra_shortest_paths(g, start,
-                          distance_map(get(vertex_distance, g)));
+                          distance_map(get(vertex_distance, g)).predecessor_map(get(vertex_predecessor, g)));
 
   // Output a Graphviz DOT file
   std::string outfile = filename;
-------------------------------------------

This (actually get(vertex_predecessor, g)) gives me

-------------------------------------------
In file included from /usr/include/boost/property_map/parallel/distributed_property_map.hpp:706:0,
                 from /usr/include/boost/property_map/property_map.hpp:645,
                 from /usr/include/boost/graph/properties.hpp:19,
                 from /usr/include/boost/mpi/graph_communicator.hpp:30,
                 from /usr/include/boost/mpi.hpp:27,
                 from /usr/include/boost/graph/distributed/mpi_process_group.hpp:30,
                 from dijkstra_shortest_paths.cpp:16:
/usr/include/boost/property_map/parallel/impl/distributed_property_map.ipp: In instantiation of ‘void boost::parallel::distributed_property_map<ProcessGroup, GlobalMap, StorageMap>::handle_message<Reduce>::handle_multiput(int, int, const std::vector<boost::unsafe_pair<typename boost::property_traits<StorageMap>::key_type, typename boost::property_traits<StorageMap>::value_type> >&, boost::graph::parallel::trigger_receive_context) [with Reduce = boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::parallel::global_descriptor<long unsigned int> >; ProcessGroup = boost::graph::distributed::mpi_process_group; GlobalMap = boost::detail::parallel::global_descriptor_property_map<long unsigned int>; StorageMap = boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > 
>, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>*, boost::detail::parallel::global_descriptor<long unsigned int>, boost::detail::parallel::global_descriptor<long unsigned int>&, boost::vertex_predecessor_t>; typename boost::property_traits<StorageMap>::value_type = boost::detail::parallel::global_descriptor<long unsigned int>; typename boost::property_traits<StorageMap>::key_type = long unsigned int]’:
/usr/include/boost/property_map/parallel/impl/distributed_property_map.ipp:255:18:   required from ‘void boost::parallel::distributed_property_map<ProcessGroup, GlobalMap, StorageMap>::handle_message<Reduce>::setup_triggers(boost::parallel::distributed_property_map<ProcessGroup, GlobalMap, StorageMap>::process_group_type&) [with Reduce = boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::parallel::global_descriptor<long unsigned int> >; ProcessGroup = boost::graph::distributed::mpi_process_group; GlobalMap = boost::detail::parallel::global_descriptor_property_map<long unsigned int>; StorageMap = boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, shor
t int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>*, boost::detail::parallel::global_descriptor<long unsigned int>, boost::detail::parallel::global_descriptor<long unsigned int>&, boost::vertex_predecessor_t>; boost::parallel::distributed_property_map<ProcessGroup, GlobalMap, StorageMap>::process_group_type = boost::graph::distributed::mpi_process_group]’
/usr/include/boost/property_map/parallel/impl/distributed_property_map.ipp:35:3:   required from ‘boost::parallel::distributed_property_map<ProcessGroup, GlobalMap, StorageMap>::distributed_property_map(const ProcessGroup&, const GlobalMap&, const StorageMap&, const Reduce&) [with Reduce = boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::parallel::global_descriptor<long unsigned int> >; ProcessGroup = boost::graph::distributed::mpi_process_group; GlobalMap = boost::detail::parallel::global_descriptor_property_map<long unsigned int>; StorageMap = boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, floa
t> > >, boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>*, boost::detail::parallel::global_descriptor<long unsigned int>, boost::detail::parallel::global_descriptor<long unsigned int>&, boost::vertex_predecessor_t>]’
/usr/include/boost/graph/distributed/adjacency_list.hpp:3468:50:   required from ‘typename boost::property_map<boost::adjacency_list<OutEdgeListS, boost::distributedS<ProcessGroup, InVertexListS, InDistribution>, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS>, Property>::type boost::get(Property, boost::adjacency_list<OutEdgeListS, boost::distributedS<ProcessGroup, InVertexListS, InDistribution>, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS>&) [with Property = boost::vertex_predecessor_t; OutEdgeListS = boost::vecS; ProcessGroup = boost::graph::distributed::mpi_process_group; InVertexListS = boost::vecS; InDistribution = boost::defaultS; DirectedS = boost::undirectedS; VertexProperty = boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >; EdgeProperty = boost::property<boost::edge_weight_t, float>; GraphProperty = boost::no_property; EdgeL
istS = boost::listS; typename boost::property_map<boost::adjacency_list<OutEdgeListS, boost::distributedS<ProcessGroup, InVertexListS, InDistribution>, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS>, Property>::type = boost::parallel::distributed_property_map<boost::graph::distributed::mpi_process_group, boost::detail::parallel::global_descriptor_property_map<long unsigned int>, boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<b
oost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>*, boost::detail::parallel::global_descriptor<long unsigned int>, boost::detail::parallel::global_descriptor<long unsigned int>&, boost::vertex_predecessor_t> >]’
dijkstra_shortest_paths.cpp:77:106:   required from here
/usr/include/boost/property_map/parallel/impl/distributed_property_map.ipp:236:47: error: no match for call to ‘(boost::property_reduce<boost::vertex_predecessor_t>::apply<boost::detail::parallel::global_descriptor<long unsigned int> >) (const long unsigned int&, boost::parallel::distributed_property_map<boost::graph::distributed::mpi_process_group, boost::detail::parallel::global_descriptor_property_map<long unsigned int>, boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>, boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::property<boost::vertex_distance_t
, float, boost::property<boost::vertex_predecessor_t, boost::detail::parallel::global_descriptor<long unsigned int> > >, boost::property<boost::edge_locally_owned_t, bool, boost::property<boost::edge_target_processor_id_t, short int, boost::property<boost::edge_weight_t, float> > >, boost::no_property, boost::listS>*, boost::detail::parallel::global_descriptor<long unsigned int>, boost::detail::parallel::global_descriptor<long unsigned int>&, boost::vertex_predecessor_t> >::value_type&, const boost::detail::parallel::global_descriptor<long unsigned int>&)’
                              values[i].second));
                                               ^
In file included from /usr/include/boost/graph/distributed/breadth_first_search.hpp:23:0,
                 from /usr/include/boost/graph/breadth_first_search.hpp:404,
                 from /usr/include/boost/graph/dijkstra_shortest_paths.hpp:21,
                 from dijkstra_shortest_paths.cpp:19:
/usr/include/boost/graph/parallel/properties.hpp:90:11: note: candidates are:
     class apply
           ^
/usr/include/boost/graph/parallel/properties.hpp:95:9: note: T boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T) const [with T = boost::detail::parallel::global_descriptor<long unsigned int>]
       T operator()(T key) const { return key; }
         ^
/usr/include/boost/graph/parallel/properties.hpp:95:9: note:   candidate expects 1 argument, 3 provided
/usr/include/boost/graph/parallel/properties.hpp:96:9: note: T boost::property_reduce<boost::vertex_predecessor_t>::apply<T>::operator()(T, T, T) const [with T = boost::detail::parallel::global_descriptor<long unsigned int>]
       T operator()(T key, T, T y) const { return y; }
         ^
/usr/include/boost/graph/parallel/properties.hpp:96:9: note:   no known conversion for argument 1 from ‘const long unsigned int’ to ‘boost::detail::parallel::global_descriptor<long unsigned int>’
-------------------------------------------

What is wrong here?
Greetings,
Florian