Modify

Opened 4 years ago

Closed 4 years ago

Last modified 2 years ago

#8791 closed Bugs (fixed)

successfull compilation depends on header order in Graph

Reported by: karnigen <karnigen@…> Owned by: Jeremiah Willcock
Milestone: To Be Determined Component: graph
Version: Boost 1.54.0 Severity: Cosmetic
Keywords: header compilation graph Cc:

Description

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;

}

Attachments (2)

x.cpp (478 bytes) - added by karnigen <karnigen@…> 4 years ago.
0001-trac-8791-reversed-order-of-get_param_type-parameter.patch (1.1 KB) - added by Maël Valais <mael.valais@…> 2 years ago.

Download all attachments as: .zip

Change History (11)

Changed 4 years ago by karnigen <karnigen@…>

Attachment: x.cpp added

comment:1 Changed 4 years ago by Jeremiah Willcock

Resolution: fixed
Status: newclosed

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

comment:2 Changed 3 years ago by 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

comment:3 in reply to:  2 Changed 3 years ago by 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!

comment:4 Changed 2 years ago by 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)

comment:5 Changed 2 years ago by 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

comment:6 Changed 2 years ago by edaskel@…

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

comment:7 in reply to:  6 Changed 2 years ago by 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.

comment:8 Changed 2 years ago by 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?

Changed 2 years ago by Maël Valais <mael.valais@…>

comment:9 Changed 2 years ago by 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

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain Jeremiah Willcock.
The resolution will be deleted.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.