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 >);" 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 >); 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 #include

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::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 >); //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 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 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 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(), 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

On Sun, Nov 7, 2010 at 1:20 AM, Peter Wright 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(), 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(), 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.