graph/adjacency_matrix: iterator goes past end
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. Regards, Guillaume
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. Doug
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.
On Monday 19 July 2004 12:34 am, Guillaume Melquiond wrote:
That's strange. I wouldn't have proposed a patch without first running the regression tests.
I hope it isn't compiler-dependent :( Which compiler are you using? Also, are you checking the program exit code? The test doesn't actually print anything, it just returns -1 on failure. I've changed the test to complain loudly if something does fail.
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.
I didn't mean to sound accusing; my apologies if I came across that way. The pre-patch code is clearly wrong; I'm just not sure how to fix it at the moment.
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...
I looked at the changes to adjacency_matrix_test.cpp; they're only formatting changes ("cvs diff -b" shows no differences). Reverting the patch to boost/graph/adjacency_matrix.hpp does "fix" the problem for me (i.e., adjacency_matrix_test passes now). I can dig into this later today or this evening, unless you have a chance; I don't understand the representation well enough to put in a quick fix now. Doug
Le lun 19/07/2004 à 17:56, Doug Gregor a écrit :
On Monday 19 July 2004 12:34 am, Guillaume Melquiond wrote:
That's strange. I wouldn't have proposed a patch without first running the regression tests.
I hope it isn't compiler-dependent :( Which compiler are you using?
No, I don't think it is compiler-dependent since I also get the failures now that I have updated my CVS. The iterator failure was detected by GCC 3.4.1. But I also tested with GCC 3.3.4 and Intel 8.
Also, are you checking the program exit code?
Bjam does it for me since it complains when the exit code is not 0. I did try to get back to the actual state of the trunk where the test passed, but I was unable to do it. [...]
I can dig into this later today or this evening, unless you have a chance; I don't understand the representation well enough to put in a quick fix now.
I think I understand the representation. But I don't even understand how the previous code could pass the regression test. I think it was only pure luck. Indeed, the test does this kind of loop: for (boost::tie(ei1, eend1) = boost::out_edges(*vi1, g1), boost::tie(ei2, eend2) = boost::out_edges(*vi2, g2); ei1 != eend1; ++ei1, ++ei2) { if (boost::get(index_map1, boost::target(*ei1, g1)) != boost::get(index_map2, boost::target(*ei2, g2))) return -1; } Please note that the edges for (1) are correctly computed. And it is the end iterator for (1) that is used to stop the loop. The wrong code was concerning the edges for (2). Since the code for (1) is correct, the loop was stopping before any problem with a wrong iterator for (2). With my patch, the iterator for (2) stays valid and consequently stop a lot sooner than before. Before the iterator for (1) in fact. And it's what causing the failure. I'm currently looking at correctly defining the iterator (2) so that it goes as far as necessary. But I wonder if anybody ever used the BGL with undirected graphs. I just spotted another obvious mistake: if you use a constant graph, get_edge(u,v) is given by "m_matrix[u * (u - 1)/2 + v]", but if you use a non-constant graph the result is "m_matrix[u * (u + 1)/2 + v]". So you will not get the same result depending on the const-ness of your adjacency matrix... I will also submit a patch for this. Regards, Guillaume
On Monday 19 July 2004 12:14 pm, Guillaume Melquiond wrote:
I think I understand the representation. But I don't even understand how the previous code could pass the regression test. I think it was only pure luck.
Seems like pure luck to me :)
I'm currently looking at correctly defining the iterator (2) so that it goes as far as necessary. But I wonder if anybody ever used the BGL with undirected graphs. I just spotted another obvious mistake: if you use a constant graph, get_edge(u,v) is given by "m_matrix[u * (u - 1)/2 + v]", but if you use a non-constant graph the result is "m_matrix[u * (u + 1)/2 + v]". So you will not get the same result depending on the const-ness of your adjacency matrix... I will also submit a patch for this.
Thanks! Doug
Hi, Now I think I have a correct solution. And I finally understood what the original code was doing; it would have been correct if there was an additional line in the adjacency triangular matrix. Indeed the iterator didn't try to stop on the first element outside the matrix but on the first line outside the matrix. So the patch I now submit transforms the edge iterator so that the end iterator doesn't go so far but stop at the end of the matrix. It involves a special casing in the increment of the iterator so that it doesn't try to reach far outside the matrix. In the middle of the patch also lies my correction for the const-ness problem of the get_edge function I was explaining in the previous mail. Regards, Guillaume PS: And so that there is no misunderstanding: **passed** ../../../bin/boost/libs/graph/test/adjacency_matrix_test.test/gcc-3.4/debug/adjacency_matrix_test.test **passed** ../../../bin/boost/libs/graph/test/adjacency_matrix_test.test/gcc/debug/adjacency_matrix_test.test **passed** ../../../bin/boost/libs/graph/test/adjacency_matrix_test.test/intel-linux/debug/adjacency_matrix_test.test :-) PPS: As a side note, I think the iterator could be made smaller by removing the m_inc variable and replacing it by m_targ since they are equivalent on the second half of the road and m_inc is not used on the first half. But it is a story for another time.
On Monday 19 July 2004 1:05 pm, Guillaume Melquiond wrote:
Now I think I have a correct solution. And I finally understood what the original code was doing; it would have been correct if there was an additional line in the adjacency triangular matrix. Indeed the iterator didn't try to stop on the first element outside the matrix but on the first line outside the matrix.
Oh, that makes sense.
So the patch I now submit transforms the edge iterator so that the end iterator doesn't go so far but stop at the end of the matrix. It involves a special casing in the increment of the iterator so that it doesn't try to reach far outside the matrix.
Looks good.
In the middle of the patch also lies my correction for the const-ness problem of the get_edge function I was explaining in the previous mail.
This looks fine, too. Thanks! Check it in whatever you'd like.
PPS: As a side note, I think the iterator could be made smaller by removing the m_inc variable and replacing it by m_targ since they are equivalent on the second half of the road and m_inc is not used on the first half. But it is a story for another time.
Another time, yes. I'd like to hold off on this type of change until after 1.32.0 is out there. Doug
participants (4)
-
Doug Gregor -
Guillaume Melquiond