Boost C++ Libraries: Ticket #8791: successfull compilation depends on header order in Graph

attachment set

Sun, 07 Jul 2013 11:42:45 GMT

attachment → x.cpp

status changed; resolution set

Jeremiah Willcock — Sun, 07 Jul 2013 16:50:25 GMT

status new → closed
resolution → fixed

(In [84976]) Changed to use adjacency_list for temporary graph, avoiding ADL issues with vector_as_graph; fixes #8791

Wed, 08 Oct 2014 11:39:52 GMT

Hi,

I've a very similar problem with boost/graph/dijkstra_shortest_paths.hpp, it should be included before boost/graph/strong_components.hpp... could it be related also to this ADL problem?

Also I've a very similar problem with boost/graph/edmonds_karp_max_flow.hpp, but I can't make it compile at all (changing headers order) on 1.55, it works on 1.50.

The original code is not mine, I'm not an expert on boost.graph, but the simpler test case I've been able to create from the original to replicate the error for boost/graph/edmonds_karp_max_flow.hpp is:

#include <boost/graph/edmonds_karp_max_flow.hpp>
#include <boost/graph/adjacency_list.hpp>
typedef boost::adjacency_list_traits < boost::listS, boost::vecS, boost::bidirectionalS > Traits;
struct NodeMaxFlowProperties {
    boost::default_color_type color;
    double distance;
    Traits::edge_descriptor predecessor;
    NodeMaxFlowProperties() : color(boost::white_color), predecessor() {}
};
struct EdgeMaxFlowProperties {
    double capacity;
    double residual_capacity;
    Traits::edge_descriptor reverse_edge;
    EdgeMaxFlowProperties() : capacity(0), residual_capacity(0), reverse_edge() {}
};
typedef boost::adjacency_list<  boost::listS,
                                boost::vecS,
                                boost::bidirectionalS,
                                NodeMaxFlowProperties,
                                EdgeMaxFlowProperties
                                > Graph;
typedef boost::graph_traits<Graph>::vertex_descriptor Node;
int main ()
{
    Graph graph;
    Node source;
    Node sink;
    boost::edmonds_karp_max_flow(graph, source, sink ,  boost::capacity_map(    get(&EdgeMaxFlowProperties::capacity,                           graph)).
                                                        residual_capacity_map(  get(&EdgeMaxFlowProperties::residual_capacity,                  graph)).
                                                        reverse_edge_map(       get(&EdgeMaxFlowProperties::reverse_edge,                       graph)).
                                                        color_map(              get(&NodeMaxFlowProperties::color,                              graph)));
}

The GCC error looks like:

