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

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