boost.graph question concerning edge descriptor details
I'm using gcc v3.4.1 and boost_CVS captured on Tue Jun 29 05:25:17 EDT 2004. I'm developing a boost.graph application that must deal with multiple graphs. The following typedefs describe how its using boost.graph: typedef boost::adjacency_list<boost::vecS,boost::vecS,boost::bidirectionalS> GraphT; typedef boost::shared_ptr<GraphT> GraphPtr; typedef boost::graph_traits <GraphT>::vertex_descriptor Vertex; typedef boost::graph_traits <GraphT>::edge_descriptor Edge; In addition, I have various maps that must act as a "bridge" between these graphs. I'm using the following typedefs as keys in such maps: typedef std::pair<GraphPtr,Vertex> ExternalVertex; typedef std::pair<GraphPtr,Edge> ExternalEdge; I've used ExternalVertex successfully in two different maps. Now I'm having trouble populating the first map that uses ExternalEdge. The compiler warnings that I'm getting sugguest that Edge does have an "operator<" method. Specifically its: error: no match for 'operator<' in '__x->std::pair<GraphPtr, Edge>::second < __y->std::pair<GraphPtr, Edge>::second' I'm wondering why Edge is different from Vertex. As you can see, as I've defined GraphT, both edge and vertex properties should be no_property. Any guidance that assists me to, at worst case, write a Compare operator for my "map<ExternalEdge,...>" containers would be appreciated.
On Aug 20, 2004, at 3:53 PM, Jeff Holle wrote:
I'm using gcc v3.4.1 and boost_CVS captured on Tue Jun 29 05:25:17 EDT 2004. I'm developing a boost.graph application that must deal with multiple graphs.
The following typedefs describe how its using boost.graph: typedef boost::adjacency_list<boost::vecS,boost::vecS,boost::bidirectionalS> GraphT; [snip] I've used ExternalVertex successfully in two different maps.
Since the vertices are stored in an std::vector, the vertex descriptor is actually an unsigned integer in [0:num_vertices(g)).
Now I'm having trouble populating the first map that uses ExternalEdge. The compiler warnings that I'm getting sugguest that Edge does have an "operator<" method. Specifically its: error: no match for 'operator<' in '__x->std::pair<GraphPtr, Edge>::second < __y->std::pair<GraphPtr, Edge>::second'
Right. Edge descriptors do not have a < operator.
I'm wondering why Edge is different from Vertex.
It's not always clear how to order edges, nor is it clear how to order vertices except when the vertices are stored in an std::vector.
Any guidance that assists me to, at worst case, write a Compare operator for my "map<ExternalEdge,...>" containers would be appreciated.
You have a few options here: 1) You could just add the property as an internal property 2) You could add (and maintain!) an edge_index internal property and order based on that 3) If you don't have parallel edges, you could order based on std::make_pair(source(e, g), target(e, g)). Doug
I may have answered my own question. The Compare functor that does the trick is: struct ltExternalEdge : public std::binary_function<ExternalEdge,ExternalEdge, bool> { bool operator()(const ExternalEdge& __x, const ExternalEdge& __y) const { return (__x.first < __y.first || (!(__y.first < __x.first) && __x.second.get_property() < __y.second.get_property())) ? true : false; } }; Is such a Compare operator safe? Note that I'm note using internal properties. It would be really nice if the object that edge_iterator references implemenented a operator< method. Then it would work seamlessly with the std::pair operator< method, which I pretty much copied in the above code. Doug Gregor wrote:
On Aug 20, 2004, at 3:53 PM, Jeff Holle wrote:
I'm using gcc v3.4.1 and boost_CVS captured on Tue Jun 29 05:25:17 EDT 2004. I'm developing a boost.graph application that must deal with multiple graphs.
The following typedefs describe how its using boost.graph: typedef boost::adjacency_list<boost::vecS,boost::vecS,boost::bidirectionalS> GraphT;
[snip]
I've used ExternalVertex successfully in two different maps.
Since the vertices are stored in an std::vector, the vertex descriptor is actually an unsigned integer in [0:num_vertices(g)).
Now I'm having trouble populating the first map that uses ExternalEdge. The compiler warnings that I'm getting sugguest that Edge does have an "operator<" method. Specifically its: error: no match for 'operator<' in '__x->std::pair<GraphPtr, Edge>::second < __y->std::pair<GraphPtr, Edge>::second'
Right. Edge descriptors do not have a < operator.
I'm wondering why Edge is different from Vertex.
It's not always clear how to order edges, nor is it clear how to order vertices except when the vertices are stored in an std::vector.
Any guidance that assists me to, at worst case, write a Compare operator for my "map<ExternalEdge,...>" containers would be appreciated.
You have a few options here: 1) You could just add the property as an internal property 2) You could add (and maintain!) an edge_index internal property and order based on that 3) If you don't have parallel edges, you could order based on std::make_pair(source(e, g), target(e, g)).
Doug
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On Aug 23, 2004, at 11:30 AM, Jeff Holle wrote:
I may have answered my own question. The Compare functor that does the trick is: struct ltExternalEdge : public std::binary_function<ExternalEdge,ExternalEdge, bool> { bool operator()(const ExternalEdge& __x, const ExternalEdge& __y) const { return (__x.first < __y.first || (!(__y.first < __x.first) && __x.second.get_property() < __y.second.get_property())) ? true : false; } };
Is such a Compare operator safe? Note that I'm note using internal properties.
This is not guaranteed to work, because edge descriptors aren't required to have the "get_property" or "first" members. Practically speaking, I think it will work, but can't be sure.
It would be really nice if the object that edge_iterator references implemenented a operator< method. Then it would work seamlessly with the std::pair operator< method, which I pretty much copied in the above code.
I'm not sure that this can always be implemented efficiently, but it surely would be useful. Doug
participants (1)
-
Doug Gregor -
Jeff Holle