[Boost-users] [BGL] Distributed Dijkstra vertex_iterator

Subject: [Boost-users] [BGL] Distributed Dijkstra vertex_iterator
From: Bruno Santos (bmfs_at_[hidden])
Date: 2010-06-02 14:53:32

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