From: Daniel Mitchell (danmitchell_at_[hidden])
Date: 2006-07-25 14:59:59
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
> > 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk