From: David Abrahams (dave_at_[hidden])
Date: 2006-07-25 10:42:03
Daniel Mitchell <danmitchell_at_[hidden]> writes:
> Loïc Joly <loic.joly <at> reportive.com> writes:
>> There is a bug in the boost graph library in depth_first_search. When we
>> look at the implementation, we can see in file
>> choose_param(get_param(params, graph_visitor),
>> choose_param(get_param(params, root_vertex_t()),
>> 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk