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-14 19:26:31

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