[boost] Re: graph/adjacency_matrix: iterator goes past end

From: Guillaume Melquiond (guillaume.melquiond_at_[hidden])
Date: 2004-07-19 00:34:52

Le lun 19/07/2004 à 06:05, Doug Gregor a écrit :
> On Jul 17, 2004, at 3:26 AM, Guillaume Melquiond wrote:
> 
> > Hi,
> >
> > Line 567 of adjacency_matrix.hpp is:
> >
> >   typename Graph::MatrixIter l = g.m_matrix.end() + u;
> >
> > Obviously l is an iterator past the end. Looking at the algorithm, it
> > seems to me it shouldn't be g.m_matrix.end() but f. So here comes a
> > patch.
> 
> This patch breaks adjacency_matrix_test... I didn't look closely enough 
> to determine what went wrong, but line 171 does the return.

That's strange. I wouldn't have proposed a patch without first running
the regression tests. Moreover, I did propose a patch in the first place
because adjacency_matrix_test was failing for me. It was also failing in
Martin Wille's Linux regression logs. Here is an excerpt:

Linker output:
Chmod1 ../bin/boost/libs/graph/test/adjacency_matrix_test.test/gcc-3.4.1-linux/debug/adjacency_matrix_test

Run output:
/usr/local/gcc-3.4.1/lib/gcc/i686-pc-linux-gnu/3.4.1/../../../../include/c++/3.4.1/debug/safe_iterator.h:274:
    error: attempt to advance a past-the-end iterator 1 steps, which falls     
    outside its valid range.

Objects involved in the operation:
iterator @ 0x0xbfffe4e0 {
type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPcN10__gnu_norm6vectorIcSaIcEEEEEN15__gnu_debug_def6vectorIcS6_EEEE (mutable iterator);
  state = past-the-end;
  references sequence with type `N15__gnu_debug_def6vectorIcSaIcEEE' @ 0x0xbfffe4e0
}

EXIT STATUS: 134

So because it was failing, I was looking for a patch. And I only
submitted such a patch when there was no more failure in
adjacency_matrix_test (what would have been the benefit otherwise?).
Moreover, I hope you agree with me that the previous code was wrong.
Adding a positive value to an end() iterator is obviously an error.

Consequently, I'm not sure the failure is caused by my patch. Maybe
another patch somewhere (not necessarily in the Graph library) did break
something. For example, I see that 196 lines were changed in
adjacency_matrix_test.cpp yesterday. So maybe...

Regards,

Guillaume

PS: it doesn't mean I'm sure my patch is correct. I still don't know if
it is a correct behavior for out_edges in an undirected graph to behave
as if the graph was directed (it's what my patch does, I suppose). But
what I'm sure is that the previous code was wrong.