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::vertices_size_type> i_type ;
typedef boost::associative_property_map
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