/usr/local/include/boost/graph/detail/adjacency_list.hpp: In instantiation of 'struct boost::detail::adj_list_any_edge_pmap::bind_<boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>, EdgeMaxFlowProperties, boost::edge_capacity_t>':
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2683:12:   required from 'struct boost::detail::adj_list_choose_edge_pmap<boost::edge_capacity_t, boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>, EdgeMaxFlowProperties>'
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2688:14:   required from 'struct boost::detail::adj_list_edge_property_selector::bind_<boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>, EdgeMaxFlowProperties, boost::edge_capacity_t>'
/usr/local/include/boost/graph/properties.hpp:208:12:   required from 'struct boost::detail::edge_property_map<boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>, boost::edge_capacity_t>'
/usr/local/include/boost/graph/properties.hpp:228:10:   required from 'struct boost::property_map<boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>, boost::edge_capacity_t, void>'
/usr/local/include/boost/mpl/eval_if.hpp:38:31:   recursively required from 'struct boost::mpl::eval_if<mpl_::bool_<true>, boost::detail::const_type_as_type<boost::property_map<boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>, boost::edge_capacity_t, void> >, boost::property_map<boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>, boost::edge_capacity_t, void> >'
/usr/local/include/boost/mpl/eval_if.hpp:38:31:   required from 'struct boost::mpl::eval_if<boost::is_same<boost::param_not_found, boost::param_not_found>, boost::mpl::eval_if<mpl_::bool_<true>, boost::detail::const_type_as_type<boost::property_map<boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>, boost::edge_capacity_t, void> >, boost::property_map<boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>, boost::edge_capacity_t, void> >, boost::mpl::identity<boost::param_not_found> >'
/usr/local/include/boost/graph/named_function_params.hpp:269:12:   required from 'struct boost::detail::choose_impl_result<mpl_::bool_<true>, boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>, boost::param_not_found, boost::edge_capacity_t>'
/usr/local/include/boost/graph/named_function_params.hpp:326:156:   required from 'struct boost::detail::edge_capacity_value<boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>, boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>, boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>*, boost::default_color_type, boost::default_color_type&, boost::default_color_type NodeMaxFlowProperties::*>, boost::vertex_color_t, boost::bgl_named_params<boost::adj_list_edge_property_map<boost::bidirectional_tag, boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>, boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>&, unsigned int, EdgeMaxFlowProperties, boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int> EdgeMaxFlowProperties::*>, boost::edge_reverse_t, boost::bgl_named_params<boost::adj_list_edge_property_map<boost::bidirectional_tag, double, double&, unsigned int, EdgeMaxFlowProperties, double EdgeMaxFlowProperties::*>, boost::edge_residual_capacity_t, boost::bgl_named_params<boost::adj_list_edge_property_map<boost::bidirectional_tag, double, double&, unsigned int, EdgeMaxFlowProperties, double EdgeMaxFlowProperties::*>, boost::edge_capacity_t, boost::no_property> > > >'
/usr/local/include/boost/graph/edmonds_karp_max_flow.hpp:223:3:   required by substitution of 'template<class Graph, class P, class T, class R> typename boost::detail::edge_capacity_value::type boost::edmonds_karp_max_flow(Graph&, typename boost::graph_traits<IncidenceGraph>::vertex_descriptor, typename boost::graph_traits<IncidenceGraph>::vertex_descriptor, const boost::bgl_named_params<T, Tag, Base>&) [with Graph = boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>; P = boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>, boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>*, boost::default_color_type, boost::default_color_type&, boost::default_color_type NodeMaxFlowProperties::*>; T = boost::vertex_color_t; R = boost::bgl_named_params<boost::adj_list_edge_property_map<boost::bidirectional_tag, boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>, boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>&, unsigned int, EdgeMaxFlowProperties, boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int> EdgeMaxFlowProperties::*>, boost::edge_reverse_t, boost::bgl_named_params<boost::adj_list_edge_property_map<boost::bidirectional_tag, double, double&, unsigned int, EdgeMaxFlowProperties, double EdgeMaxFlowProperties::*>, boost::edge_residual_capacity_t, boost::bgl_named_params<boost::adj_list_edge_property_map<boost::bidirectional_tag, double, double&, unsigned int, EdgeMaxFlowProperties, double EdgeMaxFlowProperties::*>, boost::edge_capacity_t, boost::no_property> > >]'
sample.cpp:39:152:   required from here
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2651:29: error: forming reference to void
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2652:35: error: forming reference to void
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2656:61: error: forming reference to void
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2659:68: error: forming reference to void
sample.cpp: In function 'int main()':
sample.cpp:39:152: error: no matching function for call to 'edmonds_karp_max_flow(Graph&, Node&, Node&, boost::bgl_named_params<boost::vec_adj_list_vertex_property_map<boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>, boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, NodeMaxFlowProperties, EdgeMaxFlowProperties>*, boost::default_color_type, boost::default_color_type&, boost::default_color_type NodeMaxFlowProperties::*>, boost::vertex_color_t, boost::bgl_named_params<boost::adj_list_edge_property_map<boost::bidirectional_tag, boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>, boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int>&, unsigned int, EdgeMaxFlowProperties, boost::detail::edge_desc_impl<boost::bidirectional_tag, unsigned int> EdgeMaxFlowProperties::*>, boost::edge_reverse_t, boost::bgl_named_params<boost::adj_list_edge_property_map<boost::bidirectional_tag, double, double&, unsigned int, EdgeMaxFlowProperties, double EdgeMaxFlowProperties::*>, boost::edge_residual_capacity_t, boost::bgl_named_params<boost::adj_list_edge_property_map<boost::bidirectional_tag, double, double&, unsigned int, EdgeMaxFlowProperties, double EdgeMaxFlowProperties::*>, boost::edge_capacity_t, boost::no_property> > > >)'
sample.cpp:39:152: note: candidates are:
In file included from tools/examples/tool_config_example/src/tool_config_example.cpp:17:0:
/usr/local/include/boost/graph/edmonds_karp_max_flow.hpp:79:3: note: template<class Graph, class CapacityEdgeMap, class ResidualCapacityEdgeMap, class ReverseEdgeMap, class ColorMap, class PredEdgeMap> typename boost::property_traits<CapacityEdgeMap>::value_type boost::edmonds_karp_max_flow(Graph&, typename boost::graph_traits<VertexListGraph>::vertex_descriptor, typename boost::graph_traits<VertexListGraph>::vertex_descriptor, CapacityEdgeMap, ResidualCapacityEdgeMap, ReverseEdgeMap, ColorMap, PredEdgeMap)
/usr/local/include/boost/graph/edmonds_karp_max_flow.hpp:79:3: note:   template argument deduction/substitution failed:
sample.cpp:39:152: note:   candidate expects 8 arguments, 4 provided
In file included from tools/examples/tool_config_example/src/tool_config_example.cpp:17:0:
/usr/local/include/boost/graph/edmonds_karp_max_flow.hpp:223:3: note: template<class Graph, class P, class T, class R> typename boost::detail::edge_capacity_value::type boost::edmonds_karp_max_flow(Graph&, typename boost::graph_traits<IncidenceGraph>::vertex_descriptor, typename boost::graph_traits<IncidenceGraph>::vertex_descriptor, const boost::bgl_named_params<T, Tag, Base>&)
/usr/local/include/boost/graph/edmonds_karp_max_flow.hpp:223:3: note:   substitution of deduced template arguments resulted in errors seen above
/usr/local/include/boost/graph/edmonds_karp_max_flow.hpp:238:3: note: template<class Graph> typename boost::property_traits<typename boost::property_map<Graph, boost::edge_capacity_t>::const_type>::value_type boost::edmonds_karp_max_flow(Graph&, typename boost::graph_traits<Graph>::vertex_descriptor, typename boost::graph_traits<Graph>::vertex_descriptor)
/usr/local/include/boost/graph/edmonds_karp_max_flow.hpp:238:3: note:   template argument deduction/substitution failed:
sample.cpp:39:152: note:   candidate expects 3 arguments, 4 provided

