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

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

namespace geoff { typedef boost::adjacency_list Graph; typedef boost::multi_array 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 Graph; typedef boost::property_map::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), 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::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