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

From: Daniel Mitchell (danmitchell_at_[hidden])
Date: 2006-07-24 14:29:26

Loïc Joly <loic.joly <at> reportive.com> writes:

> 
> 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.

I'm not sure I'd call that a bug; after all, the graph must contain at least a 
source vertex for DFS to be sensible. I would say that having a non-empty 
graph is a pre-condition for calling DFS. Would it be better to make the 
source a mandatory argument as in breadth_first_search?

D.