Do you think that it's the same problem, or should I report it to a different bug/ticket?

Thanks!

Albert

Mon, 13 Oct 2014 07:58:51 GMT

Replying to Albert Gil <albert.gil@…>:

I've a very similar problem with boost/graph/dijkstra_shortest_paths.hpp, it should be included before boost/graph/strong_components.hpp... could it be related also to this ADL problem? Also I've a very similar problem with boost/graph/edmonds_karp_max_flow.hpp, but I can't make it compile at all (changing headers order) on 1.55, it works on 1.50.

Sorry, I've just enabled -std=c++11 in gcc and it just worked!

mael.valais@… — Wed, 03 Jun 2015 14:39:42 GMT

I just tested your code with:

g++-4.8.4 with -std=c++11 and boost 1.50.0 -> OK
g++-4.8.4 with -std=c++11 and boost 1.55.0 -> NOK
g++-4.8.4 with -std=c++11 and boost 1.58.0 -> NOK

What happend, did the "max-flow capacity property" break from 1.50.0 to 1.55.0? (see in boost/graph/named_function_params.hpp:326 for boost 1.58.0)

albert.gil@… — Wed, 03 Jun 2015 15:25:04 GMT

Sorry, you are right: the -std=c++11 didn't solved the problem at all! It was a false-positive... I missed to report it here.

My final workaround (after trying my best) was to not calling the main/public edmonds_karp_max_flow function:

float64 flow = boost::edmonds_karp_max_flow( graph,
                                             source,
                                             sink,
                                             boost::capacity_map    ( get(&Graph::EdgePropertiesType::capacity         ,graph)).
                                               residual_capacity_map( get(&Graph::EdgePropertiesType::residual_capacity,graph)).
                                               reverse_edge_map     ( get(&Graph::EdgePropertiesType::reverse_edge     ,graph)).
                                               color_map            ( get(&Graph::NodePropertiesType::color            ,graph)));

But calling the "internal" funtion with more parameters:

float64 flow = boost::edmonds_karp_max_flow( graph,
	                                     source,
	                                     sink,
	                                     get(&Graph::EdgePropertiesType::capacity,          graph),
	                                     get(&Graph::EdgePropertiesType::residual_capacity, graph),
	                                     get(&Graph::EdgePropertiesType::reverse_edge,      graph),
	                                     get(&Graph::NodePropertiesType::color,             graph),
	                                     get(&Graph::NodePropertiesType::predecessor,       graph));

Not sure why, but it worked...?

Albert

edaskel@… — Wed, 03 Jun 2015 23:06:23 GMT

Appears to be svn commit 77549, but I'm not sure why.

edaskel@… — Thu, 04 Jun 2015 04:44:18 GMT

Replying to edaskel@…:

Appears to be svn commit 77549, but I'm not sure why.

I believe it is because named_function_params.hpp, line 326, has the arguments to get_param_type in reverse order. The Tag should be provided first.

anonymous — Thu, 04 Jun 2015 07:59:30 GMT

@albert Thank you for your answer. -std=c++11 is no help then :(

@edaskel You found it! Thank you so much!!! I just tried to invert them, and it worked.

Before in boost/graph/named_function_params.hpp:326:

typedef typename detail::choose_impl_result<boost::mpl::true_, Graph, typename get_param_type<Params, edge_capacity_t>::type, edge_capacity_t>::type CapacityEdgeMap;

After in boost/graph/named_function_params.hpp:326:

typedef typename detail::choose_impl_result<boost::mpl::true_, Graph, typename get_param_type<edge_capacity_t, Params>::type, edge_capacity_t>::type CapacityEdgeMap;

Shouldn't we submit that fix to the trunk?

attachment set

Thu, 04 Jun 2015 12:30:34 GMT

attachment → 0001-trac-8791-reversed-order-of-get_param_type-parameter.patch

edaskel@… — Thu, 04 Jun 2015 14:37:28 GMT

Maël we should also make a new bug, as this one was marked "fixed" 2 years ago and actually is not related to your issue after all :) -Jeff