[bgl] Bug in depth_first_search (and therefore topological_sort...)
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. Best regards, -- Loïc
--- Loïc Joly wrote:
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.
Why not just request that the corresponding documentation be amended to reflect the fact that both depth_first_search and topological_sort require non-empty graphs? It's a simple matter of adding (0 < num_vertices(g)) as a precondition. I'd rather not pay for extra runtime checks if my graphs are already guaranteed to contain vertices. Cromwell D. Enage __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
Cromwell Enage a écrit :
Why not just request that the corresponding documentation be amended to reflect the fact that both depth_first_search and topological_sort require non-empty graphs? It's a simple matter of adding (0 < num_vertices(g)) as a precondition. I'd rather not pay for extra runtime checks if my graphs are already guaranteed to contain vertices.
Does it have to require a specific test ? When iterating over a container from begin() to end(), I don't have to introduce some special cases to handle an empty container. It might be possible to do the same for topological_sort. Anyway, if you believe such a test could really have any visible impact on performances, maybe two versions of the algorithms would be another option, just like std::vector<T>::at and std::vector<T>::operator[]. -- Loïc
--- Loïc Joly wrote:
Cromwell Enage a écrit:
Why not just request that the corresponding documentation be amended to reflect the fact that both depth_first_search and topological_sort require non-empty graphs? It's a simple matter of adding (0 < num_vertices(g)) as a precondition. I'd rather not pay for extra runtime checks if my graphs are already guaranteed to contain vertices.
Does it have to require a specific test? When iterating over a container from begin() to end(), I don't have to introduce some special cases to handle an empty container. It might be possible to do the same for topological_sort.
At each iteration, one always tests if the current iterator is past-the-end of the container or not. Graph algorithms don't exactly do that; they usually terminate after visiting all the vertices [that are reachable from the source vertex].
Anyway, if you believe such a test could really have any visible impact on performances, maybe two versions of the algorithms would be another option, just like std::vector<T>::at and std::vector<T>::operator[].
I'll leave it to the maintainers to determine that. Cromwell D. Enage __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
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? D.
Daniel Mitchell a écrit :
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.
It may be so for depth-first-search, I'm not a domain expert at all. In that case, maybe just adding this requirement to the doc would be enough. However, for topological_sort, this goes against my expectations. std::sort on an empty STL sequence may be useless, it is however defined and does the right thing. And it allows to write generic code easily, without requiring the user to check anything before. I do not see any reason why topological_sort would not behave the same. -- Loïc
Loïc Joly <loic.joly <at> reportive.com> writes:
Daniel Mitchell a écrit :
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.
It may be so for depth-first-search, I'm not a domain expert at all. In that case, maybe just adding this requirement to the doc would be enough.
However, for topological_sort, this goes against my expectations. std::sort on an empty STL sequence may be useless, it is however defined and does the right thing. And it allows to write generic code easily, without requiring the user to check anything before. I do not see any reason why topological_sort would not behave the same.
I guess adding a simple test such as if( vertices( g ).first == vertices( g ).second ) return; at the beginning of topological_sort wouldn't hurt.
Daniel Mitchell <danmitchell@mail.utexas.edu> 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
On Jul 25, 2006, at 10:42 AM, David Abrahams wrote:
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.
If you happen to remember the reason, I'd like to know, because I've been hoping to eliminate the difference for the far-off, much- anticipated "BGLv2". Doug
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.
participants (5)
-
Cromwell Enage -
Daniel Mitchell -
David Abrahams -
Doug Gregor -
Loïc Joly