Re: [Boost-users] [BGL] Distributed Dijkstra vertex_iterator

Subject: Re: [Boost-users] [BGL] Distributed Dijkstra vertex_iterator
From: Bruno Santos (bmfs_at_[hidden])
Date: 2010-06-03 16:04:37

After further study I understood my problem.
I was totally ignoring that the vertices were distributed by the processors
and each processor only has part of the vertices and edges.

Now my problem is:
Is there any faster way to gather the distance map from the
dijkstra_shortest_paths?
The obvious solution is to manually exchange messages between the
processors. But certainly there is a more transparent way to do that.

I was looking at the distributed property map but I wasn't able to find any
example to check if that is what I need.

Best,
Bruno Santos

On Wed, Jun 2, 2010 at 7:53 PM, Bruno Santos <bmfs_at_[hidden]> wrote:

> Hi all,
>
> I'm fairly new to boost so please bear my ignorance.
>
> I'm trying to implement the example of the distributed Dijkstra using the
> Parallel BGL and I'm having problems when iterating through the distance
> map.
>
> This is the code. Just updated the dijkstra_example.cpp with the Parallel
> BGL Dijkstra instructions.
>
> #include <boost/config.hpp>
> #include <iostream>
> #include <fstream>
> #include <stdio.h>
> #include <iomanip>
> #include <vector>
>
> #include <boost/graph/use_mpi.hpp>
> #include <boost/graph/distributed/mpi_process_group.hpp>
> #include <boost/graph/dijkstra_shortest_paths.hpp>
> #include <boost/graph/distributed/adjacency_list.hpp>
>
> using namespace boost;
> using boost::graph::distributed::mpi_process_group;
>
> int main(int argc, char* argv[])
> {
>     boost::mpi::environment env(argc,argv);
>
>     typedef adjacency_list<listS,
>         distributedS<mpi_process_group, vecS>,
>         directedS,
>         no_property,                 // Vertex properties
>         property<edge_weight_t, int> // Edge properties
>         > graph_t;
>     typedef graph_traits < graph_t >::vertex_descriptor vertex_descriptor;
>     typedef graph_traits < graph_t >::edge_descriptor edge_descriptor;
>     typedef std::pair<int, int> Edge;
>
>     const int num_nodes = 5;
>     enum nodes { A, B, C, D, E };
>     char name[] = "ABCDE";
>     Edge edge_array[] = { Edge(A, C), Edge(B, B), Edge(B, D), Edge(B, E),
>         Edge(C, B), Edge(C, D), Edge(D, E), Edge(E, A), Edge(E, B)
>     };
>     int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1 };
>     int num_arcs = sizeof(edge_array) / sizeof(Edge);
> #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
>     graph_t g(num_nodes);
>     property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight,
> g);
>     for (std::size_t j = 0; j < num_arcs; ++j) {
>         edge_descriptor e; bool inserted;
>          tie(e, inserted) = add_edge(edge_array[j].first,
> edge_array[j].second, g);
>         weightmap[e] = weights[j];
>     }
> #else
>     graph_t g(edge_array, edge_array + num_arcs, weights, num_nodes);
>     property_map<graph_t, edge_weight_t>::type weightmap = get(edge_weight,
> g);
> #endif
>     std::vector<vertex_descriptor> p(num_vertices(g));
>     std::vector<int> d(num_vertices(g));
>     vertex_descriptor s = vertex(A, g);
>
> #if defined(BOOST_MSVC) && BOOST_MSVC <= 1300
>   // VC++ has trouble with the named parameters mechanism
>     property_map<graph_t, vertex_index_t>::type indexmap =
> get(vertex_index, g);
>     dijkstra_shortest_paths(g, s, &p[0], &d[0], weightmap, indexmap,
>         std::less<int>(), closed_plus<int>(),
>         (std::numeric_limits<int>::max)(), 0,
>         default_dijkstra_visitor());
> #else
>     dijkstra_shortest_paths
>       (g, s,
>        predecessor_map(
>          make_iterator_property_map(p.begin(), get(vertex_index, g))).
>        distance_map(
>          make_iterator_property_map(d.begin(), get(vertex_index, g)))
>        );
> #endif
>
>     std::cout << "distances and parents:" << std::endl;
>     graph_traits < graph_t >::vertex_iterator vi, vend;
>     for (tie(vi, vend) = vertices(g); vi != vend; ++vi) {
>         std::cout << "distance(" << name[*vi] << ") = " << d[*vi] << ", ";
>         std::cout << "parent(" << name[*vi] << ") = " << name[p[*vi]] <<
> std::
>         endl;
>     }
>     std::cout << std::endl;
>
>     return 0;
> }
>
> The compiler line I'm using is:
>
> mpic++ -I/usr/include/boost/graph/distributed/ -I/usr/include/boost/
> -L/usr/lib/ /usr/lib/libboost_mpi-mt.so
> /usr/lib/libboost_serialization-mt.so /usr/lib/libboost_graph_parallel-mt.so
> /usr/lib/libboost_system-mt.so dij.cpp -o dijkstr
>
> and the error is:
>
> In file included from /usr/include/c++/4.4/backward/hash_set:59,
>                  from /usr/include/boost/graph/adjacency_list.hpp:25,
>                  from
> /usr/include/boost/graph/distributed/adjacency_list.hpp:18,
>                  from dij.cpp:11:
> /usr/include/c++/4.4/backward/backward_warning.h:28:2: warning: #warning
> This file includes at least one deprecated or antiquated header which may be
> removed without further notice at a future date. Please use a non-deprecated
> interface with equivalent functionality instead. For a listing of
> replacement headers and interfaces, consult the file backward_warning.h. To
> disable this warning use -Wno-deprecated.
> dij.cpp: In function ‘int main(int, char**)’:
> dij.cpp:74: error: no match for ‘operator[]’ in
> ‘name[((boost::iterator_facade<boost::transform_iterator<boost::detail::parallel::global_descriptor<long
> unsigned int>::generator, boost::counting_iterator<long unsigned int,
> boost::use_default, boost::use_default>, boost::use_default,
> boost::use_default>, boost::detail::parallel::global_descriptor<long
> unsigned int>, boost::random_access_traversal_tag,
> boost::detail::parallel::global_descriptor<long unsigned int>, long int>*)(&
> vi))->boost::iterator_facade<I, V, TC, R, D>::operator* [with Derived =
> boost::transform_iterator<boost::detail::parallel::global_descriptor<long
> unsigned int>::generator, boost::counting_iterator<long unsigned int,
> boost::use_default, boost::use_default>, boost::use_default,
> boost::use_default>, Value = boost::detail::parallel::global_descriptor<long
> unsigned int>, CategoryOrTraversal = boost::random_access_traversal_tag,
> Reference = boost::detail::parallel::global_descriptor<long unsigned int>,
> Difference = long int]()]’
> dij.cpp:74: error: no match for ‘operator[]’ in
> ‘d[((boost::iterator_facade<boost::transform_iterator<boost::detail::parallel::global_descriptor<long
> unsigned int>::generator, boost::counting_iterator<long unsigned int,
> boost::use_default, boost::use_default>, boost::use_default,
> boost::use_default>, boost::detail::parallel::global_descriptor<long
> unsigned int>, boost::random_access_traversal_tag,
> boost::detail::parallel::global_descriptor<long unsigned int>, long int>*)(&
> vi))->boost::iterator_facade<I, V, TC, R, D>::operator* [with Derived =
> boost::transform_iterator<boost::detail::parallel::global_descriptor<long
> unsigned int>::generator, boost::counting_iterator<long unsigned int,
> boost::use_default, boost::use_default>, boost::use_default,
> boost::use_default>, Value = boost::detail::parallel::global_descriptor<long
> unsigned int>, CategoryOrTraversal = boost::random_access_traversal_tag,
> Reference = boost::detail::parallel::global_descriptor<long unsigned int>,
> Difference = long int]()]’
> /usr/include/c++/4.4/bits/stl_vector.h:610: note: candidates are: typename
> std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type::reference std::vector<_Tp,
> _Alloc>::operator[](size_t) [with _Tp = int, _Alloc = std::allocator<int>]
> /usr/include/c++/4.4/bits/stl_vector.h:625: note:                 typename
> std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type::const_reference
> std::vector<_Tp, _Alloc>::operator[](size_t) const [with _Tp = int, _Alloc =
> std::allocator<int>]
> dij.cpp:75: error: no match for ‘operator[]’ in
> ‘name[((boost::iterator_facade<boost::transform_iterator<boost::detail::parallel::global_descriptor<long
> unsigned int>::generator, boost::counting_iterator<long unsigned int,
> boost::use_default, boost::use_default>, boost::use_default,
> boost::use_default>, boost::detail::parallel::global_descriptor<long
> unsigned int>, boost::random_access_traversal_tag,
> boost::detail::parallel::global_descriptor<long unsigned int>, long int>*)(&
> vi))->boost::iterator_facade<I, V, TC, R, D>::operator* [with Derived =
> boost::transform_iterator<boost::detail::parallel::global_descriptor<long
> unsigned int>::generator, boost::counting_iterator<long unsigned int,
> boost::use_default, boost::use_default>, boost::use_default,
> boost::use_default>, Value = boost::detail::parallel::global_descriptor<long
> unsigned int>, CategoryOrTraversal = boost::random_access_traversal_tag,
> Reference = boost::detail::parallel::global_descriptor<long unsigned int>,
> Difference = long int]()]’
> dij.cpp:75: error: no match for ‘operator[]’ in
> ‘p[((boost::iterator_facade<boost::transform_iterator<boost::detail::parallel::global_descriptor<long
> unsigned int>::generator, boost::counting_iterator<long unsigned int,
> boost::use_default, boost::use_default>, boost::use_default,
> boost::use_default>, boost::detail::parallel::global_descriptor<long
> unsigned int>, boost::random_access_traversal_tag,
> boost::detail::parallel::global_descriptor<long unsigned int>, long int>*)(&
> vi))->boost::iterator_facade<I, V, TC, R, D>::operator* [with Derived =
> boost::transform_iterator<boost::detail::parallel::global_descriptor<long
> unsigned int>::generator, boost::counting_iterator<long unsigned int,
> boost::use_default, boost::use_default>, boost::use_default,
> boost::use_default>, Value = boost::detail::parallel::global_descriptor<long
> unsigned int>, CategoryOrTraversal = boost::random_access_traversal_tag,
> Reference = boost::detail::parallel::global_descriptor<long unsigned int>,
> Difference = long int]()]’
> /usr/include/c++/4.4/bits/stl_vector.h:610: note: candidates are: typename
> std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type::reference std::vector<_Tp,
> _Alloc>::operator[](size_t) [with _Tp =
> boost::detail::parallel::global_descriptor<long unsigned int>, _Alloc =
> std::allocator<boost::detail::parallel::global_descriptor<long unsigned int>
> >]
> /usr/include/c++/4.4/bits/stl_vector.h:625: note:                 typename
> std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type::const_reference
> std::vector<_Tp, _Alloc>::operator[](size_t) const [with _Tp =
> boost::detail::parallel::global_descriptor<long unsigned int>, _Alloc =
> std::allocator<boost::detail::parallel::global_descriptor<long unsigned int>
> >]
>
> The boost version I'm using is 1.40.0 in a Ubuntu Machine.
>
> If anyone could help me I would be grateful :)
>
> Thanks,
> Bruno Santos
>