Re: [Boost-users] Parallel Dijkstra with Predecessors

Subject: Re: [Boost-users] Parallel Dijkstra with Predecessors
From: Marcin Zalewski (marcin.zalewski_at_[hidden])
Date: 2014-02-25 15:47:43

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

  template<>
  struct property_reduce<vertex_predecessor_t>
  {
    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 <florian.meier_at_[hidden]> 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<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 unsigne
>  d 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_i
>  d_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_weigh
>  t_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_proper
>  ty; 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::p
>  roperty<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_d
>  istance_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
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users