Modify

Ticket #8791 (closed Bugs: fixed)

Opened 2 years ago

Last modified 3 months ago

successfull compilation depends on header order in Graph

Reported by: karnigen <karnigen@…> Owned by: jewillco
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

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

Change History

Changed 2 years ago by karnigen <karnigen@…>

comment:1 Changed 2 years ago by jewillco

  • Status changed from new to closed
  • Resolution set to fixed

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

comment:2 follow-up: ↓ 3 Changed 11 months 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 11 months 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 3 months 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 3 months 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 follow-up: ↓ 7 Changed 3 months ago by edaskel@…

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

comment:7 in reply to: ↑ 6 Changed 3 months 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 3 months 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 3 months ago by Maël Valais <mael.valais@…>

comment:9 Changed 3 months 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

View

Add a comment

Modify Ticket

Change Properties
<Author field>
Action
as closed
The resolution will be deleted. Next status will be 'reopened'
Author


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

 
Note: See TracTickets for help on using tickets.