Could the BGL graph algorithms be improved to automatically work with VertexList = listS graphs?
Hi, If I define a BGL graph of the type typedef boost::adjacency_list <boost::vecS, boost::listS, boost::undirectedS, boost::no_property, boost::no_property, boost::no_property> BadGraphType ; Then many of the standard BGL graph algorithms such as boost::graph_copy will not compile (e.g you get "binary '+' : no operator found which takes a left-hand operand of type <type>" with VC7.1 - this did not help me understand what the problem really was - i.e. a missing vertex_index property!) This "no-compiler" problem is only fixed if either a vertex_index property map is made explicitly present on this graph type via VertexProperties template argument (See #5 on the BGL FAQ page (http://www.boost.org/libs/graphd/oc/faq.html .)) OR the particular graph algorithm is passed an external (or internal - if not of the vertex_index_t type) property map as a named parameter as in: boost::graph_copy (graph_in, graph_out, boost::vertex_index_map (i_map)) ; In either case prior to copying (or whatever) you need to ensure this property map is numbered contiguously from 0 to n - 1, where n is the number of graph vertices. My graph does not support an implicit vertex_index property, nor do I *want* to add an explicit vertex_index compatible property *just* to make these algorithms work. Especially as my graphs are dynamic and I would have to remember to renumber the property values to eliminate gaps after vertices are deleted. The BGL algorithms in this situation are particularly weak as first the "no-compile" messages are remote from the real problem, and when you have solved that then you have to prepare the graph properly prior using the algorithm! (if not you get memory scribbles if the indices are not contiguous and confined to 0 to n-1) These lead me to wonder if this problem can be eliminated and be automated as part of the algorithm itself, i.e. if no vertex_index property was supplied by any means, then the algorithm creates a temporary vertex index map, loads it with vertices mapped to indices 0 to n-1 and runs the algoritm out-of-the-box. It should be possible for the compiler to detect that the internal property map is missing AND the named parameter alternative is missing (in fact the implementations of these BGL algorithms *do* set out to discover that this is the case, but unfortunately a final vertex "descriptor-is-the-index" map (which is only true when VertexList=vecS) is assumed and hence the compilation failure and a lot grief and a steep learning curve is experienced :( ) Now to the point I wanted to make :). There IS a solution that can do this. However I'm not expert enough to merge this into the heart of each BGL graph algorithm algorithm that requires a vertex_index property. I have however developed crude wrappers that do this. Here is an example solution for boost::copy_graph that handles any graph type out of the box /** copy_graph_ex. A wrapper for boost::copy_graph that sets up the required vertex to 0 -> n - 1 index translation map @param g_in the graph to copy @param g_out the graph copy */ template <class G1, class G2> void copy_graph_ex (const G1& g_in, G2& g_out) { // Create a temporary external property map that maps vertex // descriptors to indices that will run 0 to n-1 typedef std::map<typename G1::vertex_descriptor, typename G1::vertices_size_type> i_type ; typedef boost::associative_property_map<i_type> i_map_type ; i_type i ; i_map_type i_map (i) ; // Load the external property map with values 0 to n-1 G1::vertices_size_type n = 0 ; G1::vertex_iterator vi ; G1::vertex_iterator vi_end ; for (boost::tie (vi, vi_end) = boost::vertices (g_in) ; vi != vi_end ; ++vi) { boost::put (i_map, *vi, n++) ; } // Get the BGL graph algorithm to use the constructed index map boost::copy_graph (g_in, g_out, boost::vertex_index_map (i_map)) ; } It would be much nicer if this external setup code was made part of the default handling of BGL graph algorithms that require it. What do to BGL experts/implementers say? Would it not be **saner** to get these algorithms to work automatically no matter what graph type was chosen? TIA Tony Cook (who went insane with this problem for two days)
Hi Tony, On Sep 14, 2005, at 11:08 AM, Tony Cook wrote:
The BGL algorithms in this situation are particularly weak as first the "no-compile" messages are remote from the real problem, and when you have solved that then you have to prepare the graph properly prior using the algorithm! (if not you get memory scribbles if the indices are not contiguous and confined to 0 to n-1) Part of the problem is the language (C++), not the library. However, we may be able to fix this by going to extraordinary lengths. Though I can't say when one of the developers will have the time to do this. It's quite tedious trying to imagine all the ways an algorithm can be misused and try to trick the compiler into giving a good error message. This is one of the reasons I wrote a Ph.D. thesis about a new language.
At some point the BGL should be updated to use the new boost named parameter library. When that happens it would be a good idea for us to keep this issue in mind and check on the error messages.
These lead me to wonder if this problem can be eliminated and be automated as part of the algorithm itself, i.e. if no vertex_index property was supplied by any means, then the algorithm creates a temporary vertex index map, loads it with vertices mapped to indices 0 to n-1 and runs the algoritm out-of-the-box.
typedef std::map<typename G1::vertex_descriptor,
typename G1::vertices_size_type> i_type ;
typedef boost::associative_property_map<i_type> i_map_type ;
It would be much nicer if this external setup code was made part of the default handling of BGL graph algorithms that require it.
What do to BGL experts/implementers say? Would it not be **saner** to get these algorithms to work automatically no matter what graph type was chosen? The problem with std::map is that it does not provide constant time access to the vertex index (it is logarithmic). Thus, the graph algorithm will run slower; it won't have the advertised time complexity. Then we'll get bug reports from people that are surprised by how slow the algorithm is.
Cheers, Jeremy
On Sep 14, 2005, at 7:26 PM, Jeremy Siek wrote:
Part of the problem is the language (C++), not the library. However, we may be able to fix this by going to extraordinary lengths. Though I can't say when one of the developers will have the time to do this. It's quite tedious trying to imagine all the ways an algorithm can be misused and try to trick the compiler into giving a good error message. This is one of the reasons I wrote a Ph.D. thesis about a new language.
And Jeremy neglected to mention that we're trying *very* hard to get some extensions into C++0x so that wretched error messages like these will be a thing of the past.
What do to BGL experts/implementers say? Would it not be **saner** to get these algorithms to work automatically no matter what graph type was chosen?
The problem with std::map is that it does not provide constant time access to the vertex index (it is logarithmic). Thus, the graph algorithm will run slower; it won't have the advertised time complexity. Then we'll get bug reports from people that are surprised by how slow the algorithm is.
It's definitely slower, but I think we need to give the usability issue more weight. I only recall ever having seen two cases where someone complained about the BGL being to slow: one was with betweenness_centrality, until we learned that the person had compiled without any optimizations; the other was with bundled properties slowing things down (due to the extra level of dispatch). On the other hand, we get questions every week about how to create property maps, especially edge property maps (because there's no way to avoid managing your own edge_index_t). We should get users hooked on the BGL first, then we can worry about getting maximal performance for them later. I've been thinking of a few ways to try to help users with creating and using property maps. It's possible that "all of them" is the right answer: 1) Make edge descriptors ordered (via <), so that users can make associative property maps more easily 2) Create templates vertex_property_map<T, Graph> and edge_property_map<T, Graph> that create external property maps without much effort from the user; in particular, that'll use an associative property map or an iterator property map depending on whether a vertex_index property is available. 3) As Tony mentions, make the algorithms a bit more lenient about the input graphs. They could use something like the class templates in #2, so long as we can still get maximal efficiency out of them when index maps are available. 4) Create new graph types (say, directed_graph<Vertex, Edge> and undirected_graph<Vertex, Edge>) that maintain vertex and edge index maps internally (as does the Python graph type). Doug
Hi Doug, All excellent points and I really hope it happens in some form :) . The BGL is great BUT yes usability should take more weight. My project manager was all for scrapping using the BGL because of some of these issues. I thought it was worth a couple more days graft to work out solutions because the payback using the BGL would be more than worth it. In my limited experience (2 months now) there are too many trip wires of the sort we are discussing. I got there in the end with my current problem but the axe is still hovering :( Can I add that misuse of graph assignment and a graph copy constructor is possible - corruptible shallow copies are the result. These methods should be given private scope to prevent (mis)use or be correctly implemented G2 = G1 ; // Compiles but NO you must use boost::graph_copy (G1, G2) instead
3) ... so long as we can still get maximal efficiency out of them when index maps are available.
This was exactly what I was asking in the original post, that my suggestion (in some form) be merged into the algorithm such that it is ONLY used if there is no vertex_index property available either by a graph vertex property OR a named parameter input to the algorithm.
4) ... that maintain vertex and edge index maps internally (as does the Python graph type).
I'm doing just this in a wrapper I have around the BGL graph types. So yes there is a problem that I guess others are also working around.
1) Make edge descriptors ordered (via <), so that users can make associative property maps more easily
Well guess what - I had to do this (but it won't work for multigraphs so it's not complete)! template<typename EdgeType> struct EdgeCompare : public std::binary_function<EdgeType, EdgeType, bool> { bool operator ()(const EdgeType& edge1, const EdgeType& edge2) const { if (edge1.m_source < edge2.m_source) return true ; if (edge1.m_source == edge2.m_source && edge1.m_target < edge2.m_target) return true ; return false ; } } ; /** An atom graph edge set type (i.e. a type that represents a set of atom/atom interactions) Note we need to supply a custom type containing a LessThanComparable functor to determine the sort order for AtomEdgeType */ typedef std::set<AtomEdgeType, EdgeCompare<AtomEdgeType> > AtomEdgeSetType ; Tony PS I've not introduced myself. I've worked on graph algorithms applications in computer chemical representation problems for 21 years and I am familiar with a whole range of graph algorithms for efficient graph isomorphism detection, subgraph isomorphism (Ullman, Sussenguth, Figeras etc), Morgan vertex labeling, graph partitioning (symmetry detection), maximal common subgraph, beta rings, k rings, smallest set of smallest rings (SSSR), extended SSSR etc etc. Hopefully over the next few years I'll be able to contribute new (to the BGL) algorithms if they prove useful. If I'm correct in my understanding the BGL is/was developed at Indiana University, in which case can I suggest you could lookup David Wild in the ChemoInformatics dept as he can comment on the utility of many graph algorithms mentioned above in the chemoinformatics domain. -----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Douglas Gregor Sent: 15 September 2005 03:02 To: boost-users@lists.boost.org Subject: Re: [Boost-users] Could the BGL graph algorithms be improved toautomatically work with VertexList = listS graphs? On Sep 14, 2005, at 7:26 PM, Jeremy Siek wrote:
Part of the problem is the language (C++), not the library. However, we may be able to fix this by going to extraordinary lengths. Though I can't say when one of the developers will have the time to do this. It's quite tedious trying to imagine all the ways an algorithm can be misused and try to trick the compiler into giving a good error message. This is one of the reasons I wrote a Ph.D. thesis about a new language.
And Jeremy neglected to mention that we're trying *very* hard to get some extensions into C++0x so that wretched error messages like these will be a thing of the past.
What do to BGL experts/implementers say? Would it not be **saner** to get these algorithms to work automatically no matter what graph type was chosen?
The problem with std::map is that it does not provide constant time access to the vertex index (it is logarithmic). Thus, the graph algorithm will run slower; it won't have the advertised time complexity. Then we'll get bug reports from people that are surprised by how slow the algorithm is.
It's definitely slower, but I think we need to give the usability issue more weight. I only recall ever having seen two cases where someone complained about the BGL being to slow: one was with betweenness_centrality, until we learned that the person had compiled without any optimizations; the other was with bundled properties slowing things down (due to the extra level of dispatch). On the other hand, we get questions every week about how to create property maps, especially edge property maps (because there's no way to avoid managing your own edge_index_t). We should get users hooked on the BGL first, then we can worry about getting maximal performance for them later. I've been thinking of a few ways to try to help users with creating and using property maps. It's possible that "all of them" is the right answer: 1) Make edge descriptors ordered (via <), so that users can make associative property maps more easily 2) Create templates vertex_property_map<T, Graph> and edge_property_map<T, Graph> that create external property maps without much effort from the user; in particular, that'll use an associative property map or an iterator property map depending on whether a vertex_index property is available. 3) As Tony mentions, make the algorithms a bit more lenient about the input graphs. They could use something like the class templates in #2, so long as we can still get maximal efficiency out of them when index maps are available. 4) Create new graph types (say, directed_graph<Vertex, Edge> and undirected_graph<Vertex, Edge>) that maintain vertex and edge index maps internally (as does the Python graph type). Doug _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
On 9/15/05 7:05 AM, "Tony Cook" <tony__cook@hotmail.com> wrote:
Can I add that misuse of graph assignment and a graph copy constructor is possible - corruptible shallow copies are the result. These methods should be given private scope to prevent (mis)use or be correctly implemented
G2 = G1 ; // Compiles but NO you must use boost::graph_copy (G1, G2) instead
If this is accurate, then it should be fixed. Types with abnormal copying semantics can't be used in STL containers or similar contexts. -- Daryle Walker Mac, Internet, and Video Game Junkie darylew AT hotmail DOT com
Hi Doug, On Sep 14, 2005, at 9:01 PM, Douglas Gregor wrote:
It's definitely slower, but I think we need to give the usability issue more weight. I only recall ever having seen two cases where someone complained about the BGL being to slow: one was with betweenness_centrality, until we learned that the person had compiled without any optimizations; the other was with bundled properties slowing things down (due to the extra level of dispatch). On the
And is the reason they don't complain because they don't care about speed, or because the BGL is fast? :) Don't get me wrong, I care about usability and I think something should be done about this.
other hand, we get questions every week about how to create property maps, especially edge property maps (because there's no way to avoid managing your own edge_index_t). We should get users hooked on the BGL first, then we can worry about getting maximal performance for them later.
I've been thinking of a few ways to try to help users with creating and using property maps. It's possible that "all of them" is the right answer:
1) Make edge descriptors ordered (via <), so that users can make associative property maps more easily 2) Create templates vertex_property_map<T, Graph> and edge_property_map<T, Graph> that create external property maps without much effort from the user; in particular, that'll use an associative property map or an iterator property map depending on whether a vertex_index property is available.
3) As Tony mentions, make the algorithms a bit more lenient about the input graphs. They could use something like the class templates in #2, so long as we can still get maximal efficiency out of them when index maps are available.
4) Create new graph types (say, directed_graph<Vertex, Edge> and undirected_graph<Vertex, Edge>) that maintain vertex and edge index maps internally (as does the Python graph type).
All of those options sound reasonable. Cheers, Jeremy
On 9/15/05, Jeremy Siek <jeremy.siek@gmail.com> wrote:
Hi Doug,
On Sep 14, 2005, at 9:01 PM, Douglas Gregor wrote:
<snip>
I've been thinking of a few ways to try to help users with creating and using property maps. It's possible that "all of them" is the right answer:
1) Make edge descriptors ordered (via <), so that users can make associative property maps more easily 2) Create templates vertex_property_map<T, Graph> and edge_property_map<T, Graph> that create external property maps without much effort from the user; in particular, that'll use an associative property map or an iterator property map depending on whether a vertex_index property is available.
3) As Tony mentions, make the algorithms a bit more lenient about the input graphs. They could use something like the class templates in #2, so long as we can still get maximal efficiency out of them when index maps are available.
4) Create new graph types (say, directed_graph<Vertex, Edge> and undirected_graph<Vertex, Edge>) that maintain vertex and edge index maps internally (as does the Python graph type).
All of those options sound reasonable.
All of Doug's options sound good to me, too, and I'd like to add one more idea. Most of the BGL algorithms operate on the assumption that if you don't pass in a vertex or edge index map explicitly, that index map should be accessible as an internal property, for instance, something like: template<typename Graph, typename VertexIndexMap> void foo(const Graph& g, VertexIndexMap vim = get(vertex_index,g)); In the above code, if g doesn't have a vertex_index property, no_property is returned from the get. What I'm thinking about is returning something other than no_property: consider another type of property map, which I'll call auto_index_property_map. It's got two data members: a shared_ptr to an associative container and an integer index called next_available_index. Its default constructor creates a new associative container, while the copy constructor and assignment operator just copy over the shared_ptr. When you call "get" on an auto_index_property_map for an element x, it checks to see if x is a key in the associative container. If it is, return the index x is associated with. If not, put the pair (x,next_available_index) in the container and return next_available_index and post-increment it. The main problem I can see with this solution is that if you call get(vertex_index,g) twice you get distinct instances of an auto_index_property_map, containing different associative containers. This could cause some pretty spectacular failures and might be a tough bug to catch within an algorithm. But from what I've seen, getting the vertex_index or edge_index property is usually done once by the algorithm, as in foo's signature above, so that all we would need to do is change the behavior of get(vertex_index,g) and get(edge_index,g) to return an auto_index_property_map. I'd be willing to code up an auto_index_property_map if anyone likes this idea, otherwise I vote for Doug's #4 above. Aaron
On Sep 15, 2005, at 11:55 AM, Aaron Windsor wrote:
The main problem I can see with this solution is that if you call get(vertex_index,g) twice you get distinct instances of an auto_index_property_map, containing different associative containers. This could cause some pretty spectacular failures and might be a tough bug to catch within an algorithm. But from what I've seen, getting the vertex_index or edge_index property is usually done once by the algorithm, as in foo's signature above, so that all we would need to do is change the behavior of get(vertex_index,g) and get(edge_index,g) to return an auto_index_property_map. I'd be willing to code up an auto_index_property_map if anyone likes this idea, otherwise I vote for Doug's #4 above.
I like the idea of being able to build an auto_index_map map. However, I don't think it should be returned from get(vertex_index, g) automatically. My concern is that we'd be lying to the user, in effect, about the presence of a vertex index property. Now, if we do exactly the same thing but call the property vertex_auto_index, then I'd be thrilled to have an implementation and integrate it into the BGL. Doug
Thank you very much Jeremy for your prompt answer. I wasn't promoting this as a real world solution. It was just an illustration of an approach that could be taken. However I *was* promoting the principle that the BGL algorithms should work with all graph types - or at *least* document which types are not supported - currently neither is true. Do you agree with this principle?
The problem with std::map is that it does not provide constant time access to the vertex index (it is logarithmic).
1. Can anyone suggest an associative container type that I can use that performs better than std::map - some sort of hash map perhaps (does boost have one)?
... Thus, the graph algorithm will run slower; it won't have the advertised time complexity. ...
Why not change the time complexity advertisement? For example clear_vertex() advertises 4 distinct time complexities depending on sequence based vs associative-container EdgeList types and directed vs undirected graph types. Surely each of the algorithms could do likewise? I would rather have something that works and documents the consequences than something that only works under narrow conditions that are NOT documented. E.g. the documentation for copy_graph (and others) does not advertise the fact that it does not work for VertexList=listS (unless the vertex_index property is explicitly present). Maybe it should. In a nutshell the BGL is behaving like Henry Ford's model T - any graph type you like as long as it is VertexList=vecS ;) - otherwise you just have to fathom it out for yourself with little help - hummmmm.
... Then we'll get bug reports from people that are surprised by how slow the algorithm is. ...
OK so instead you get bug reports about algorithms mysteriously not compiling with certain graph types (like this one ;) - and obviously very frequently at one time as this is issue #5 on the BGL FAQ! - however I missed the FAQ connection as I didn't formulate the question in the way written). Cheers, Tony Cook PS the documentation for graph_copy has an error - its says the vertex_index_map named property should map from 0 to num_vertices(G). It should read 0 to num_vertices(G) - 1. -----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Jeremy Siek Sent: 15 September 2005 01:27 To: boost-users@lists.boost.org Subject: Re: [Boost-users] Could the BGL graph algorithms be improved toautomatically work with VertexList = listS graphs? Hi Tony, On Sep 14, 2005, at 11:08 AM, Tony Cook wrote:
The BGL algorithms in this situation are particularly weak as first the "no-compile" messages are remote from the real problem, and when you have solved that then you have to prepare the graph properly prior using the algorithm! (if not you get memory scribbles if the indices are not contiguous and confined to 0 to n-1) Part of the problem is the language (C++), not the library. However, we may be able to fix this by going to extraordinary lengths. Though I can't say when one of the developers will have the time to do this. It's quite tedious trying to imagine all the ways an algorithm can be misused and try to trick the compiler into giving a good error message. This is one of the reasons I wrote a Ph.D. thesis about a new language.
At some point the BGL should be updated to use the new boost named parameter library. When that happens it would be a good idea for us to keep this issue in mind and check on the error messages.
These lead me to wonder if this problem can be eliminated and be automated as part of the algorithm itself, i.e. if no vertex_index property was supplied by any means, then the algorithm creates a temporary vertex index map, loads it with vertices mapped to indices 0 to n-1 and runs the algoritm out-of-the-box.
typedef std::map<typename G1::vertex_descriptor,
typename G1::vertices_size_type> i_type ;
typedef boost::associative_property_map<i_type> i_map_type ;
It would be much nicer if this external setup code was made part of the default handling of BGL graph algorithms that require it.
What do to BGL experts/implementers say? Would it not be **saner** to get these algorithms to work automatically no matter what graph type was chosen? The problem with std::map is that it does not provide constant time access to the vertex index (it is logarithmic). Thus, the graph algorithm will run slower; it won't have the advertised time complexity. Then we'll get bug reports from people that are surprised by how slow the algorithm is.
Cheers, Jeremy _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Hi Tony, On Sep 15, 2005, at 4:15 AM, Tony Cook wrote:
Thank you very much Jeremy for your prompt answer.
I wasn't promoting this as a real world solution. It was just an illustration of an approach that could be taken. However I *was* promoting the principle that the BGL algorithms should work with all graph types - or at *least* document which types are not supported - currently neither is true. Do you agree with this principle?
I would if that principle were possible, but it is not possible. Algorithms have lots of different requirements, and it is not practical or efficient to implement all requirements in all graph types. For example, would you suggest that we implement the Incidence Graph concept for the edge_list adaptor? It would be extremely painful to implement that, and then it would be really slow. If a graph algorithm does not document its requirements, that's a bug, and should be fixed. However, copy_graph does document its requirement for vertex_index.
1. Can anyone suggest an associative container type that I can use that performs better than std::map - some sort of hash map perhaps (does boost have one)?
A hash map will be constant time, but is still somewhat slow. Boost does not yet have one.
Why not change the time complexity advertisement? For example clear_vertex() advertises 4 distinct time complexities depending on sequence based vs associative-container EdgeList types and directed vs undirected graph types. Surely each of the algorithms could do likewise?
Yes, that's a viable option.
I would rather have something that works and documents the consequences than something that only works under narrow conditions that are NOT documented. E.g. the documentation for copy_graph (and others) does not advertise the fact that it does not work for VertexList=listS (unless the vertex_index property is explicitly present). Maybe it should.
I don't think you understand the nature of generic algorithms. I can't talk about specific graph types in the documentation for copy_graph. There are a potentially infinite number of specific graph types out there. The requirement that copy_graph needs vertex_index is documented. Also, the fact that only VertexList=vecS provides a vertex_index is also documented. It does take some time to get use to using generic algorithms. They are documented in terms of abstract properties of graphs instead of particular graph classes. This means that you have to do more work to figure out which combinations are legal.
In a nutshell the BGL is behaving like Henry Ford's model T - any graph type you like as long as it is VertexList=vecS ;) - otherwise you just have to fathom it out for yourself with little help - hummmmm.
That's an exaggeration.
OK so instead you get bug reports about algorithms mysteriously not compiling with certain graph types (like this one ;) - and obviously very frequently at one time as this is issue #5 on the BGL FAQ! - however I missed the FAQ connection as I didn't formulate the question in the way written).
This problem would be much less troublesome if we improved the error messages, which we will try to do.
PS the documentation for graph_copy has an error - its says the vertex_index_map named property should map from 0 to num_vertices (G). It should read 0 to num_vertices(G) - 1.
Thanks. -Jeremy
Thanks for all the help guys.
If a graph algorithm does not document its requirements, that's a bug, and should be fixed. However, copy_graph does document its requirement for vertex_index.
I see that now. However it is written in a difficult form which made little sense to me without that nudge. Man BGL is very steep! "Default: get(vertex_index, G)" ?? How about "Default: requires the presence of the vertex_index property map" Why else do you think FAQ #5 exists ;)
A hash map will be constant time, but is still somewhat slow. Boost does not yet have one.
:(
I don't think you understand the nature of generic algorithms.
I'm new and I'm learning. Thanks for the enlightenment :) . OK please reread this as an issue with the graph_copy algorithm. Surely all graph types should at least copy - even if *relatively* inefficiently (I can't believe that its impractical to copy!!). Worse still you can write G1 = G2 ; It compiles but doesn't work! It's shallow.
That's an exaggeration.
:) :) What I didn't tell you is that I'm *forced* by VC7.1 to use vecS,listS graphs as with my particular collection of properties, ALL other graph type combinations cause VC7.1 to issue an "Internal Compiler Error" - I should have slammed the Ford attribute onto VC7.1 - it deserves it, not BGL Anyway I'm happy this issue is being considered. I need no further assistance on this matter. Cheers, Tony
"Tony Cook" <tony__cook@hotmail.com> wrote in message news:BAY101-DAV3F0D19A90268124B3A570CB9E0@phx.gbl...
A hash map will be constant time, but is still somewhat slow. Boost does not yet have one.
:(
Have you looked at Hashed indices from Boost.MultiIndex? http://www.boost.org/libs/multi_index/doc/reference/hash_indices.html I'm not sure if it's compatible with BGL. Jeff Flinn
Hi Tony, On Sep 15, 2005, at 9:57 AM, Tony Cook wrote:
How about
"Default: requires the presence of the vertex_index property map"
Why else do you think FAQ #5 exists ;)
That's a fine suggestion, I've made a change along those lines to every graph algorithm.
I'm new and I'm learning. Thanks for the enlightenment :) . OK please reread this as an issue with the graph_copy algorithm. Surely all graph types should at least copy - even if *relatively* inefficiently (I can't believe that its impractical to copy!!).
Worse still you can write
G1 = G2 ;
It compiles but doesn't work! It's shallow.
Ew, that doesn't sound right. What graph type was that with? Could you send a little program that demonstrates the problem.
That's an exaggeration.
:) :)
What I didn't tell you is that I'm *forced* by VC7.1 to use vecS,listS graphs as with my particular collection of properties, ALL other graph type combinations cause VC7.1 to issue an "Internal Compiler Error" - I should have slammed the Ford attribute onto VC7.1 - it deserves it, not BGL
Ugh, I thought our days of ICE's from VC was over... that brings back bad memories from the days of VC 6.
Anyway I'm happy this issue is being considered. I need no further assistance on this matter.
Thanks for reporting these troubles, and thanks for encouraging the use of the BGL at work! Cheers, Jeremy
Ew, that doesn't sound right. What graph type was that with? Could you send a little program that demonstrates the problem.
OK scrub that problem (blush) - it was mine - one of my property values shallow copied when it shouldn't have
Ugh, I thought our days of ICE's from VC was over... that brings back bad memories from the days of VC 6.
I can post the exact details when I'm back at work tomorrow but it occurs somewere in MPLs /plain/apply_wrap.hpp which I presume the BGL is using indirectly. I've done some tracing as the interesting thing is that the /plain/ version was selected and not the /msvc60/ or /msvc70/ versions of apply_wrap.hpp. The crux is I can see some conditional compilation in the MPL that knows about VC6.0 and VC7.0 but it is *unaware* of VC7.1 and thus selects the /plain/ version (maybe intentionally) - however VC7.1 chokes in certain combinations of graph type/property types.There is no /msvc71/ compiler specific stuff in MPL, is VC7.1 requiring no workarounds? This is scaring the hell out of me as adding new vertex or edge properties is apt to trip an ICE, as is changing the graph VertexList and EdgeList types. I've been lucky in that reordering the property type nests has so far cured the prob - but for how much longer - the combination to try are growing - and property bundles are also ICE tripping. I've done the obvious and tried fooling boost into thinking its being compiled under VC7.0 but I haven't succeded yet. Tony
The problem with std::map is that it does not provide constant time access to the vertex index (it is logarithmic). Thus, the graph algorithm will run slower; it won't have the advertised time complexity. Then we'll get bug reports from people that are surprised by how slow the algorithm is.
As a postscript to this issue with graph_copy, I note that the current implementation of the related boost::adjacency_list<> operator= uses a std::map in the core of its implementation (boost 1.33.0 adjacency_list.hpp line 1775). So this objection to std::map was overruled here. However the author has noted the non constant time. (The non existent boost::hash_map would improve matters - yes?) inline void copy_impl(const adj_list_impl& x_) { ... // Would be better to have a constant time way to get from // vertices in x to the corresponding vertices in *this. 1775: std::map<stored_vertex*,stored_vertex*> vertex_map; ... for (tie(vi, vi_end) = vertices(x); vi != vi_end; ++vi) { ... vertex_map[(stored_vertex*)*vi] = v; } ... for (tie(ei, ei_end) = edges(x); ei != ei_end; ++ei) { ... tie(e, inserted) = add_edge(vertex_map[(stored_vertex*)s], vertex_map[(stored_vertex*)t], *this); ... } } Tony
participants (7)
-
Aaron Windsor -
Daryle Walker -
Doug Gregor -
Douglas Gregor -
Jeff Flinn -
Jeremy Siek -
Tony Cook