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

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:

>

>> 

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