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

From: Cromwell Enage (sponage_at_[hidden])
Date: 2006-07-24 18:37:13

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