[BGL] Unable to sort list of edge_descriptors
I'm trying to sort a list of edge_descriptors, but I get the compiler error described below. typedef adjacency_list < vecS, vecS, bidirectionalS >::edge_descriptor edgeDescriptor; // defined globally template < typename Graph, typename edgeDescriptor > struct SortByName : public binary_function<edgeDescriptor, edgeDescriptor, bool> { bool operator()(const Graph & g, const edgeDescriptor& a, const edgeDescriptor& b) { return g[a].eName < g[b].eName; } }; template < typename Graph > void Sort_Test(Graph & g) { typedef std::list<edgeDescriptor> edge_list; typename graph_traits<Graph>::edge_iterator edge_iter, edges_end; edge_list A; for (tie(edge_iter, edges_end) = edges(g); edge_iter != edges_end; ++edge_iter) A.push_back(*edge_iter); for (edge_list::iterator i = A.begin(); i != A.end(); ++i) cout << " *i = " << " " << g[*i].eName << "\n"; // If the following line is commented out the program compiles and runs OK. A.sort(SortByName< typename Graph, typename edgeDescriptor >()); //With the above line uncommented the compiler says: /* ./Includes/Utilities.cpp: In function ‘void Sort_Test(Graph&)’: ./Includes/Utilities.cpp:539: error: wrong number of template arguments (1, should be 2) ./Includes/Utilities.cpp:513: error: provided for ‘template<class Graph, class edgeDescriptor> struct SortByName’ make: *** [plc] Error 1 */ } But clearly there are two template arguments - < typename Graph, typename edgeDescriptor > Thanks
Hi, I am not absolutely sure on this, but it seems to me, that you have wrongly specified your SortByName. The compiler accepts its code, when it is not used (commented out), because it will not try to create an actual instance of the code (formulation might be a bit simplistic). The syntax looks good to me, so this should not be the problem. But when the sort-algorithm wants to use this as functor for the comparison, it will fail for several reasons. First: when you look at your definition of SortByName, where should a functor get the information of the Graph (g) from? You need to specify it as an attribute so it can access the information on the edges in the graph. Second: sort will expect an operator() that will use two elements that should be compared, so specifying a Graph there will probably confuse it. My suggestion for the struct would be: template < typename Graph > struct SortByName : { template< typename edgeDescriptor > bool operator()( const edgeDescriptor& a, const edgeDescriptor& b) const { return g[a].eName < g[b].eName; } Graph g; }; And finally third, you have not specified a constructor or detailed constructor in the struct nor did you specify the graph in your call of sort(). This is important so the struct knows where to take the information from. I am aware, that in my example, it is missing the "public binary_function<edgeDescriptor,edgeDescriptor, bool>". I have to admit, that I do not completely understand what this should do here. Probably to inherit something?! This might be the reason why the compiler is complaining, as it probably expects the two template-arguments here? It would also be a bit easier to find out what is really causing the issue if you could provide a more complete example so one can see the rest of the code. A simple short main would be enough, especially as you have already defined your functions separately. Working with the BGL, I have experienced quite some situations where the compiler was complaining about template-arguments, and such, that were interenstingly caused by a completely different piece of code, so if my suggestion does not fix the problem, please include a complete example. Best, Cedric On Saturday, 6. November 2010 10:04:57 Mike Douglass wrote:
I'm trying to sort a list of edge_descriptors, but I get the compiler error described below.
typedef adjacency_list < vecS, vecS, bidirectionalS >::edge_descriptor edgeDescriptor; // defined globally
template < typename Graph, typename edgeDescriptor > struct SortByName : public binary_function<edgeDescriptor, edgeDescriptor, bool> { bool operator()(const Graph & g, const edgeDescriptor& a, const edgeDescriptor& b) { return g[a].eName < g[b].eName; }
};
template < typename Graph > void Sort_Test(Graph & g) {
typedef std::list<edgeDescriptor> edge_list; typename graph_traits<Graph>::edge_iterator edge_iter, edges_end;
edge_list A;
for (tie(edge_iter, edges_end) = edges(g); edge_iter != edges_end; ++edge_iter) A.push_back(*edge_iter);
for (edge_list::iterator i = A.begin(); i != A.end(); ++i) cout << " *i = " << " " << g[*i].eName << "\n";
// If the following line is commented out the program compiles and runs OK. A.sort(SortByName< typename Graph, typename edgeDescriptor >()); //With the above line uncommented the compiler says:
/* ./Includes/Utilities.cpp: In function ‘void Sort_Test(Graph&)’: ./Includes/Utilities.cpp:539: error: wrong number of template arguments (1, should be 2) ./Includes/Utilities.cpp:513: error: provided for ‘template<class Graph, class edgeDescriptor> struct SortByName’ make: *** [plc] Error 1 */
}
But clearly there are two template arguments - < typename Graph, typename edgeDescriptor >
Thanks
I have attached a minimal working program to test the sort function on a list of edges. Compile with : g++ -O3 prog.cpp -o prog The problem is line "myList.sort(SortByName< graph_t <edge_t> >);" near the bottom of the page. See comments. //======================================================================= // Sort Testing Program - prog.cpp //======================================================================= #include <iostream> #include <string> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/properties.hpp> using namespace boost; using namespace std; struct vertex_properties { }; struct edge_properties { string eName; }; typedef adjacency_list < vecS, vecS, bidirectionalS >::edge_descriptor edge_t; typedef adjacency_list < vecS, vecS, bidirectionalS >::vertex_descriptor vertex_t; typedef adjacency_list < vecS, vecS, bidirectionalS, vertex_properties, edge_properties > graph_t; //////////////////////////////////////////////////////////////////////////////////////////////////////////////////// template < typename Graph > void add_edges(Graph & g) { // Add some edges with names. typename graph_traits<Graph>::edge_iterator edge_iter, edges_end; std::pair< typename graph_traits<Graph>::edge_descriptor, bool > a = add_edge(1,2,g); g[a.first].eName = "A"; std::pair< typename graph_traits<Graph>::edge_descriptor, bool > b = add_edge(1,3,g); g[b.first].eName = "B"; std::pair< typename graph_traits<Graph>::edge_descriptor, bool > c = add_edge(2,1,g); g[c.first].eName = "C"; std::pair< typename graph_traits<Graph>::edge_descriptor, bool > d = add_edge(2,3,g); g[d.first].eName = "D"; cout << endl << " list of edges " << endl; for (tie(edge_iter, edges_end) = edges(g); edge_iter != edges_end; ++edge_iter) cout << " " << g[*edge_iter].eName << endl; } template < typename Graph > struct SortByName { // The Predicate template < typename edge_t > bool operator()(const edge_t& a, const edge_t& b) const { return g[a].eName < g[b].eName; } Graph g; }; template < typename Graph > void Sort_Test(Graph & g) { // Test the sort function. typedef std::list<graph_traits<graph_t>::edge_descriptor> edge_list; typename graph_traits<Graph>::edge_iterator edge_iter, edges_end; edge_list myList; // Load myList with the edges of g for (tie(edge_iter, edges_end) = edges(g); edge_iter != edges_end; ++edge_iter) myList.push_back(*edge_iter); // Write out myList cout << endl << " myList " << endl; for (edge_list::iterator i = myList.begin(); i != myList.end(); ++i) cout << " " << g[*i].eName << endl; // Sort myList // If the following line is commented out the program compiles and runs OK. myList.sort(SortByName< graph_t <edge_t> >); //With the above line uncommented the compiler says: // "prog.cpp:88: error: ‘graph_t’ is not a template" -- I'm stumped. } int main() { graph_t g; add_edges(g); Sort_Test(g); } ________________________________ From: Cedric Laczny <cedric.laczny@gmx.de> To: boost-users@lists.boost.org Sent: Sat, November 6, 2010 3:54:49 AM Subject: Re: [Boost-users] [BGL] Unable to sort list of edge_descriptors if my suggestion does not fix the problem, please include a complete example.
Hi, first of all, nice example you specified and also a good idea to include the command-line used to compile. On Sunday, 7. November 2010 05:55:14 Mike Douglass wrote:
I have attached a minimal working program to test the sort function on a list of edges. Compile with : g++ -O3 prog.cpp -o prog
The problem is line "myList.sort(SortByName< graph_t <edge_t> >);" near the bottom of the page. See comments.
Interstingly, the problem is not BGL related. You simply have mixed up some things with using templates here. When you define a struct-template with one parameter, as you do with Graph, then you must also only specify one. You specified a graph_t< edge_t >. However, your graph_t is just a typedef for an adjacency_list and this adjacency_list is not a template. And that's exactly what the compiler is complaining about. So if you change: myList.sort(SortByName< graph_t <edge_t> >); to: myList.sort(SortByName< graph_t >()); your example compiles fine here on my Linux machine. I didn't check if it behaves the way you want it to, but this should be easier to do by yourself when your program is now running. Best, Cedric
//=======================================================================
// Sort Testing Program - prog.cpp
//=======================================================================
#include <iostream> #include <string> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/properties.hpp>
using namespace boost; using namespace std;
struct vertex_properties {
};
struct edge_properties { string eName; };
typedef adjacency_list < vecS, vecS, bidirectionalS >::edge_descriptor edge_t; typedef adjacency_list < vecS, vecS, bidirectionalS
::vertex_descriptor vertex_t; typedef adjacency_list < vecS, vecS, bidirectionalS, vertex_properties, edge_properties > graph_t;
/////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////
template < typename Graph > void add_edges(Graph & g) { // Add some edges with names.
typename graph_traits<Graph>::edge_iterator edge_iter, edges_end;
std::pair< typename graph_traits<Graph>::edge_descriptor, bool > a = add_edge(1,2,g); g[a.first].eName = "A"; std::pair< typename graph_traits<Graph>::edge_descriptor, bool > b = add_edge(1,3,g); g[b.first].eName = "B"; std::pair< typename graph_traits<Graph>::edge_descriptor, bool > c = add_edge(2,1,g); g[c.first].eName = "C"; std::pair< typename graph_traits<Graph>::edge_descriptor, bool > d = add_edge(2,3,g); g[d.first].eName = "D";
cout << endl << " list of edges " << endl; for (tie(edge_iter, edges_end) = edges(g); edge_iter != edges_end; ++edge_iter) cout << " " << g[*edge_iter].eName << endl;
}
template < typename Graph > struct SortByName { // The Predicate
template < typename edge_t > bool operator()(const edge_t& a, const edge_t& b) const { return g[a].eName < g[b].eName; }
Graph g;
};
template < typename Graph > void Sort_Test(Graph & g) { // Test the sort function.
typedef std::list<graph_traits<graph_t>::edge_descriptor> edge_list; typename graph_traits<Graph>::edge_iterator edge_iter, edges_end;
edge_list myList;
// Load myList with the edges of g for (tie(edge_iter, edges_end) = edges(g); edge_iter != edges_end; ++edge_iter) myList.push_back(*edge_iter);
// Write out myList cout << endl << " myList " << endl; for (edge_list::iterator i = myList.begin(); i != myList.end(); ++i) cout << " " << g[*i].eName << endl;
// Sort myList // If the following line is commented out the program compiles and runs OK. myList.sort(SortByName< graph_t <edge_t> >); //With the above line uncommented the compiler says: // "prog.cpp:88: error: ‘graph_t’ is not a template" -- I'm stumped.
}
int main() {
graph_t g;
add_edges(g);
Sort_Test(g);
}
________________________________ From: Cedric Laczny <cedric.laczny@gmx.de> To: boost-users@lists.boost.org Sent: Sat, November 6, 2010 3:54:49 AM Subject: Re: [Boost-users] [BGL] Unable to sort list of edge_descriptors
if my suggestion does not fix the problem, please include a complete example.
Hi Mike, This problem intrigued me enough that I felt like actually doing the work to make sense of it - which turned out to be a useful learning experience, as I now: (a) better understand the typename keyword, and (b) realise how amazingly helpful the Clang C++ compiler output can be. :) Short explanation - I think you did at least three things wrong: 1. you used the "typename" keyword incorrectly, 2. you defined the SortByName functor class incorrectly (inheriting from std::binary_function when the operator() was _not_ a binary function), then 3. you *used* the SortByName functor incorrectly (by supplying it to std::list::sort, which expects a 2-arg function instead of 3-arg). Longer explanation below: On 06/11 02:04:57, Mike Douglass wrote:
I'm trying to sort a list of edge_descriptors, but I get the compiler error described below. [ ... ] //With the above line uncommented the compiler says:
/* ./Includes/Utilities.cpp: In function ???void Sort_Test(Graph&)???: ./Includes/Utilities.cpp:539: error: wrong number of template arguments (1, should be 2) ./Includes/Utilities.cpp:513: error: provided for ???template<class Graph, class edgeDescriptor> struct SortByName??? make: *** [plc] Error 1 */ [ ... ] But clearly there are two template arguments - < typename Graph, typename edgeDescriptor >
(Note: I rewrote your code into a bastardised form that doesn't use Boost::Graph, as the problem doesn't look like it's got anything to do with that.) Compile the attached douglass-broken.cpp with GNU g++ and you get error output closely matching your report (I've replaced GCC's open/close single-quotes with ' to avoid encoding issues): ---------------------------------------------------------------------- $ g++ douglass-broken.cpp -o douglas-broken douglass-broken.cpp: In function 'void Sort_Test(Graph&)': douglass-broken.cpp:45:62: error: wrong number of template arguments (1, should be 2) douglass-broken.cpp:21:8: error: provided for 'template<class Graph, class edgeDescriptor> struct SortByName' $ ---------------------------------------------------------------------- I agree, it's not a particuarly helpful error message - in fact it's outright misleading. The output from clang++, however, is *extremely* helpful (though it's much easier to read with the default coloured/bolded output, here it's just plain text): ---------------------------------------------------------------------- $ clang++ douglass-broken.cpp -o douglass-broken douglass-broken.cpp:45:32: error: expected a qualified name after 'typename' A.sort(SortByName<typename Graph, typename edgeDescriptor>()); ^ douglass-broken.cpp:45:48: error: expected a qualified name after 'typename' A.sort(SortByName<typename Graph, typename edgeDescriptor>()); ^ In file included from douglass-broken.cpp:2: In file included from /usr/include/c++/4.5.1/list:65: /usr/include/c++/4.5.1/bits/list.tcc:286:12: error: no matching function for call to object of type 'SortByName<std::map<std::basic_string<char>, Edge, std::less<std::basic_string<char> >, std::allocator<std::pair<std::basic_string<char> const, Edge> > >, std::basic_string<char> >' if (__comp(*__first2, *__first1)) ^~~~~~ /usr/include/c++/4.5.1/bits/list.tcc:398:7: note: in instantiation of function template specialization 'std::list<std::basic_string<char>, std::allocator<std::basic_string<char> > >::merge<SortByName<std::map<std::basic_string<char>, Edge, std::less<std::basic_string<char> >, std::allocator<std::pair<std::basic_string<char> const, Edge> > >, std::basic_string<char> > >' requested here __counter->merge(__carry, __comp); ^ douglass-broken.cpp:45:5: note: in instantiation of function template specialization 'std::list<std::basic_string<char>, std::allocator<std::basic_string<char> > >::sort<SortByName<std::map<std::basic_string<char>, Edge, std::less<std::basic_string<char> >, std::allocator<std::pair<std::basic_string<char> const, Edge> > >, std::basic_string<char> > >' requested here A.sort(SortByName<typename Graph, typename edgeDescriptor>()); ^ douglass-broken.cpp:64:5: note: in instantiation of function template specialization 'Sort_Test<std::map<std::basic_string<char>, Edge, std::less<std::basic_string<char> >, std::allocator<std::pair<std::basic_string<char> const, Edge> > > >' requested here Sort_Test<Graph>(the_graph); ^ douglass-broken.cpp:23:10: note: candidate function not viable: requires 3 arguments, but 2 were provided bool operator()(const Graph& g, const edgeDescriptor& a, const edgeDescriptor& b) ^ 3 errors generated. ---------------------------------------------------------------------- So, the first problem is that you used typename where it shouldn't be used, in this line: A.sort(SortByName<typename Graph, typename edgeDescriptor>()); ...and I suspect that confused the g++ parser so that it interpreted the expression "typename Graph, typename edgeDescriptor" as a *single* type, resulting in the confusing error message. You can verify this by adding extra nonsense types in the same way, eg.: A.sort(SortByName<typename Graph, typename edgeDescriptor, typename NonexistentType, typename Rubbish, typename Bollocks>()); Compile that and the error message supplied by my g++ (I'm using version 4.5.1) is still the same "wrong number of template arguments (1, should be 2)", despite it now looking like *five* arguments :). As you can see, the Clang C++ compiler does a much better job, both pointing out the typename-usage error *and* reporting (albeit indirectly) that you're supplying a three-argument functor to the std::list::sort, when it actually requires a binary functor/function. (Note: To be fair to GCC, once you remove the two incorrect "typename" keywords in the A.sort line, it also generates a usable error message.) One way to fix it would be as Cedric suggested, and that's the model I used in my douglass-working.cpp (attached). I changed SortByName so it requires a const Graph& in its constructor, stores a reference to that in a private variable, *then* changed SortByName::operator() to take two edgeDescriptor args and return bool. It is dicey in one way, in that it stores a *reference* to its Graph - so if the SortByName object outlives the Graph then it could blow up spectacularly. But the alternative of copying the entire graph seemed a bit excessive. Another way to fix it (and also avoid the reference-storing problem) requires using Boost::Bind - change SortByName to this: ---------------------------------------------------------------------- template <typename G, typename ED> struct SortByName { typedef bool result_type; // required for use by STL algorithms. result_type operator()(G& g, const ED& a, const ED& b) { return g[a].eName < g[b].eName; } }; ---------------------------------------------------------------------- ...and the A.sort call to this: A.sort( boost::bind(SortByName<Graph, edgeDescriptor>(), g, _1, _2) ); That seems to work fine, and may be a closer match to what you originally intended. Pete. -- "DAMN WHO MESSED WITH MY CAPSLOCK KEY that's better." -- geoff lane, <e886430646@swirld.mcc.ac.uk>, asr
Hi Pete, On Sunday, 7. November 2010 07:20:50 Peter Wright wrote:
One way to fix it would be as Cedric suggested, and that's the model I used in my douglass-working.cpp (attached). I changed SortByName so it requires a const Graph& in its constructor, stores a reference to that in a private variable, *then* changed SortByName::operator() to take two edgeDescriptor args and return bool.
It is dicey in one way, in that it stores a *reference* to its Graph - so if the SortByName object outlives the Graph then it could blow up spectacularly. But the alternative of copying the entire graph seemed a bit excessive.
Another way to fix it (and also avoid the reference-storing problem) requires using Boost::Bind - change SortByName to this:
---------------------------------------------------------------------- template <typename G, typename ED> struct SortByName { typedef bool result_type; // required for use by STL algorithms. result_type operator()(G& g, const ED& a, const ED& b) { return g[a].eName < g[b].eName; } }; ----------------------------------------------------------------------
...and the A.sort call to this:
A.sort( boost::bind(SortByName<Graph, edgeDescriptor>(), g, _1, _2) );
That seems to work fine, and may be a closer match to what you originally intended.
I have to agree that your solution is nicer with respect to the living time of the graph and struct, respectively. Those are things that are easily neglected and can hit you very bad. Therefore, note to myself: keep such things always in the back of your head!
Pete.
Best regards and thank you for the idea, Cedric
Thank you Cedric and Peter. I implemented your suggestions and my program is working perfectly. ________________________________ From: Cedric Laczny <cedric.laczny@gmx.de> To: boost-users@lists.boost.org Sent: Sun, November 7, 2010 7:41:18 AM Subject: Re: [Boost-users] [BGL] Unable to sort list of edge_descriptors Hi Pete, On Sunday, 7. November 2010 07:20:50 Peter Wright wrote:
One way to fix it would be as Cedric suggested, and that's the model I used in my douglass-working.cpp (attached). I changed SortByName so it requires a const Graph& in its constructor, stores a reference to that in a private variable, *then* changed SortByName::operator() to take two edgeDescriptor args and return bool.
It is dicey in one way, in that it stores a *reference* to its Graph - so if the SortByName object outlives the Graph then it could blow up spectacularly. But the alternative of copying the entire graph seemed a bit excessive.
Another way to fix it (and also avoid the reference-storing problem) requires using Boost::Bind - change SortByName to this:
---------------------------------------------------------------------- template <typename G, typename ED> struct SortByName { typedef bool result_type; // required for use by STL algorithms. result_type operator()(G& g, const ED& a, const ED& b) { return g[a].eName < g[b].eName; } }; ----------------------------------------------------------------------
...and the A.sort call to this:
A.sort( boost::bind(SortByName<Graph, edgeDescriptor>(), g, _1, _2) );
That seems to work fine, and may be a closer match to what you originally intended.
I have to agree that your solution is nicer with respect to the living time of the graph and struct, respectively. Those are things that are easily neglected and can hit you very bad. Therefore, note to myself: keep such things always in the back of your head!
Pete.
Best regards and thank you for the idea, Cedric _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Sun, Nov 7, 2010 at 1:20 AM, Peter Wright <pete@flooble.net> wrote: It is dicey in one way, in that it stores a *reference* to its Graph -
so if the SortByName object outlives the Graph then it could blow up spectacularly. But the alternative of copying the entire graph seemed a bit excessive.
Another way to fix it (and also avoid the reference-storing problem) requires using Boost::Bind - change SortByName to this:
<snip/> ...and the A.sort call to this:
A.sort( boost::bind(SortByName<Graph, edgeDescriptor>(), g, _1, _2) );
It does avoid the reference-storing problem. I believe it does so by copying the entire graph. boost::bind() stores its parameters by value. If that is in fact excessive, you could write: A.sort( boost::bind(SortByName<Graph, edgeDescriptor>(), boost::ref(g), _1, _2) ); Now you're passing a reference again. It's unfortunate that you have to know whether a given function stores its parameters to know whether passing a reference might incur lifespan troubles. My impulse would be to think: "Hmm, sort(), I see no reason why any of its parameters should persist beyond its return." I assume that the whole boost::bind() value will be destroyed on return from sort(), therefore the bound reference to g as well.
participants (4)
-
Cedric Laczny -
Mike Douglass -
Nat Linden -
Peter Wright