Boost logo

Boost :

Subject: Re: [boost] Is the bellman_ford_shortest_paths function missing an overload with the root vertex?
From: Geoff Hilton (geoff.hilton_at_[hidden])
Date: 2008-11-28 14:45:05


Geoff Hilton wrote:
> Geoff Hilton wrote:
>> Quick question, was the fact that there is no
>> bellman_ford_shortest_paths overload in the BGL that allows for the
>> specification of the root vertex intentional? I'm using MSVC9 and
>> tried using the named parameters overload but it won't compile. Ditto
>> for dijkstra_shortest_paths and dag_shortest_paths actually.
>>
>> Here's what I have that won't compile with (twice) the error message:
>> error C2248: 'Weight<long long>::Weight': cannot access private member
>> declared in class 'Weight<long long>' c:\program
>> files\boost\boost_1_37_0\boost\graph\bellman_ford_shortest_paths.hpp
>> 155
>>
>>
>> class ShortestPathBellmanFordForward: public ShortestPathFunction
>> {
>> public:
>> virtual ~ShortestPathBellmanFordForward(){}
>> virtual AlgoResult operator()(
>> const vertex_descriptor startingVertex,
>> const WeightComparer<long long>& comparer,
>> Graph& graph) const {
>> const size_t numVertices = boost::num_vertices(graph);
>> AlgoResult retval;
>> retval.first = PredecessorMap(numVertices);
>> retval.second = DistanceMap(numVertices);
>> vertex_index_prop_t vindex = get(boost::vertex_index, graph);
>> boost::bellman_ford_shortest_paths(graph, numVertices,
>> weight_map(boost::get(&EdgeProp::weights, graph)).
>> predecessor_map(boost::make_iterator_property_map(
>> retval.first.begin(), vindex)).
>> distance_map(boost::make_iterator_property_map(
>> retval.second.begin(), vindex)).
>> root_vertex(startingVertex).
>> distance_combine(WeightCombiner<long long>()).
>> distance_compare(comparer));
>> return retval;
>> }
>> };
>>
>> Thanks,
>> Geoff
>
> Hmm, so I realized that the above error was because my Weight datatype
> happens to have a private constructor which takes a
> template-type-specified value in the constructor for default
> initialization (it's really only used (in my code) by my named
> constructors CreateInfinity() and CreateZero() though).
> When I comment out the word "private:" which hides the constructor in
> question, everything compiles fine, but when I comment out the
> constructor entirely (and adjust the named constructors accordingly) the
> compiler goes nuts with 30 errors (all of which are attributed by the
> compiler to bellman_ford_shortest_paths.hpp), the first of which is:
>
> error C2440: '<function-style-cast>': cannot convert from 'int' to
> 'weight_type' c:\program
> files\boost\boost_1_37_0\boost\graph\bellman_ford_shortest_paths.hpp 155
>
> "cannot convert from 'int' to 'weight_type'"... well duh. But notice
> line 155 as mentioned above... is this really desirable? That line does
> indeed force the requirement that the weight type have a constructor
> which takes a POD as a parameter.
>
> I'd like to propose replacing the above mentioned behaviour with that
> which is similar to dijkstra or dag; namely that a weight of value
> infinity and zero be supplied to the algorithm by named/unnamed parameter.
>
> Thanks,
> Geoff

Oh, although the above means that I don't need to worry about the
unnamed function variant for now, I'd just like to reiterate that I
think it would be a good idea that root_vertex be added as a
(default-able) parameter.
Thanks,
Geoff


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk