successfull compilation depends on header order in Graph

[karnigen <karnigen@…>]

From time to time program cannot be compiled due to incorrect order of headers. It always takes some time to resolve correct order of headers. I found also very simple example, see attachment. Example does not compile until transitive_closure.hpp is moved up.

compiled on Linux 64:
g++ -std=c++0x -Iboost/include -frounding-math -O2 x.cpp -o x.exe

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/transitive_closure.hpp> must be on top

int main(int, char *[]) {

using namespace boost;
typedef adjacency_list < listS, vecS, directedS > G;
G g;
add_edge(0,1, g);
adjacency_list <> tc;
transitive_closure(g, tc);
print_graph(tc);
return 0;

}

[Jeremiah Willcock]

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

[Albert Gil <albert.gil@…>]

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

[Albert Gil <albert.gil@…>]

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@…]

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@…]

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@…]

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

[edaskel@…]

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]

@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?

[edaskel@…]

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