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/