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: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-02-04 14:14:55

On Thu, 4 Feb 2010, Geoff Hilton wrote:

> 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!

Are you providing a distance map?  It appears that there isn't one 
provided to dag_shortest_paths.

>>> 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.

Are there other equality comparisons other than the one to infinity? 
Most of the inequality comparisons should be safe as they only assume 
things like that x + y >= x whenever x >= 0 and y >= 0, which I believe is 
always true (though x + y > x when y > 0 is not always true).

>>> #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.

There is no distance map being provided, and the algorithm requires one to 
be explicitly provided.

> 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).

Why is it an issue?  The reason that bundled properties are structs is 
that you may want to have several properties in your bundle.  I do think 
the thing you're trying to do (passing float as the property) works most 
of the time, though; use get(edge_bundle, g) to get that map.

> 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.

How do you know that the property the user wants to define is the weight? 
What about the color, edge capacity, ...?  Old-style properties are good 
for that.

-- Jeremiah Willcock