David Abrahams <dave <at> boost-consulting.com> writes:
Daniel Mitchell <danmitchell <at> mail.utexas.edu> writes:
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.
Then it seems that the real issue here is how to formulate the DFS algorithm. Is it "Given a graph g, repeatedly select a vertex and do ..." or is it "Given a graph g and a starting vertex u, do ..." In the first formulation you cannot assume a nonempty vertex set, whereas in the second you can. The issue raised by the OP results from not taking a clear stand on which formulation depth_first_search implements. If it implemented the first, there would already be code to check for an empty graph; if it implemented the second, the source vertex would be mandatory and this issue never would have been raised. In terms of code, the problem is the optional source vertex. Either make it mandatory, or don't take one at all.