[Graph] LEDA adapter - concept check VertexListGraph fails

Hi everyone, when running the tests for Graph, the first concept check in leda_graph_cc.cpp fails: gcc.compile.c++ ../../../bin.v2/libs/graph/test/leda_graph_cc.test/gcc-4.6.1/debug/leda_graph_cc.o In file included from leda_graph_cc.cpp:9:0: ../../../boost/graph/graph_concepts.hpp: In destructor 'boost::concepts::VertexListGraph<G>::~VertexListGraph() [with G = leda::GRAPH<int, int>]': ../../../boost/graph/graph_concepts.hpp:168:1: instantiated from 'static void boost::concepts::requirement<boost::concepts::failed************ Model::************>::failed() [with Model = boost::concepts::VertexListGraphConcept<leda::GRAPH<int, int> >]' leda_graph_cc.cpp:21:5: instantiated from here ../../../boost/graph/graph_concepts.hpp:189:9: error: no matching function for call to 'vertices(leda::GRAPH<int, int>&)' ../../../boost/graph/graph_concepts.hpp:189:9: note: candidate is: ../../../boost/graph/graph_concepts.hpp:45:48: note: template<class T> typename T::ThereReallyIsNoMemberByThisNameInT boost::vertices(const T&) (among some further errors, but I'd like to ask just about this one now) Apparently it cannot find a vertices() function: ../../../boost/graph/graph_concepts.hpp:189:9: error: no matching function for call to 'vertices(leda::GRAPH<int, int>&)' But there is one in leda_graph.hpp: template <class vtype, class etype> inline std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator, typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator > vertices(const leda::GRAPH<vtype,etype>& g) { typedef typename graph_traits< leda::GRAPH<vtype,etype>
::vertex_iterator Iter; return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) ); }
So, can someone enlighten me why it isn't found? Has it something to do with #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK // dwa 2003/7/11 -- This clearly shouldn't be necessary, but if // you want to use vector_as_graph, it is! I'm sure the graph // library leaves these out all over the place. Probably a // redesign involving specializing a template with a static // member function is in order :( using boost::vertices; #endif ? Best regards, Jens

On Sun, 18 Dec 2011, Jens Müller wrote:
Hi everyone,
when running the tests for Graph, the first concept check in leda_graph_cc.cpp fails:
gcc.compile.c++ ../../../bin.v2/libs/graph/test/leda_graph_cc.test/gcc-4.6.1/debug/leda_graph_cc.o In file included from leda_graph_cc.cpp:9:0: ../../../boost/graph/graph_concepts.hpp: In destructor 'boost::concepts::VertexListGraph<G>::~VertexListGraph() [with G = leda::GRAPH<int, int>]': ../../../boost/graph/graph_concepts.hpp:168:1: instantiated from 'static void boost::concepts::requirement<boost::concepts::failed************ Model::************>::failed() [with Model = boost::concepts::VertexListGraphConcept<leda::GRAPH<int, int> >]' leda_graph_cc.cpp:21:5: instantiated from here ../../../boost/graph/graph_concepts.hpp:189:9: error: no matching function for call to 'vertices(leda::GRAPH<int, int>&)' ../../../boost/graph/graph_concepts.hpp:189:9: note: candidate is: ../../../boost/graph/graph_concepts.hpp:45:48: note: template<class T> typename T::ThereReallyIsNoMemberByThisNameInT boost::vertices(const T&)
(among some further errors, but I'd like to ask just about this one now)
Apparently it cannot find a vertices() function:
../../../boost/graph/graph_concepts.hpp:189:9: error: no matching function for call to 'vertices(leda::GRAPH<int, int>&)'
But there is one in leda_graph.hpp:
template <class vtype, class etype> inline std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator, typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator > vertices(const leda::GRAPH<vtype,etype>& g) { typedef typename graph_traits< leda::GRAPH<vtype,etype>
::vertex_iterator Iter; return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) ); }
That function is in the boost namespace, so it won't be found when searching for an unqualified call to vertices() (which is what algorithms are supposed to use). You might need to do something like the ADL hack you mentioned (pulling those functions into the global namespace) to get the concept check to pass. -- Jeremiah Willcock

On 18.12.2011 22:59, Jeremiah Willcock wrote:
That function is in the boost namespace, so it won't be found when searching for an unqualified call to vertices() (which is what algorithms are supposed to use). You might need to do something like the ADL hack you mentioned (pulling those functions into the global namespace) to get the concept check to pass.
As far as I can tell, this _is_ used. boost/graph/graph_concepts.hpp contains the following: #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) \ && !BOOST_WORKAROUND(__GNUC__, <= 2) \ && !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) # define BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK #endif #ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK template <class T> typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&); #endif This line is mentioned in the error message, so BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK _is_ indeed defined. - Jens

On Sun, 18 Dec 2011, Jens Müller wrote:
On 18.12.2011 22:59, Jeremiah Willcock wrote:
That function is in the boost namespace, so it won't be found when searching for an unqualified call to vertices() (which is what algorithms are supposed to use). You might need to do something like the ADL hack you mentioned (pulling those functions into the global namespace) to get the concept check to pass.
As far as I can tell, this _is_ used.
boost/graph/graph_concepts.hpp contains the following:
#if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) \ && !BOOST_WORKAROUND(__GNUC__, <= 2) \ && !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) # define BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK #endif
#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK template <class T> typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&); #endif
This line is mentioned in the error message, so BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK _is_ indeed defined.
That's odd; I can see a need for a using declaration, but not for a strange function like that one. I think the LEDA adapter will require some kind of namespace import even with a conforming compiler. -- Jeremiah Willcock

On 18.12.2011 23:36, Jeremiah Willcock wrote:
#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK template <class T> typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&); #endif
This line is mentioned in the error message, so BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK _is_ indeed defined.
That's odd; I can see a need for a using declaration, but not for a strange function like that one.
If I remove it, all kinds of non-LEDA tests start to fail. Do you know who dwa is? He probably had something in mind when inventing this hack ... - Jens

On Mon, 19 Dec 2011, Jens Müller wrote:
On 18.12.2011 23:36, Jeremiah Willcock wrote:
#ifdef BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK template <class T> typename T::ThereReallyIsNoMemberByThisNameInT vertices(T const&); #endif
This line is mentioned in the error message, so BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK _is_ indeed defined.
That's odd; I can see a need for a using declaration, but not for a strange function like that one.
If I remove it, all kinds of non-LEDA tests start to fail.
Do you know who dwa is? He probably had something in mind when inventing this hack ...
Dave Abrahams; see svn commit 19070 for the full set of changes. -- Jeremiah Willcock

On 18.12.2011 23:36, Jeremiah Willcock wrote:
I think the LEDA adapter will require some kind of namespace import even with a conforming compiler.
This is the function that should be found: namespace boost { template <class vtype, class etype> inline std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator, typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator > vertices(const leda::GRAPH<vtype,etype>& g) { typedef typename graph_traits< leda::GRAPH<vtype,etype>
::vertex_iterator Iter; return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) ); } } // namespace boost
I now tried out something different. I wondered about this comment: "It is needed in order to allow us to write using boost::vertices as needed for ADL when using vector_as_graph below.", and my idea was "so that a function of that name is indeed defined" ... I switched the order of the imports in leda_graph_cc.cpp: #include <boost/graph/leda_graph.hpp> #include <boost/graph/graph_concepts.hpp> and indeed, this bug is gone (there is another one in the same concept check, but I will deal with it later). Should this really be order-dependent? If yes, should it be documented somewhere? - Jens

On Mon, 19 Dec 2011, Jens Müller wrote:
On 18.12.2011 23:36, Jeremiah Willcock wrote:
I think the LEDA adapter will require some kind of namespace import even with a conforming compiler.
This is the function that should be found:
namespace boost { template <class vtype, class etype> inline std::pair< typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator, typename graph_traits< leda::GRAPH<vtype,etype> >::vertex_iterator > vertices(const leda::GRAPH<vtype,etype>& g) { typedef typename graph_traits< leda::GRAPH<vtype,etype>
::vertex_iterator Iter; return std::make_pair( Iter(g.first_node(),&g), Iter(0,&g) ); } } // namespace boost
I now tried out something different. I wondered about this comment: "It is needed in order to allow us to write using boost::vertices as needed for ADL when using vector_as_graph below.", and my idea was "so that a function of that name is indeed defined" ...
I switched the order of the imports in leda_graph_cc.cpp:
#include <boost/graph/leda_graph.hpp> #include <boost/graph/graph_concepts.hpp>
and indeed, this bug is gone (there is another one in the same concept check, but I will deal with it later).
It is supposed to work in the other order; please try turning off BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK and flip the header order back and see what happens. It probably won't work, but I think that's what the standard says is supposed to happen. It would be nicer (and probably work) if the LEDA wrappers were in the leda namespace (same as the graph types), although that isn't elegant because of modifying a third-party library's namespace. -- Jeremiah Willcock

Am 19.12.2011 01:54, schrieb Jeremiah Willcock:
I switched the order of the imports in leda_graph_cc.cpp:
#include <boost/graph/leda_graph.hpp> #include <boost/graph/graph_concepts.hpp>
and indeed, this bug is gone (there is another one in the same concept check, but I will deal with it later).
It is supposed to work in the other order; please try turning off BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK
Done: #if !defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) \ && !BOOST_WORKAROUND(__GNUC__, <= 2) \ && !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x564)) // # define BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK #endif
and flip the header order back and see what happens.
It works: http://nopaste.us/5915.html With the ADL hack vertices is not found: http://nopaste.linux-dev.org/?24564
It probably won't work, but I think that's what the standard says is supposed to happen. It would be nicer (and probably work) if the LEDA wrappers were in the leda namespace (same as the graph types), although that isn't elegant because of modifying a third-party library's namespace.
No I wonder for what BOOST_VECTOR_AS_GRAPH_GRAPH_ADL_HACK is actually needed ... All the other Graph tests also run fine without it! Maybe Dave can enlighten us ... -- Jens
participants (2)
-
Jens Müller
-
Jeremiah Willcock