Re: [boost] [bgl] Bug in depth_first_search (and therefore topological_sort...)

From: Cromwell Enage (sponage_at_[hidden])
Date: 2006-07-24 14:22:40

--- Loïc Joly wrote:
> Hello,
> 
> There is a bug in the boost graph library in
> depth_first_search. When we look at the
> implementation, we can see in file 
> boost/graph/depth_first_search.hpp):
> 
>      detail::dfs_dispatch<C>::apply
>        (g,
>         choose_param(get_param(params,
> graph_visitor),
>                     
> make_dfs_visitor(null_visitor())),
>         choose_param(get_param(params,
> root_vertex_t()),
>                      *vertices(g).first),
>         params,
>         get_param(params, vertex_color)
>         );
> 
> This code makes the assumption the the graph is
> non-empty, since it calls *vertices(g).first.
> For empty graphs, this call fails.

Why not just request that the corresponding
documentation be amended to reflect the fact that both
depth_first_search and topological_sort require
non-empty graphs?  It's a simple matter of adding (0 <
num_vertices(g)) as a precondition.  I'd rather not
pay for extra runtime checks if my graphs are already
guaranteed to contain vertices.

                              Cromwell D. Enage

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com