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

From: Guillaume Melquiond (guillaume.melquiond_at_[hidden])
Date: 2004-07-19 12:14:39

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