Re: [Boost-users] [BGL] predecessor map from a view on a multi_array

Subject: Re: [Boost-users] [BGL] predecessor map from a view on a multi_array
From: Geoff Hilton (geoff.hilton_at_[hidden])
Date: 2010-02-04 13:37:26

On 03/02/2010 1:59 PM, Jeremiah Willcock wrote:
> On Mon, 1 Feb 2010, Geoff Hilton wrote:
>
>> Hi, I'm currently using MSVC9 and the code listed below doesn't
>> compile, instead producing the following errors and warnings:
>>
>> Warning 1 warning C4100: 'x' : unreferenced formal parameter
>> c:\program files\boost\boost_1_41_0\boost\concept\detail\msvc.hpp 20 test
>> Warning 2 warning C4100: 'id' : unreferenced formal parameter
>> c:\program files\boost\boost_1_41_0\boost\graph\dag_shortest_paths.hpp
>> 86 test
>> Error 3 error C2440: '<function-style-cast>' : cannot convert from
>> 'int' to 'D' c:\program files\microsoft visual studio
>> 9.0\vc\include\limits 109 test
>
> Do you have an instantiation stack for this? I can't see how it relates
> to BGL otherwise.
>
Hi and thanks for your much appreciated response. I should have simply 
sent you the build log as attached this time around, sorry!

>> I know MSVC has issues with named parameters among other things, but I
>> haven't been able to get it to compile with the non-named-parameters
>> overload either, in this instance.
>> What am I misusing and how am I misusing it? Also, I get the
>> impression that the default combiner/comparer may be unsafe for
>> floating-point comparisons and addition (with respect to
>> over/underflow and comparing floating point values, I seem to recall
>> it being a good idea never to compare with direct equalities, eg. x ==
>> infinity because of rounding issues).
>
> I know there have been issues with things like load(store(a + b)) != a +
> b before (due to rounding issues). I believe comparison to infinity is
> safe, though, since that is a special value; checking online seems to
> suggest that there is only one bit pattern for each infinity.
> std::plus<double> should work since the CPU should handle infinity as a
> special case. Even if the comparisons in closed_plus always return
> false, the code should still work for float and double.
>
>> Might it be a good idea to further specialize appropriate areas of the
>> algorithm code to account for this, or am I
>> over-generalizing(specializing?)? How about a specialized
>> closed_plus<> in relax.hpp which makes the comparisons more safely for
>> floats and doubles (since both parameters "a" and "b" of closed_plus
>> must be of type T anyway)?
>
> What comparisons need to be safer? Just comparison to infinity?

All of them I suppose including addition/subtraction/etc, though I'm no 
numerical analyst, but I imagine that comparisons need to be checked 
against a minimal margin of error to ensure they are relatively "equal" 
as opposed to(or in addition to) *actually* "less than" or "greater 
than". After some reading I think this may require the specification of 
a level of precision for accuracy, but then we get into floating point 
computation to which there are whole libraries devoted (eg. MPFR[1] is 
the only one I've found, but C++ wrappers are all very outdated or wrap 
versions other than the most recent). Ideally, it would be nice if there 
were a maintained boost wrapper for such a library, but that may just be 
a pipe dream unless someone volunteers.

>
>> #include <boost/graph/adjacency_list.hpp>
>> #include <boost/graph/dag_shortest_paths.hpp>
>> #include <boost/multi_array.hpp>
>>
>> namespace geoff {
>> typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS
>> ,boost::no_property, float> Graph;
>> typedef
>> boost::multi_array<boost::graph_traits<Graph>::vertex_descriptor, 2U>
>> PredecessorsMatrix;
>>
>> typedef PredecessorsMatrix::array_view<1>::type PredecessorMap;
>> } //namespace geoff
>>
>> int main(int /*argc*/, char* /*argv*/[])
>> {
>> const std::size_t num_agents = 3;
>> geoff::Graph graph;
>> geoff::PredecessorsMatrix
>> per_agent_matrix(boost::extents[num_agents][boost::num_vertices(graph)]);
>> geoff::PredecessorsMatrix::index_gen indices;
>> std::size_t agent_index = 0U;
>> geoff::PredecessorMap agent_x_predecessors =
>> per_agent_matrix[indices[agent_index][boost::multi_array_types::index_range()]];
>>
>> boost::dag_shortest_paths(graph, 0,
>> boost::predecessor_map(agent_x_predecessors));
>> }
>
> Is this the erroring code? What errors do you get from it?
>
> -- Jeremiah Willcock

