Re: [Boost-users] Could the BGL graph algorithms be improved to automatically work with VertexList = listS graphs?

From: Jeremy Siek (jeremy.siek_at_[hidden])
Date: 2005-09-15 09:08:16

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