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

From: Tony Cook (tony__cook_at_[hidden])
Date: 2005-09-15 04:15:05

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_at_[hidden]
[mailto:boost-users-bounces_at_[hidden]] On Behalf Of Jeremy Siek
Sent: 15 September 2005 01:27
To: boost-users_at_[hidden]
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_at_[hidden]
http://lists.boost.org/mailman/listinfo.cgi/boost-users