Yes the above code causes the mentioned warnings and errors.

I've since gotten it to compile by working with it as a bundled property 
but because of the nature of bundled properties I had to use a struct 
wrapper such that the resulting types look as follows:

struct EdgeProperty {
   float value;
};
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS
,boost::no_property, EdgeProperty> Graph;
typedef boost::property_map<Graph, float EdgeProperty::*>::type WeightMap;

WeightMap w_map = boost::get(&toptlogic::EdgeProperty::value, graph);

dag_shortest_paths(graph, 0, predecessor_map( 
make_iterator_property_map(agent_x_predecessors.begin(), v_index) )
.weight_map(w_map)
);

What I want is the equivalent of an interior property but it doesn't 
need to be a bundled property because it's just one float per edge. I'd 
rather not use a syntax which is considered obsolete (eg. 
property<edge_weight_t, float>), but I also don't need it to be bundled. 
I get the impression that this simple test case seems to have slipped 
through the cracks as suggested by the fact that every single example 
involving a BGL graph (most likely without exception) either uses 
bundled properties or the old property<...> syntax (I think keeping the 
documentation up to date might have revealed this small oversight 
sooner, but I do understand what a task that can be).

Because the bundled property syntax allows us to replace the entire 
property<...> chaining mechanism with one custom struct, simple cases 
like the one at hand might reasonably be placed on the same level as 
bundled properties in the sense that a float is identical to a struct 
MyFloat{float value; } but with just one value. As such, a WeightMap 
might justifiably be equivalent to something along the lines of 
property_map<Graph, float*>::type, but since we can't know to what 
variable or area in memory it maps to (provided it being interior is 
implied), I think it might be reasonable for something akin to 
get(edge_weight, graph) to "magically" work, automatically mapping to 
the appropriate type and more-or-less "dropping support" for other 
property types (eg. edge_weight2_t) by allowing only edge_weight (for 
example) to work in the case where the property is an arithmetic type 
(ie. where is_arithmetic<T> inherits from true_type) and not a bundled 
property (in which case use the bundled property mechanism) or a 
property<...> (in which case use the old mechanism). This of course 
would apply to vertex properties and graph properties as well.

In summary, this means that:
1) bundled properties could continue to work as they currently do,
2) the original property<...> syntax could be preserved,
3) and (upon reflection) instead of reusing edge_weight for edges (for 
example) three new types could be used specifically for this magic 
mapping of interior arithmetic types, such as edge_property_t, 
vertex_property_t, graph_property_t.

That way, the following code could compile and run:

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS
,boost::no_property, float> Graph;
//typedef boost::property_map<Graph, float*>::type WeightMap;

//WeightMap w_map = boost::get(edge_property, graph);

dag_shortest_paths(graph, 0, predecessor_map( 
make_iterator_property_map(agent_x_predecessors.begin(), v_index))
);

//(as opposed to...)

/*excluding weight_map should compile and use a default weight map when 
the edge property is an arithmetic type. If it should already compile 
successfully without specifying a weight map then it must be an issue 
with MSVC because it won't compile without it on my system.*/
dag_shortest_paths(graph, 0, predecessor_map( 
make_iterator_property_map(agent_x_predecessors.begin(), v_index) )
.weight_map(w_map));

Thanks again,
Geoff

[1] http://www.mpfr.org/