[Boost-users] Problem calling bellman_ford_shortest_paths

Subject: [Boost-users] Problem calling bellman_ford_shortest_paths
From: Tim Keitt (tkeitt_at_[hidden])
Date: 2008-10-27 17:06:10

I'm prototyping some code that exposes an edge_list iterator interface
to a database cursor. I've defined a forward_iterator using
iterator_facade and can use that to create an edge_list graph. I'm
running into a problem however calling bellman_ford_shortest_paths on
the graph. I get

boost_bellman_ford.cpp:18: error: no matching function for call to
'bellman_ford_shortest_paths(Graph&, position_t&, edge_weight_map,
long long int*, double*)'

The code leading up to that looks like:

        position_t N = getNumVertices();
        edge_iterator iter;
        DEBUG_MESSAGE("Contructed iterator");
        Graph g(iter, iter.end());
        DEBUG_MESSAGE("Constructed edge list graph");
        std::vector<double> distance(N, std::numeric_limits<double>::max());
        distance[0] = 0.0;
        std::vector<position_t> parent(N);
        for ( position_t i = 0; i < N; ++i ) parent[i] = i;
         boost::bellman_ford_shortest_paths(g, N, edge_weight_map(),
&parent[0], &distance[0]);

The edge iterator is linked to the database cursor on construction.

The problem I am guessing is in how I define the edge_weight_map. It looks like

struct edge_weight_map
{
        typedef cost_t value_type;
        typedef cost_t * reference;
        typedef edge_t key_type;
        typedef boost::readable_property_map_tag category;
};

boost::property_traits<edge_weight_map>::value_type
get(edge_weight_map map,
boost::property_traits<edge_weight_map>::key_type key) { return
key.cost; }

It makes no sense for me to repeatedly query the database for the edge
weight, so I attach it as a third field in the edge_descriptor. The
get function merely returns the third component of the edge struct.
I'm sort of assuming the way I am defining the edge_weight_map is the
problem. Any insights?

Also, I noticed the simply constructing the edge_list graph traverses
the entire iterator range. Is there some copying going on? Can I
override this behavior?

THK

-- 
Timothy H. Keitt
http://www.keittlab.org/