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