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@eksperimental.net> 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