Re: [Boost-users] Parallel Dijkstra with Predecessors

25 Feb 2014


      I have exactly the same problem. I have been able to "fix" it by
modifying the following code:

  template<>
  struct property_reduce
  {
    template<typename T>
    class apply
    {
    public:
      BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);

      template<typename Key>
      T operator()(const Key&) const { return T(); }
      template<typename Key>
      T operator()(const Key&, T, T y) const { return y; }
    };
  };

Check the original version in
/opt/local/include/boost/graph/parallel/properties.hpp (sorry for no
diff). Basically, I have changed the operators to take the key as the
parameter. If this is not done, key must be of the same type as T,
which is not the case because of how handle_multiput is implemented
(in boost/property_map/parallel/impl/distributed_property_map.ipp).
There, reduce is called with local key type, but the current
implementation of reduce (without Key as a template argument) prevents
using local key values. I think that the current implementation is a
bug, and my modification is probably the fix of lowest effort. :)

-m

On Fri, Feb 14, 2014 at 12:49 PM, Florian Meier  wrote:
...
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, undirectedS>::vertex_descriptor vertex_descriptor;
+
 typedef adjacency_list, undirectedS,
-                       /*Vertex properties=*/property,
+                       /*Vertex properties=*/property >,
                        /*Edge properties=*/property >
   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::handle_message<Reduce>::handle_multiput(int, int, const std::vector >&, boost::graph::parallel::trigger_receive_context) [with Reduce = boost::property_reduceboost::vertex_predecessor_t::apply; 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::property > >, boost::no_property, boost::listS>, boost::adjacency_list >, boost::property > >, 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::handle_message<Reduce>::setup_triggers(boost::parallel::distributed_property_map::process_group_type&) [with Reduce = boost::property_reduceboost::vertex_predecessor_t::apply; 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::property > >, boost::no_property, boost::listS>, boost::adjacency_list >, boost::property > >, 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::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::distributed_property_map(const ProcessGroup&, const GlobalMap&, const StorageMap&, const Reduce&) [with Reduce = boost::property_reduceboost::vertex_predecessor_t::apply; 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::property > >, boost::no_property, boost::listS>, boost::adjacency_list >, boost::property > >, 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, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS>, Property>::type boost::get(Property, boost::adjacency_list, 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 >; EdgeProperty = boost::property; GraphProperty = boost::no_proper
 ty; EdgeL
istS = boost::listS; typename boost::property_map, DirectedS, VertexProperty, EdgeProperty, GraphProperty, EdgeListS>, Property>::type = boost::parallel::distributed_property_map >, boost::property > >, boost::no_property, boost::listS>, boost::adjacency_list >, boost::property > >, 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_reduceboost::vertex_predecessor_t::apply) (const long unsigned int&, boost::parallel::distributed_property_map >, boost::property > >, boost::no_property, boost::listS>, boost::adjacency_list >, boost::property > >, 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_reduceboost::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_reduceboost::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
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

    

Re: [Boost-users] Parallel Dijkstra with Predecessors

Marcin Zalewski