Daniel Mitchell <danmitchell@mail.utexas.edu> writes:
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?
No. The classic DFS algorithm works on disconnected graphs by repeatedly selecting a vertex and doing DFS from there. It's weird that BFS and DFS are different in this regard, but there's a reason for it, IIRC, which now escapes me. -- Dave Abrahams Boost Consulting www.boost-consulting.com